A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling
Abstract. 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.
Authors
- Dorit Aharonov (ORCID: https://orcid.org/0000-0002-9378-8495)
- Yunchao Liu (ORCID: https://orcid.org/0000-0003-1297-6396)
- Umesh V. Vazirani
- Zeph A. Landau (ORCID: https://orcid.org/0009-0009-7316-7585)
- Xun Gao
Institutions
- Berkeley College (US)
- Hebrew University of Jerusalem (IL)
- Somerville Hospital (US)
- University of California, Berkeley (US)
Publication Details
- Journal
- SIAM Journal on Computing
- Published
- 2026-11-03
- DOI
- https://doi.org/10.1137/23m1596557
- Primary Topic
- Quantum Computing Algorithms and Architecture
- Type
- article
- Field-Weighted Citation Impact
- 0.00