A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling
SIAM Journal on Computing · 03.11.2026 · STOC23-408-STOC23-437
DOI: 10.1137/23m1596557 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 03.11.2026. Verfasst von Dorit Aharonov und 4 weiteren Autor:innen. Die Arbeit nennt 39 Literaturangaben. Gefördert von: Vannevar Bush, MPHQ, Multidisciplinary University Research Initiative.
Abstract (Originalsprache)
We give a polynomial time classical algorithm for sampling from the output distribution of a noisy random quantum circuit in the regime of anticoncentration to within inverse polynomial total variation distance. The algorithm is based on a quantum analog of noise induced low degree approximations of Boolean functions, which takes the form of the truncation of a Feynman path integral in the Pauli basis.
Förderung
- Vannevar Bush
- MPHQ
- Multidisciplinary University Research Initiative
- Army Research Office
- Israel Science Foundation
- National Science Foundation
- Templeton Religion Trust
- U.S. Department of Energy
Zitieren
APA
Aharonov, D., Gao, X., Landau, Z., Liu, Y., & Vazirani, U. (2026). A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling. SIAM Journal on Computing, STOC23-408-STOC23-437. https://doi.org/10.1137/23m1596557
Vancouver
Aharonov D, Gao X, Landau Z, Liu Y, Vazirani U. A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling. SIAM Journal on Computing. 2026:STOC23-408-STOC23-437. doi:10.1137/23m1596557
BibTeX
@article{Aharonov2026,
author = {Aharonov, Dorit and Gao, Xun and Landau, Zeph and Liu, Yunchao and Vazirani, Umesh},
title = {A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling},
journal = {SIAM Journal on Computing},
year = {2026},
pages = {STOC23--408--STOC23--437},
doi = {10.1137/23m1596557}
}
EUVIMED