A polynomial-time classical sampler for noisy quantum circuits from statistical mechanics

Abstract

Developing classical simulation algorithms for noisy quantum circuits is essential to delineating the limits of quantum advantage. Existing classical sampling approaches for general circuits require circuit depths to grow logarithmically with system size, so that noise drives the global output state close to a trivial state. Here we show that local accumulation of noise at a depth independent of system size is already sufficient. Specifically, we prove that any geometrically local circuit composed of unital operations and interspersed with single-qubit depolarizing noise of strength p after Θ(p⁻¹ log p⁻¹) depth can be approximately sampled from a polynomial-time classical computer. This generalizes existing results that impose anticoncentration assumptions or non-universal gate sets in order to obtain a classical sampler at such shallow depths. Our proof maps the output state of the circuit to a polymer model in statistical mechanics, and combines a convergent cluster expansion with hypercontractivity of the depolarizing channel.

Statistical mechanics of classical fractons on a line
Ylias Sadki, Abhishodh Prakash, S. L. Sondhi
arXiv22 Sep 2026PreprintCC BY 4.0Full textCondensed matter Statistical & nonlinear physicsarXiv
Indeterminism and classical mechanics
Alexander Givental
arXiv1 Oct 2026PreprintCC BY 4.0Full textGeneral physicsarXiv
Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits
Matthew Coudron, Michael J. Gullans, Jon Nelson +2
arXiv1 Oct 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
On the Statistical Mechanics of Attention
Jerry Yao-Chieh Hu, Yu-An Chen, Maojiang Su +1
arXiv12 Oct 2026PreprintCC BY-NC-SA 4.0Full textStatistics Condensed matterarXiv
Statistical mechanics of spontaneous behavior
Daniel Y. Takahashi, Ahmed El Hady
arXiv1 Nov 2026PreprintCC BY 4.0Full textNeuroscience Biological & medical physicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{nelson2026polynomialtime,
  title = {{A polynomial-time classical sampler for noisy quantum circuits from statistical mechanics}},
  author = {Jon Nelson and Joel Rajakumar and Chao Yin and Yifan F. Zhang and Michael J. Gullans},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.00548},
  eprint = {2610.00548},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.00548},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - A polynomial-time classical sampler for noisy quantum circuits from statistical mechanics
AU  - Jon Nelson
AU  - Joel Rajakumar
AU  - Chao Yin
AU  - Yifan F. Zhang
AU  - Michael J. Gullans
PY  - 2026
DA  - 2026/10/05
PB  - arXiv
DO  - 10.48550/arxiv.2610.00548
UR  - https://arxiv.org/abs/2610.00548
AB  - Developing classical simulation algorithms for noisy quantum circuits is essential to delineating the limits of quantum advantage. Existing classical sampling approaches for general circuits require circuit depths to grow logarithmically with system size, so that noise drives the global output state close to a trivial state. Here we show that local accumulation of noise at a depth independent of system size is already sufficient. Specifically, we prove that any geometrically local circuit composed of unital operations and interspersed with single-qubit depolarizing noise of strength p after Θ(p^−1 log p^−1) depth can be approximately sampled from a polynomial-time classical computer. This generalizes existing results that impose anticoncentration assumptions or non-universal gate sets in order to obtain a classical sampler at such shallow depths. Our proof maps the output state of the circuit to a polymer model in statistical mechanics, and combines a convergent cluster expansion with hypercontractivity of the depolarizing channel.
ER  -

Abstract

Related

Cite