Classical simulation of bosonic linear-optical random circuits beyond linear light cone
arXiv:2102.10083
Abstract
Sampling from probability distributions of quantum circuits is a fundamentally and practically important task which can be used to demonstrate quantum supremacy using noisy intermediate-scale quantum devices. In the present work, we examine classical simulability of sampling from the output photon-number distribution of linear-optical circuits composed of random beam splitters with equally distributed squeezed vacuum states and single-photon states input. We provide efficient classical algorithms to simulate linear-optical random circuits and show that the algorithms' error is exponentially small up to a depth less than quadratic in the distance between sources using a classical random walk behavior of random linear-optical circuits. Notably, the average-case depth allowing an efficient classical simulation is larger than the worst-case depth limit, which is linear in the distance. Besides, our results together with the hardness of boson sampling give a lower-bound on the depth for constituting global Haar-random unitary circuits.
arXiv comment16 pages, 1 figure. Significant improvement has been made and updated in arXiv:2110.01564
References in corpus (29)
- Quantum Computing in the NISQ era and beyond
- Gaussian Quantum Information
- Efficient classical simulation of slightly entangled quantum computations
- Quantum state transfer and entanglement distribution among distant nodes in a quantum network
- Continuous variable quantum information: Gaussian states and beyond
- Operator Spreading in Random Unitary Circuits
- Ballistic spreading of entanglement in a diffusive nonintegrable system
- Gaussian Boson Sampling
- Operator spreading and the emergence of dissipative hydrodynamics under unitary evolution with conservation laws
- Lieb-Robinson and the butterfly effect
- Quantum Supremacy and the Complexity of Random Circuit Sampling
- Quantum fidelity for arbitrary Gaussian states
- A detailed study of Gaussian Boson Sampling
- Efficient classical simulation of random shallow 2D quantum circuits
- Gaussian Boson Sampling using threshold detectors
- Mode-Wise Entanglement of Gaussian States
- Simulating boson sampling in lossy architectures
- Regimes of classical simulability for noisy Gaussian boson sampling
- Scrambling and Complexity in Phase Space
- Exact simulation of Gaussian Boson Sampling in polynomial space and exponential time
- Dynamical phase transitions in sampling complexity
- Classical simulation of lossy boson sampling using matrix product operators
- Noise and the frontier of quantum supremacy
- A limit formula for the quantum fidelity
- Classical simulability of noisy boson sampling
- Quantum supremacy and random circuits
- Power of Quantum Computation with Few Clean Qubits
- The complexity of simulating constant-depth BosonSampling
- Complexity phase diagram for interacting and long-range bosonic Hamiltonians