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.

arXiv commentRevision 6, few minor typos corrected. 15 pages, 1 figure

References in corpus (29)

• Boson Sampling on a Photonic Chip
• Experimental Boson Sampling
• Experimental boson sampling in arbitrary integrated photonic circuits
• Photonic Boson Sampling in a Tunable Circuit
• 12-photon entanglement and scalable scattershot boson sampling with optimal entangled-photon pairs from parametric down-conversion
• Boson Sampling from Gaussian States
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Experimental Scattershot Boson Sampling
• BosonSampling with single-photon Fock states from a bright solid-state source
• No imminent quantum supremacy by boson sampling
• Scalable boson sampling with a single-photon device
• Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
• Scalable boson-sampling with time-bin encoding using a loop-based architecture
• Toward Scalable Boson Sampling with Photon Loss
• Efficient algorithm for boson sampling with partially distinguishable photons
• Partial indistinguishability theory for multi-photon experiments in multiport devices
• On the hardness of classically simulating the one clean qubit model
• Scalable Implementation of Boson Sampling with Trapped Ions
• A Linear-Optical Proof that the Permanent is #P-Hard
• Error tolerance of the BosonSampling model for linear optics quantum computing
• Classical simulation of photonic linear optics with lost particles
• BosonSampling with Lost Photons
• Sufficient bound on the mode mismatch of single photons for scalability of the boson sampling computer
• Microwave Boson Sampling
• Dynamical phase transitions in sampling complexity
• Tight bound on trace distance between a realistic device with partially indistinguishable bosons and the ideal Boson Sampling
• Collective phases of identical particles interfering on linear multiports
• Quantum simulation of partially distinguishable 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