A polynomial-time classical algorithm for noisy quantum circuits

Abstract

We provide a polynomial-time classical algorithm for noisy quantum circuits. The algorithm computes the expectation value of any observable for any circuit, with a small average error over input states drawn from an ensemble (e.g. the computational basis). Our approach is based upon the intuition that noise exponentially damps non-local correlations relative to local correlations. This enables one to classically simulate a noisy quantum circuit by only keeping track of the dynamics of local quantum information. Our algorithm also enables sampling from the output distribution of a circuit in quasi-polynomial time, so long as the distribution anti-concentrates. A number of practical implications are discussed, including a fundamental limit on the efficacy of noise mitigation strategies: for constant noise rates, any quantum circuit for which error mitigation is efficient on most input states, is also classically simulable on most input states.

11 pages, 3 figures + 30 page Appendix

Cited by in corpus (5)

• Quantum many-body simulations with PauliStrings.jl
• Digital-analog quantum learning on Rydberg atom arrays
• Statistics of topological defects across a phase transition in a digital superconducting quantum processor
• Learning unitaries with quantum statistical queries
• Efficient Online Quantum Circuit Learning with No Upfront Training