How long can a noisy quantum computer run before a laptop can imitate it? For devices built from local gates on a chip or an array, with noise striking every qubit at every step and no fresh qubits or mid-circuit resets, a new paper gives a sharp answer: not very long. After a depth that depends only on the noise rate, and not on the number of qubits, the output can be sampled efficiently on a classical computer.
This article was drafted with Claude and fact-checked against the cited primary sources. The paper is “A polynomial-time classical sampler for noisy quantum circuits from statistical mechanics” by Jon Nelson, Joel Rajakumar, Chao Yin, Yifan F. Zhang and Michael J. Gullans (arXiv:2610.00548, submitted 30 September 2026).
Why this paper is worth reading
The standard argument for why noise eventually kills quantum advantage is global: under local depolarizing noise, the whole output distribution drifts toward uniform, and once the circuit depth grows faster than logarithmically in the number of qubits n, sampling becomes classically easy. That argument leaves a large window open. Circuits of constant or slowly growing depth are exactly where many proposed near-term advantage experiments live, and previous classical algorithms for that window only handled specific cases, such as random circuits, restricted gate sets, or estimating expectation values rather than sampling.
The authors close much of this window for a general class of circuits. They prove that noise does not need to wash out the global state; it is enough for it to accumulate locally.
What the paper does
The setting is precise. Qubits sit on a D-dimensional lattice with D constant. Each of d layers applies two-qubit unital operations (unitaries, or more generally unital channels) to nearest-neighbour pairs, and after every layer each qubit suffers single-qubit depolarizing noise of strength p. The input is the all-zero state and every qubit is measured in the computational basis at the end.
The main theorem states that when the depth exceeds a critical value dcrit = O(p⁻¹ log p⁻¹) (with dimension-dependent constants), a deterministic classical algorithm computes the logarithm of every marginal probability of the output distribution to additive error ε in time polynomial in n/ε. Through a standard reduction, this yields a sampler whose output probabilities are each within a multiplicative (1 ± ε) factor of the true ones, which also implies closeness in total variation distance.
The relative-error guarantee matters. Relative-error sampling is the task whose classical hardness is known under the assumption that the polynomial hierarchy does not collapse. The authors point out that prior work shows relative-error sampling remains hard for noisy geometrically local circuits below a depth of order p⁻¹. Their easiness threshold of order p⁻¹ log p⁻¹ is therefore tight up to a logarithmic factor for this task.
The key idea: entropy piles up locally
The physical intuition is a volume-versus-boundary argument. In every layer, noise injects entropy into a region in proportion to its volume, roughly p per qubit. Local gates can only move that entropy out through the region’s boundary, which grows more slowly than the volume. So entropy accumulates locally, and after enough layers every region looks like a high-temperature system. High-temperature systems are typically easy to simulate classically, and the paper turns this heuristic into a proof.
The authors stress that geometric locality is essential. With all-to-all connectivity, a circuit can shuttle noise away from a protected subsystem faster than it accumulates, which is why the earlier, general results needed depth growing with n.
How the algorithm works
Coarse-graining. The lattice is divided into blocks of side length 2d. This size guarantees that any two non-adjacent blocks have disjoint backward light cones, so observables on them evolve independently in the Heisenberg picture.
Polymer model. Each marginal probability is expanded in Pauli Z operators, and the terms are grouped by which connected clusters of blocks they touch. The authors show that the marginal (up to a known factor) is exactly the partition function of an abstract polymer model from statistical mechanics, where polymers are connected sets of blocks and two polymers interact only if they touch.
Cluster expansion. The logarithm of such a partition function can be written as a sum over clusters of polymers. This expansion converges when polymer weights decay exponentially with size, and truncating it to clusters spanning O(log n) blocks gives an additive approximation of the log-marginal.
Weight decay from noise. The core technical step proves that a polymer’s weight shrinks exponentially with the number of blocks it covers once d exceeds the threshold. The proof chains hypercontractivity of the depolarizing channel with an ℓ2-norm contraction bound, using locality to collect an independent decay factor from each block.
Computing the terms. Small polymer weights can be computed by brute force on a portion of the circuit. To keep the runtime polynomial even when d grows with n, an appendix replaces brute force with truncated Pauli-path enumeration combined with tensor networks.
Why it matters
The result sharpens a question the authors put directly: when do quantum advantages break down if devices are scaled in size and runtime without also scaling non-unital or non-local resources? Fault-tolerance schemes rely on non-unital operations such as mid-circuit measurement with feedback and qubit reset. The paper gives a rigorous reason to believe that, without them, a local noisy device cannot sustain computations whose depth scales with system size. The authors also note that their bounds may apply to future fault-tolerant devices that run logical unitary gates with depolarizing-like logical noise and some form of geometric locality.
Methodologically, the paper connects two toolkits that are usually used separately: Pauli-path methods from circuit simulation and cluster expansions from rigorous statistical mechanics. The authors suggest hypercontractivity may find broader use in classical simulation.
Technical perspective (interpretation)
The following is my reading, not a claim made in the paper. The result is asymptotic, and its constants are large. The explicit sufficient condition in the paper’s weight-decay lemma includes a term proportional to 3ᴰ/p. By my rough arithmetic, plugging in p = 10⁻³ and D = 2 gives a threshold on the order of 10⁵ layers. The polynomial runtime also has a degree that grows with the inverse noise rate, roughly like p⁻⁽ᴰ⁺¹⁾ in one of the two bounds. So the theorem does not directly threaten current advantage experiments. It instead marks a structural boundary: noisy, local, unital computation has an intrinsic depth ceiling set by the noise rate, and only non-unital resources such as reset and measurement lift it.
It is also worth noting the paper’s AI-usage acknowledgement: the authors state that generative AI tools were used to obtain specific steps of the proof, namely the weight-decay argument and the tensor-network steps, while the main idea and technique were developed by the authors. Readers checking the proof may want to look closely at those sections.
Limitations and open questions
Noise model. The theorem covers single-qubit depolarizing noise applied after every layer, with unital gates. Non-unital noise, such as amplitude damping, is not covered; the authors suggest the expansion might be developed around other fixed points.
Geometric locality is required. Constant-depth hardness for noisy circuits with all-to-all connectivity remains open.
Additive-error hardness is open. The tightness statement concerns relative-error sampling. Whether noisy local circuits at constant depth can be hard to sample to small total variation distance, under standard average-case conjectures, is left open.
Random circuits. The techniques are worst-case. Extending them to prove simulability of noisy random circuits at all depths, as some numerical work suggests, would require exploiting disorder.
A conjectured picture. The authors suspect the output state of a noisy local circuit is approximately a thermal state of a local Hamiltonian whose temperature grows with d and p, which would give a more direct proof.
Status. This is a v1 preprint and has not yet been peer reviewed. It is a theory paper with no code or data release.
Paper information
Title: A polynomial-time classical sampler for noisy quantum circuits from statistical mechanics
Authors: Jon Nelson, Joel Rajakumar, Chao Yin, Yifan F. Zhang, Michael J. Gullans (Nelson and Rajakumar contributed equally)
Affiliations listed: University of Maryland, College Park; University of California, Los Angeles; QuEra Computing Inc.; Princeton University; Stanford University
arXiv: 2610.00548v1 [quant-ph], submitted 30 September 2026
Primary sources
Abstract page: arxiv.org/abs/2610.00548
Full text (HTML): arxiv.org/html/2610.00548v1