# A polynomial-time classical algorithm for noisy random circuit sampling

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

- Archive id: arxiv:2211.03999
- Published: 2022-11-08
- Venue: In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023)
- DOI: https://doi.org/10.1145/3564246.3585234
- arXiv: https://arxiv.org/abs/2211.03999
- Citations: 69
- Source URL: https://arxiv.org/abs/2211.03999
- PDF: https://arxiv.org/pdf/2211.03999
- Provenance: arxiv

## Abstract

We give a polynomial time classical algorithm for sampling from the output distribution of a noisy random quantum circuit in the regime of anti-concentration to within inverse polynomial total variation distance. This gives strong evidence that, in the presence of a constant rate of noise per gate, random circuit sampling (RCS) cannot be the basis of a scalable experimental violation of the extended Church-Turing thesis. Our algorithm is not practical in its current form, and does not address finite-size RCS based quantum supremacy experiments.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Quantum Algorithms & Quantum Advantage](https://space-kitty.com/topics/quantum-algorithms-advantage)

Cited in dossiers:
- [Quantum Algorithms & Quantum Advantage: State of the Field (October 2026)](https://space-kitty.com/dossiers/quantum-algorithms-advantage)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.