A Polynomial-Time Classical Algorithm for Noisy Quantum Circuits
Physical Review X · 03.11.2025 · 15 (4)
DOI: 10.1103/xct1-7kf2 ↗Kurz gefasst
Fachartikel in der Zeitschrift Physical Review X, online erschienen am 03.11.2025. Verfasst von Thomas Schuster und 3 weiteren Autor:innen. Die Arbeit wurde bisher 25-mal zitiert (Crossref) und nennt 103 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Walter Burke Institute for Theoretical Physics, U.S. Department of Energy, National Science Foundation.
Abstract (Originalsprache)
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 nonlocal correlations relative to local correlations. This enables one to classically simulate a noisy quantum circuit by keeping track of only the dynamics of local quantum information. Our algorithm also enables sampling from the output distribution of a circuit in quasipolynomial time, so long as the distribution anticoncentrates. A number of 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 succeeds in polynomial-time on most input states can also be classically simulated in polynomial-time on most input states. Our algorithms scale exponentially in the inverse noise rate, which is fundamental and makes them impractical for current quantum devices.
Förderung
- Walter Burke Institute for Theoretical Physics
- U.S. Department of Energy
- National Science Foundation
- Institute for Quantum Information and Matter, California Institute of Technology
- NSF Physics Frontiers Center
Zitieren
APA
Schuster, T., Yin, C., Gao, X., & Yao, N. Y. (2025). A Polynomial-Time Classical Algorithm for Noisy Quantum Circuits. Physical Review X, 15(4). https://doi.org/10.1103/xct1-7kf2
Vancouver
Schuster T, Yin C, Gao X, Yao NY. A Polynomial-Time Classical Algorithm for Noisy Quantum Circuits. Physical Review X. 2025;15(4). doi:10.1103/xct1-7kf2
BibTeX
@article{Schuster2025,
author = {Schuster, Thomas and Yin, Chao and Gao, Xun and Yao, Norman Y.},
title = {A Polynomial-Time Classical Algorithm for Noisy Quantum Circuits},
journal = {Physical Review X},
year = {2025},
volume = {15},
number = {4},
doi = {10.1103/xct1-7kf2}
}
EUVIMED