Classical simulability of noisy boson sampling

Abstract

Quantum mechanics promises computational powers beyond the reach of classical computers. Current technology is on the brink of an experimental demonstration of the superior power of quantum computation compared to classical devices. For such a demonstration to be meaningful, experimental noise must not affect the computational power of the device; this occurs when a classical algorithm can use the noise to simulate the quantum system. In this work, we demonstrate an algorithm which simulates boson sampling, a quantum advantage demonstration based on many-body quantum interference of indistinguishable bosons, in the presence of optical loss. Finding the level of noise where this approximation becomes efficient lets us map out the maximum level of imperfections at which it is still possible to demonstrate a quantum advantage. We show that current photonic technology falls short of this benchmark. These results call into question the suitability of boson sampling as a quantum advantage demonstration.

Revised manuscript + added sup mat

Cited by in corpus (18)

• Photonic quantum information processing: a concise review
• Efficient classical simulation of noisy random quantum circuits in one dimension
• Regimes of classical simulability for noisy Gaussian boson sampling
• Sample complexity of device-independently certified "quantum supremacy"
• Classical simulation of linear optics subject to nonuniform losses
• Simulability of Imperfect Gaussian and Superposition Boson Sampling
• Distinguishing noisy boson sampling from classical simulations
• Simulating the Dynamics of Single Photons in BosonSampling Devices with Matrix Product States
• Optimizing spontaneous parametric down-conversion sources for boson sampling
• Analysis of optical loss thresholds in the fusion-based quantum computing architecture
• Efficient validation of Boson Sampling from binned photon-number distributions
• BosonSampling.jl: A Julia package for quantum multi-photon interferometry
• Marginal probabilities in boson samplers with arbitrary input states
• Efficient approximation of experimental Gaussian boson sampling
• Classical simulation of bosonic linear-optical random circuits beyond linear light cone
• On computational complexity and average-case hardness of shallow-depth boson sampling
• Sampling and the complexity of nature
• Physical Unclonable Functions with Boson Sampling