Boson sampling is a quantum mechanical task involving Fock basis state preparation and detection and evolution using only linear interactions. A classical algorithm for producing samples from this quantum task cannot be efficient unless the polynomial hierarchy of complexity classes collapses, a situation believed to be highly implausible. We present a method for constructing a device which uses Fock state preparations, linear interactions, and Gaussian continuous-variable measurements for which one can show that exact sampling would be hard for a classical algorithm in the same way as boson sampling. The detection events used from this arrangement do not allow a similar conclusion to be drawn for the classical hardness of approximate sampling. We discuss the details of this result outlining some specific properties required by approximate sampling hardness.
BosonSampling, 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\textquotedblright\ from a uniform random outcome, at least \textquotedblleft 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 such 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 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 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 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 Fermion Sampling is solvable in classical polynomial time, and we reuse techniques from our Boson Sampling analysis to characterize random FermionSampling distributions.
The extended Church-Turing theeie posits that any computable function can be oalculated efficitntly by a probabilistic Turing machine. If this thesis held true, thee global effort; to build quantum computers might ultimhiely be unnecessary. The thesis would however be strongly contradicted by a physical device that efficiently performs a task believed to be intractable for classical computers. BOSONSAMPLING—the sampling from a distribution of n photons undergoing some linear-optical process—is a recently developed, and experimentally accessible example of such a task [1].
Boson-Sampling is a classically computationally hard problem that can - in principle - be efficiently solved with quantum linear optical networks. Very recently, a rush of experimental activity has ignited with the aim of developing such devices as feasible instances of quantum simulators. Even approximate Boson-Sampling is believed to be hard with high probability if the unitary describing the optical network is drawn from the Haar measure. In this work we show that in this setup, with probability exponentially close to one in the number of bosons, no symmetric algorithm can distinguish the Boson-Sampling distribution from the uniform one from fewer than exponentially many samples. This means that the two distributions are operationally indistinguishable without detailed a priori knowledge. We carefully discuss the prospects of efficiently using knowledge about the implemented unitary for devising non-symmetric algorithms that could potentially improve upon this. We conclude that due to the very fact that Boson-Sampling is believed to be hard, efficient classical certification of Boson-Sampling devices seems to be out of reach.
Boson sampling is a computational problem that has recently been proposed as a candidate to obtain an unequivocal quantum computational advantage. The problem consists in sampling from the output distribution of indistinguishable bosons in a linear interferometer. There is strong evidence that such an experiment is hard to classically simulate, but it is naturally solved by dedicated photonic quantum hardware, comprising single photons, linear evolution, and photodetection. This prospect has stimulated much effort resulting in the experimental implementation of progressively larger devices. We review recent advances in photonic boson sampling, describing both the technological improvements achieved and the future challenges. We also discuss recent proposals and implementations of variants of the original problem, theoretical issues occurring when imperfections are considered, and advances in the development of suitable techniques for validation of boson sampling experiments. We conclude by discussing the future application of photonic boson sampling devices beyond the original theoretical scope.