Quantum computational advantage of noisy boson sampling with partially distinguishable photons

Abstract

Boson sampling stands out as a promising approach toward experimental demonstration of quantum computational advantage. However, the presence of physical noise in near-term experiments hinders the realization of the quantum computational advantage with boson sampling. Since physical noise in near-term boson sampling devices is inevitable, precise characterization of the boundary of noise rates where the classical intractability of boson sampling is maintained is crucial for quantum computational advantage using near-term devices. In this work, we identify the level of partial distinguishability noise that upholds the classical intractability of boson sampling. We find that boson sampling with on average $O(\log N)$ number of distinguishable photons out of $N$ input photons maintains the equivalent complexity to the ideal boson sampling case. By providing strong complexity theoretical evidence for the classical intractability of noisy boson sampling, we expect that our findings will ultimately facilitate the demonstration of quantum computational advantage with noisy boson sampling experiments in the near future.

arXiv comment19 pages, 1 figure

References in corpus (34)

• Quantum Computing in the NISQ era and beyond
• Efficient classical simulation of slightly entangled quantum computations
• Quantum computational advantage using photons
• Error mitigation for short-depth quantum circuits
• Efficient variational quantum simulator incorporating active error minimisation
• Quantum Error Mitigation
• Gaussian Boson Sampling
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• A detailed study of Gaussian Boson Sampling
• Gaussian Boson Sampling with Pseudo-Photon-Number Resolving Detectors and Quantum Computational Advantage
• Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
• Sampling of partially distinguishable bosons and the relation to the multidimensional permanent
• Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
• Efficient algorithm for boson sampling with partially distinguishable photons
• Simulating boson sampling in lossy architectures
• The Boundary for Quantum Advantage in Gaussian Boson Sampling
• Regimes of classical simulability for noisy Gaussian boson sampling
• Classical simulation of photonic linear optics with lost particles
• Direct dialling of Haar random unitary matrices
• BosonSampling with Lost Photons
• Sufficient bound on the mode mismatch of single photons for scalability of the boson sampling computer
• Scalable and Programmable Phononic Network with Trapped Ions
• Classical algorithm for simulating experimental Gaussian boson sampling
• Dynamical phase transitions in sampling complexity
• The Complexity of Bipartite Gaussian Boson Sampling
• Classical simulation of boson sampling based on graph structure
• Classical simulation of linear optics subject to nonuniform losses
• An atomic boson sampler
• Simulability of Imperfect Gaussian and Superposition Boson Sampling
• Classically simulating near-term partially-distinguishable and lossy boson sampling
• Noise in BosonSampling and the threshold of efficient classical simulatability
• Exploring Shallow-Depth Boson Sampling: Towards Scalable Quantum Supremacy
• Classical simulability of constant-depth linear-optical circuits with noise