Noise in BosonSampling and the threshold of efficient classical simulatability

Abstract

We study the quantum to classical transition in Boson Sampling by analysing 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 $\epsilon$, i.e., $\epsilon =\Omega (1)$ as $N\to \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., $\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\to \infty$ for arbitrarily small noise amplitude, i.e., $\epsilon =o(1)$ as $N\to \infty$, hence, we conjecture that such a noisy Boson Sampling is also hard to simulate classically. The results significantly relax sufficient condition on noise in a network components, such as two-mode beam splitters, for classical hardness of experimental Boson Sampling.

Revision 6, few minor typos corrected. 15 pages, 1 figure

References in corpus (7)

• Photonic Boson Sampling in a Tunable Circuit
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Experimental Scattershot Boson Sampling
• Scalable boson-sampling with time-bin encoding using a loop-based architecture
• Partial indistinguishability theory for multi-photon experiments in multiport devices
• Tight bound on trace distance between a realistic device with partially indistinguishable bosons and the ideal Boson Sampling
• Decoherence and Interferometric Sensitivity of BosonSampling in Superconducting Networks

Cited by in corpus (21)

• Computational advantage of quantum random sampling
• Simulability of Imperfect Gaussian and Superposition Boson Sampling
• Classically simulating near-term partially-distinguishable and lossy boson sampling
• Spoofing cross entropy measure in boson sampling
• Simulating lossy Gaussian boson sampling with matrix product operators
• Distinguishing noisy boson sampling from classical simulations
• Signatures of Many-Particle Interference
• Quantum supremacy of the many-body fluctuations in the occupations of the excited particle states in a Bose-Einstein-condensed gas
• Efficient validation of Boson Sampling from binned photon-number distributions
• Fault-tolerant quantum speedup from constant depth quantum circuits
• Sample-efficient benchmarking of multi-photon interference on a boson sampler in the sparse regime
• Exploring Shallow-Depth Boson Sampling: Towards Scalable Quantum Supremacy
• Hardware requirements for realizing a quantum advantage with deterministic single-photon sources
• Gaussian boson sampling with partial distinguishability
• BosonSampling.jl: A Julia package for quantum multi-photon interferometry
• Distinguishability theory for time-resolved photodetection and boson sampling
• Speedup in Classical Simulation of Gaussian Boson Sampling
• On computational complexity and average-case hardness of shallow-depth boson sampling
• Quantum computational advantage of noisy boson sampling with partially distinguishable photons
• Physical Unclonable Functions with Boson Sampling
• Emergence of biased errors in imperfect photonic circuits