EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A Polynomial-Time Classical Algorithm for Noisy Quantum Circuits

Thomas Schuster, Chao Yin, Xun Gao, Norman Y. Yao

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →