Efficient classical simulation of noisy quantum computation

Abstract

Understanding the boundary between classical simulatability and the power of quantum computation is a fascinating topic. Direct simulation of noisy quantum computation requires solving an open quantum many-body system, which is very costly. Here, we develop a tensor network formalism to simulate the time-dynamics and the Fourier spectrum of noisy quantum circuits. We prove that under general conditions most of the quantum circuits at any constant level of noise per gate can be efficiently simulated classically with the cost increasing only polynomially with the size of the circuits. The result holds even if we have perfect noiseless quantum gates for some subsets of operations, such as all the gates in the Clifford group. This surprising result reveals the subtle relations between classical simulatability, quantum supremacy, and fault-tolerant quantum computation. The developed simulation tools may also be useful for solving other open quantum many-body systems.

11 pages, 6 figures

References in corpus (7)

• Non-Abelian Anyons and Topological Quantum Computation
• Quantum Computational Supremacy
• Evenly distributed unitaries: on the structure of unitary designs
• Quantum computing and the entanglement frontier
• Tensor Networks in a Nutshell
• Fourier analysis of sampling from noisy chaotic quantum circuits
• Can Chaotic Quantum Circuits Maintain Quantum Supremacy under Noise?

Cited by in corpus (15)

• Variational Quantum Monte Carlo Method with a Neural-Network Ansatz for Open Quantum Systems
• A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware
• Efficient classical simulation of random shallow 2D quantum circuits
• Efficient classical simulation of noisy random quantum circuits in one dimension
• Regimes of classical simulability for noisy Gaussian boson sampling
• Random quantum circuits anti-concentrate in log depth
• Classical algorithm for simulating experimental Gaussian boson sampling
• Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions
• Efficient classical simulation of Clifford circuits with nonstabilizer input states
• Noise and the frontier of quantum supremacy
• Effects of quantum resources on the statistical complexity of quantum circuits
• Entanglement entropy scaling of noisy random quantum circuits in two dimensions
• Rademacher complexity of noisy quantum circuits
• Approximate Equivalence Checking of Noisy Quantum Circuits
• Sampling and the complexity of nature