We study the properties of output distributions of noisy random circuits.We obtain upper and lower bounds on the expected distance of the output distribution from the "useless" uniform distribution.These bounds are tight with respect to the dependence on circuit depth.Our proof techniques also allow us to make statements about the presence or absence of anticoncentration for both noisy and noiseless circuits.We uncover a number of interesting consequences for hardness proofs of sampling schemes that aim to show a quantum computational advantage over classical computation.Specifically, we discuss recent barrier results for depth-agnostic and/or noise-agnostic proof techniques.We show that in certain depth regimes, noise-agnostic proof techniques might still work in order to prove an often-conjectured claim in the literature on quantum computational advantage, contrary to what has been thought prior to this work.
In this work, drawing inspiration from the type of noise present in real hardware, we study the output distribution of random quantum circuits under practical non-unital noise sources with constant noise rates. We show that even in the presence of unital sources like the depolarizing channel, the distribution, under the combined noise channel, never resembles a maximally entropic distribution at any depth. To show this, we prove that the output distribution of such circuits never anticoncentrates $\unicode{x2014}$ meaning it is never too "flat" $\unicode{x2014}$ regardless of the depth of the circuit. This is in stark contrast to the behavior of noiseless random quantum circuits or those with only unital noise, both of which anticoncentrate at sufficiently large depths. As consequences, our results have interesting algorithmic implications on both the hardness and easiness of noisy random circuit sampling, since anticoncentration is a critical property exploited by both state-of-the-art classical hardness and easiness results.
Random circuit sampling (RCS) is a leading candidate for demonstrating quantum advantage, supported by strong complexity-theoretic evidence of hardness in the ideal setting and by rapid experimental progress to date. In practice, however, noise is unavoidable, and a central problem is to identify the noise-strength boundary between classically simulable and classically hard regimes. In this work, we establish an architecture-general hardness bound for this boundary for the standard local depolarizing noise of strength
γ. Assuming the standard average-case #P-hardness conjecture for ideal RCS, we show that, for any circuit architecture satisfying this conjecture, noisy RCS on the same architecture remains hard to simulate classically within any inverse-polynomial total variation distance whenever
γ=O(logn/(nd)) for
n-qubit circuits of depth
d, unless the polynomial hierarchy collapses. Crucially, noisy-RCS hardness follows without any additional conjectural or architecture-specific assumption beyond those already entering the ideal-RCS hardness framework. Our proof combines a low-degree polynomial extrapolation with a monotonicity reduction showing that efficient classical simulation at one depolarizing noise strength implies efficient simulation at every larger strength. Together, these ingredients transfer the standard ideal-RCS hardness conjecture to sampling hardness at a prespecified noise strength. Finally, combining the convergence-to-uniformity result of Dalzell et al. [Commun. Math. Phys. 405, 78 (2024)] with our monotonicity reduction yields efficient classical simulation for
γ=ω(logn/(nd)) on layered, regularly connected architectures. Thus, wherever the two architectural settings overlap, this identifies
γ=Θ(logn/(nd)) as the asymptotic complexity-transition scale.
In this work, drawing inspiration from the type of noise present in real hardware, we study the output distribution of random quantum circuits under practical nonunital noise sources with constant noise rates. We show that even in the presence of unital sources such as the depolarizing channel, the distribution, under the combined noise channel, never resembles a maximally entropic distribution at any depth. To show this, we prove that the output distribution of such circuits never anticoncentrates—meaning that it is never too “flat”—regardless of the depth of the circuit. This is in stark contrast to the behavior of noiseless random quantum circuits or those with only unital noise, both of which anticoncentrate at sufficiently large depths. As a consequence, our results shows that the complexity of random-circuit sampling under realistic noise is still an open question, since anticoncentration is a critical property exploited by both state-of-the-art classical hardness and easiness results. Published by the American Physical Society 2024
Quantum circuits with a constant rate of depolarizing noise per qubit per time step are known to converge to the uniform distribution at depth
ω(p−1logn), and hence become trivially classically simulable by uniform sampling. We show that under the physically natural constraint of geometric locality, noisy circuits become classically simulable at shallower depths by substantially more structured classical algorithms. We consider arbitrary geometrically local quantum circuits on
n qubits, initialized in an arbitrary product state, with nearest-neighbor gates in
O(1) spatial dimensions and interspersed depolarizing noise of any constant strength
p. Our first result is that when the depth exceeds a threshold
d∗=Θ(p−1logn), the output distribution can be approximately sampled in quasipolynomial time. This gives a worst-case simulability result for noisy geometrically local circuits, and matches in its
n-dependence the best previously known results for noisy random circuits. The proof is based on new information-theoretic bounds showing that in geometrically local noisy circuits, local regions lose correlations and independently converge to maximally mixed strictly before the entire system converges to the uniform distribution. We further prove structural results suggesting a sharper transition at depth
Θ~(p−1): after coarse-graining the lattice, Pauli weight supported on long connected paths can be truncated with exponentially small error. These results provide evidence for a percolation-like mechanism behind classical simulability at constant depth, and motivate our conjecture that all noisy geometrically local circuits admit quasipolynomial-time approximate sampling once circuit depth exceeds
Θ~(p−1).
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−1logp−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.