EUVIMEDEUVIMED entdecken
Crossref

A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling

Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, Umesh Vazirani

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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