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

Technical Summary: Polynomial-Time Classical Sampling for Noisy Quantum Circuits

Problem Statement
The paper addresses the challenge of determining the limits of quantum advantage in the presence of noise. While ideal quantum computers can exponentially outperform classical ones, experimental devices are subject to noise, which typically degrades computational power. Existing classical simulation methods for general noisy circuits generally require the circuit depth to grow super-logarithmically with system size ($d \sim \omega(\log n)$) for noise to drive the global state to a trivial, uniform distribution. A critical open question remains: can noisy quantum circuits be classically simulated at depths that are independent of system size (constant depth), provided the noise strength is non-zero? Specifically, the authors investigate whether a "worst-case" noisy geometrically local quantum circuit becomes classically simulable before the output distribution converges to uniformity.

Methodology
The authors develop a novel classical sampling algorithm that combines techniques from statistical mechanics and quantum information theory. The core methodology involves three main steps:

1. Mapping to Polymer Models:
   The authors map the marginal probabilities of the noisy quantum circuit's output distribution to the partition function of an abstract polymer model in statistical mechanics.

   • They decompose the lattice into coarse-grained blocks of side length $2d$.
   • They define "polymers" as connected sets of these blocks.
   • The weight of a polymer is defined via the Heisenberg evolution of Pauli observables restricted to that polymer's support.
   • Due to the geometric locality of the circuit, non-adjacent blocks have disjoint backward light cones, allowing the partition function to be factorized into a sum over compatible (non-overlapping and non-adjacent) polymer configurations.

2. Truncated Cluster Expansion:
   To compute the partition function (and thus the log-marginal probabilities), the authors employ a cluster expansion. This technique expands the logarithm of the partition function as a sum over "clusters" of polymers.

   • The algorithm truncates this expansion, summing only over clusters supported on $O(\log n)$ blocks.
   • The accuracy of this approximation relies on the "weight decay" property: the contribution of a polymer must decay exponentially with its size (number of blocks).

3. Proof of Weight Decay via Hypercontractivity:
   The central technical contribution is proving that the polymer weights decay exponentially when the circuit depth $d$ exceeds a critical threshold independent of system size.

   • The authors utilize quantum hypercontractivity and $\ell_2$-norm contraction bounds for depolarizing channels.
   • They construct a path of norm conversions: starting from the $\ell_\infty$ norm, passing through $\ell_{1+(4d)^D}$ and $\ell_2$ norms, and finally returning to $\ell_1$.
   • By applying hypercontractivity to transition between norms and using the contractivity of the depolarizing channel (Fact 5.2), they demonstrate that the noise accumulates locally. Because the system is geometrically local, entropy introduced by noise (scaling with volume) cannot escape as fast as it is generated (scaling with boundary), leading to a local high-temperature phase where correlations decay exponentially.

Key Results
The paper establishes the following main theorem (informal):

• Theorem: For any geometrically local quantum circuit composed of unital operations with single-qubit depolarizing noise of strength $p$ applied after each layer, there exists a polynomial-time classical algorithm that can sample from the output distribution with inverse-polynomial total variation distance (and relative error for marginals) if the circuit depth $d$ satisfies:
  $$d > d_{crit} = O(p^{-1} \log p^{-1})$$
• Algorithmic Capability: The provided algorithm is a Fully Polynomial-Time Approximation Scheme (FPTAS) for arbitrary marginals of the output distribution. It achieves relative-error sampling, a task known to be classically hard for noiseless circuits and for noisy circuits below the $O(p^{-1})$ depth threshold.
• Complexity Regime: The result identifies a new regime in the complexity landscape of noisy circuits. While prior work showed hardness for depths up to $O(p^{-1})$ and simulability for depths scaling with $\log n$ (or $\omega(\log n)$), this work proves simulability at constant depth (independent of $n$) once the depth exceeds $O(p^{-1} \log p^{-1})$.

Significance and Claims
The authors frame their work as providing a more thorough reason to believe that non-unital or non-local resources (such as mid-circuit measurements with feedback or qubit reset) are fundamentally necessary to achieve computation depths that scale with system size.

• Quantum-to-Classical Transition: The paper interprets the result as a "quantum-to-classical transition" driven by the accumulation of heat (entropy) in open quantum systems. It posits that without a low-temperature bath to drain heat (i.e., without non-unital operations), the system naturally transitions to a classically simulable high-temperature phase after a critical depth.
• Tightness: The authors note that their bound is tight up to logarithmic factors, as relative-error sampling is proven hard for depths below $O(p^{-1})$.
• Generality: The result applies to arbitrary geometrically local circuits with unital operations and depolarizing noise, subsuming previous results that were limited to restricted gate sets or specific noise models.
• Philosophical Context: The work addresses the computational complexity of open quantum systems "on their own," suggesting that the natural dynamics of noisy many-body systems exhibit a transition to classicality that can be rigorously characterized using statistical mechanical tools.

The paper does not claim to simulate specific experimental devices or propose new hardware; rather, it provides a theoretical bound on the simulability of a broad class of noisy quantum dynamics, suggesting that the "quantum advantage" in such systems is fragile and limited to shallow depths unless specific non-unital error correction mechanisms are employed.