Classical simulability of constant-depth linear-optical circuits with noise

Abstract

Noise is one of the main obstacles to realizing quantum devices that achieve a quantum computational advantage. A possible approach to minimize the noise effect is to employ shallow-depth quantum circuits since noise typically accumulates as circuit depth grows. In this work, we investigate the complexity of shallow-depth linear-optical circuits under the effects of photon loss and partial distinguishability. By establishing a correspondence between a linear-optical circuit and a bipartite graph, we show that the effects of photon loss and partial distinguishability are equivalent to removing the corresponding vertices. Using this correspondence and percolation theory, we prove that for constant-depth linear-optical circuits with single photons, there is a threshold of loss (noise) rate above which the linear-optical systems can be decomposed into smaller systems with high probability, which enables us to simulate the systems efficiently. Consequently, our result implies that even in shallow-depth circuits where noise is not accumulated enough, its effect may be sufficiently significant to make them efficiently simulable using classical algorithms due to its entanglement structure constituted by shallow-depth circuits.

10+4 pages, 3+1 figures

References in corpus (41)

• The density-matrix renormalization group in the age of matrix product states
• Review article: Linear optical quantum computing
• Efficient classical simulation of slightly entangled quantum computations
• Quantum computational advantage using photons
• Advances in Photonic Quantum Sensing
• Photonic quantum information processing: a concise review
• Boson sampling with 20 input photons in 60-mode interferometers at $10^{14}$ state spaces
• Positive Wigner functions render classical simulation of quantum computation efficient
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Real-time quantum error correction beyond break-even
• Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer
• Building a fault-tolerant quantum computer using concatenated cat codes
• Entanglement Percolation in Quantum Networks
• Gaussian Boson Sampling with Pseudo-Photon-Number Resolving Detectors and Quantum Computational Advantage
• Sampling of partially distinguishable bosons and the relation to the multidimensional permanent
• High-dimensional frequency crystals and quantum walks in electro-optic microcombs
• Efficient algorithm for boson sampling with partially distinguishable photons
• A Quantum to Classical Phase Transition in Noisy Quantum Computers
• Simulating boson sampling in lossy architectures
• Entanglement percolation in quantum complex networks
• 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
• Quantum optical coherence can survive photon losses: a continuous-variable quantum erasure correcting code
• Scalable and Programmable Phononic Network with Trapped Ions
• A proposal for a scalable universal bosonic simulator using individually 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
• 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
• Classically simulating near-term partially-distinguishable and lossy boson sampling
• Simulating lossy Gaussian boson sampling with matrix product operators
• The complexity of simulating constant-depth BosonSampling
• Distillation of Indistinguishable Photons
• Quantum Filtering of Optical Coherent States
• Exploring Shallow-Depth Boson Sampling: Towards Scalable Quantum Supremacy
• Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
• Information transmission with continuous variable quantum erasure channels
• SUperman: Efficient Permanent Computation on GPUs

Cited by in corpus (4)

• Quantum computational advantage of noisy boson sampling with partially distinguishable photons
• On computational complexity and average-case hardness of shallow-depth boson sampling
• Classical algorithms for measurement-adaptive Gaussian circuits
• Linear-optical protocols for mitigating and suppressing noise in bosonic systems