We study the quantum to classical transition in boson sampling by analyzing how
N-boson interference is affected by inevitable noise in an experimental setup. We adopt the Gaussian noise model of Kalai and Kindler for boson sampling and show that it appears from some realistic experimental imperfections. We reveal a connection between noise in boson sampling and partial distinguishability of bosons, which allows us to prove efficient classical simulatability of noisy no-collision boson sampling with finite noise amplitude $\ensuremath{\epsilon}$, i.e., $\ensuremath{\epsilon}=\mathrm{\ensuremath{\Omega}}(1)$ as $N\ensuremath{\rightarrow}\ensuremath{\infty}$. On the other hand, using an equivalent representation of network noise as losses of bosons compensated by random (dark) counts of detectors, it is proven that for noise amplitude inversely proportional to total number of bosons, i.e., $\ensuremath{\epsilon}=O(1/N)$, noisy no-collision boson sampling is as hard to simulate classically as in the noiseless case. Moreover, the ratio of ``noise clicks'' (lost bosons compensated by dark counts) to the total number of bosons
N vanishes as $N\ensuremath{\rightarrow}\ensuremath{\infty}$ for arbitrarily small noise amplitude, i.e., $\ensuremath{\epsilon}=o(1)$ as $N\ensuremath{\rightarrow}\ensuremath{\infty}$; hence, we conjecture that such a noisy boson sampling is also hard to simulate classically. The results significantly relax the sufficient condition on noise in network components, such as two-mode beam splitters, for classical hardness of experimental boson sampling
We present a classical algorithm that approximately samples from the output distribution of certain noisy Boson Sampling experiments. This algorithm is inspired by a recent result of Aharonov, Gao, Landau, Liu and Vazirani and makes use of an observation originally due to Kalai and Kindler that the output probability of Boson Sampling experiments with a Gaussian noise model can be approximated by sparse low-degree polynomials. This observation alone does not suffice for classical sampling, because its marginal probabilities might not be approximated by sparse low-degree polynomials, and furthermore, the approximated probabilities might be negative. We solve this problem by employing the first quantization representation to give an algorithm for computing the marginal probabilities of these experiments. We prove that when the overall noise rate is constant, the algorithm runs in time quasi-polynomial in the number of input photons
N and accuracy. When the overall noise rate scales as
1−x1γ for constant
x1 and
γ=Ω(logN), the running time becomes polynomial. Furthermore, we study noisy Boson Sampling with practically relevant noise models such as partial distinguishability and photon loss. We show that the same technique does not immediately apply in these settings, leaving open the possibility of a scalable demonstration of noisy quantum advantage for these noise models in certain parameter regimes.