On computational complexity and average-case hardness of shallow-depth boson sampling

Abstract

Boson sampling, a computational task believed to be classically hard to simulate, is expected to hold promise for demonstrating quantum computational advantage using near-term quantum devices. However, noise in experimental implementations poses a significant challenge, potentially rendering boson sampling classically simulable and compromising its classical intractability. Numerous studies have proposed classical algorithms under various noise models that can efficiently simulate boson sampling as noise rates increase with circuit depth. To address this issue particularly related to circuit depth, we explore the viability of achieving quantum computational advantage through boson sampling with shallow-depth linear optical circuits. Specifically, as the average-case hardness of estimating output probabilities of boson sampling is a crucial ingredient in demonstrating its classical intractability, we make progress on establishing the average-case hardness confined to logarithmic-depth regimes. We also obtain the average-case hardness for logarithmic-depth Fock-state boson sampling subject to lossy environments and for the logarithmic-depth Gaussian boson sampling. By providing complexity-theoretical backgrounds for the classical simulation hardness of logarithmic-depth boson sampling, we expect that our findings will mark a crucial step towards a more noise-tolerant demonstration of quantum advantage with shallow-depth boson sampling.

References in corpus (42)

• Efficient classical simulation of slightly entangled quantum computations
• Quantum computational advantage using photons
• Gaussian Boson Sampling
• Universal blind quantum computation
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Boson Sampling from Gaussian States
• Average-case complexity versus approximate simulation of commuting quantum computations
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Gaussian Boson Sampling with Pseudo-Photon-Number Resolving Detectors and Quantum Computational Advantage
• Unified derivations of measurement-based schemes for quantum computation
• A Note on Linear Optics Gates by Post-Selection
• Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
• Efficient algorithm for boson sampling with partially distinguishable photons
• Simulating boson sampling in lossy architectures
• Architectures for quantum simulation showing a quantum speedup
• The Boundary for Quantum Advantage in Gaussian Boson Sampling
• Scalable Implementation of Boson Sampling with Trapped Ions
• 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
• Anticoncentration theorems for schemes showing a quantum speedup
• Scalable and Programmable Phononic Network with Trapped Ions
• Classical algorithm for simulating experimental Gaussian boson sampling
• Classical simulation of lossy boson sampling using matrix product operators
• 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
• Simulability of Imperfect Gaussian and Superposition Boson Sampling
• Noise in BosonSampling and the threshold of efficient classical simulatability
• Classically simulating near-term partially-distinguishable and lossy boson sampling
• Classical simulability of noisy boson sampling
• Simulating lossy Gaussian boson sampling with matrix product operators
• The complexity of simulating constant-depth BosonSampling
• Noise Threshold of Quantum Supremacy
• Exploring Shallow-Depth Boson Sampling: Towards Scalable Quantum Supremacy
• On classical simulation algorithms for noisy Boson Sampling
• Classical simulability of constant-depth linear-optical circuits with noise
• Average-case hardness of estimating probabilities of random quantum circuits with a linear scaling in the error exponent
• Complexity-theoretic foundations of BosonSampling with a linear number of modes
• Efficient classical algorithm for simulating boson sampling with heterogeneous partial distinguishability
• Exponential improvements to the average-case hardness of BosonSampling

Cited by in corpus (1)

• Boundaries for quantum advantage with single photons and loop-based time-bin interferometers