ECCC-Report TR13-135https://eccc.weizmann.ac.il/report/2013/135Comments and Revisions published for TR13-135en-usTue, 01 Oct 2013 05:49:30 +0300
Revision 2
| BosonSampling Is Far From Uniform |
Scott Aaronson,
Alex Arkhipov
https://eccc.weizmann.ac.il/report/2013/135#revision2BosonSampling, which we proposed three years ago, is a scheme for using linear-optical networks to solve sampling problems that appear to be intractable for a classical computer. In a recent manuscript, Gogolin et al. claimed that even an ideal BosonSampling device's output would be "operationally indistinguishable" from a uniform random outcome, at least "without detailed a priori knowledge"; or at any rate, that telling the two apart might itself be a hard problem. We first answer these claims---explaining why the first is based on a definition of "a priori knowledge" so strange that, were it adopted, almost no quantum algorithm could be distinguished from a pure random-number source; while the second is neither new nor a practical obstacle to interesting BosonSampling experiments. However, we then go further, and address some interesting research questions inspired by Gogolin et al.'s mistaken arguments. We prove that, with high probability over a Haar-random matrix A, the BosonSampling distribution induced by A is far from the uniform distribution in total variation distance. More surprisingly, and directly counter to Gogolin et al., we give an efficient algorithm that distinguishes these two distributions with constant bias. Finally, we offer three "bonus" results about BosonSampling. First, we report an observation of Fernando Brandao: that, by applying a general theorem of Trevisan, Tulsiani, and Vadhan, one can efficiently sample a distribution that has large entropy and that's indistinguishable from a BosonSampling distribution by any circuit of fixed polynomial size. Second, we show that BosonSampling distributions can be efficiently distinguished from uniform even with photon losses and for general initial states. Third, we offer the simplest known proof that FermionSampling is solvable in classical polynomial time, and we reuse techniques from our BosonSampling analysis to characterize random FermionSampling distributions.Tue, 01 Oct 2013 05:49:30 +0300https://eccc.weizmann.ac.il/report/2013/135#revision2
Revision 1
| BosonSampling Is Far From Uniform |
Scott Aaronson,
Alex Arkhipov
https://eccc.weizmann.ac.il/report/2013/135#revision1BosonSampling, which we proposed three years ago, is a scheme for using linear-optical networks to solve sampling problems that appear to be intractable for a classical computer. In a recent manuscript, Gogolin et al. claimed that even an ideal BosonSampling device's output would be "operationally indistinguishable" from a uniform random outcome, at least "without detailed a priori knowledge"; or at any rate, that telling the two apart might itself be a hard problem. We first answer these claims---explaining why the first is based on a definition of "a priori knowledge" so strange that, were it adopted, almost no quantum algorithm could be distinguished from a pure random-number source; while the second is neither new nor a practical obstacle to interesting BosonSampling experiments. However, we then go further, and address some interesting research questions inspired by Gogolin et al.'s mistaken arguments. We prove that, with high probability over a Haar-random matrix A, the BosonSampling distribution induced by A is far from the uniform distribution in total variation distance. More surprisingly, and directly counter to Gogolin et al., we give an efficient algorithm that distinguishes these two distributions with constant bias. Finally, we offer three "bonus" results about BosonSampling. First, we report a striking observation due to Fernando Brandao: that, by applying a recent result of Trevisan, Tulsiani, and Vadhan, one can efficiently sample a distribution that is indistinguishable from a BosonSampling distribution by any circuit of fixed polynomial size. Second, we show that BosonSampling distributions can be efficiently distinguished from uniform even with photon losses and for general initial states. Third, we offer the simplest known proof that FermionSampling is solvable in classical polynomial time, and we reuse techniques from our BosonSampling analysis to characterize random FermionSampling distributions.Fri, 27 Sep 2013 23:10:15 +0300https://eccc.weizmann.ac.il/report/2013/135#revision1
Paper TR13-135
| BosonSampling Is Far From Uniform |
Scott Aaronson
https://eccc.weizmann.ac.il/report/2013/135BosonSampling, which we proposed three years ago, is a scheme for using linear-optical networks to solve sampling problems that appear to be intractable for a classical computer. In a recent manuscript, Gogolin et al. claimed that even an ideal BosonSampling device's output would be "operationally indistinguishable" from a uniform random outcome, at least "without detailed a priori knowledge"; or at any rate, that telling the two apart might itself be a hard problem. We first answer these claims---explaining why the first is based on a definition of "a priori knowledge" so strange that, were it adopted, almost no quantum algorithm could be distinguished from a pure random-number source; while the second is neither new nor a practical obstacle to interesting BosonSampling experiments. However, we then go further, and address some interesting research questions inspired by Gogolin et al.'s mistaken arguments. We prove that, with high probability over a Haar-random matrix A, the BosonSampling distribution induced by A is far from the uniform distribution in total variation distance. More surprisingly, and directly counter to Gogolin et al., we give an efficient algorithm that distinguishes these two distributions with constant bias. Finally, we offer three "bonus" results about BosonSampling. First, we report a striking observation due to Fernando Brandao: that, by applying a recent result of Trevisan, Tulsiani, and Vadhan, one can efficiently sample a distribution that is indistinguishable from a BosonSampling distribution by any circuit of fixed polynomial size. Second, we show that BosonSampling distributions can be efficiently distinguished from uniform even with photon losses and for general initial states. Third, we offer the simplest known proof that FermionSampling is solvable in classical polynomial time, and we reuse techniques from our BosonSampling analysis to characterize random FermionSampling distributions.Fri, 27 Sep 2013 22:50:20 +0300https://eccc.weizmann.ac.il/report/2013/135