Source-linked AI summary
Tight bounds on the convergence of noisy random circuits to the uniform distribution
Abhinav Deshpande, Pradeep Niroula, Oles Shtanko, Alexey V. Gorshkov, Bill Fefferman, Michael J. Gullans
TL;DR
The paper asks how noise changes random-circuit output distributions and the hardness arguments used for quantum computational advantage. It derives tight depth-dependent bounds, studies anticoncentration, and shows that some noise-agnostic hardness techniques remain possible in intermediate depth regimes.
Problem
Noise and limited system size complicate whether quantum-advantage experiments are classically simulable, while the convergence and anticoncentration behavior of noisy random circuits remains important for sampling hardness.
Method
The authors analyze Haar-random two-qubit circuits with local Pauli noise and computational-basis measurements, proving upper and lower bounds on expected total variation distance and studying anticoncentration.
Results
The bounds are tight in circuit-depth scaling, shallow circuits severely lack anticoncentration, and higher-depth noisy circuits anticoncentrate at least as fast as noiseless circuits.
Takeaways & Limitations
Noise-agnostic hardness techniques are not ruled out for d=Ω(log n) and d=O(n), although shallow and sufficiently deep regimes remain bounded by easy-output behavior.
Abstract
from arXiv · showhide
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 was thought prior to this work.
I. INTRODUCTION
The paper studies how noisy random-circuit output distributions approach uniformity and uses tight depth-dependent bounds to assess anticoncentration and quantum-advantage hardness barriers.
- I. INTRODUCTION: The authors study random circuits with Haar-random two-qubit gates, local Pauli noise, and computational-basis measurements, focusing on total variation distance from uniformity.They frame this question as relevant to random circuit sampling, noisy-circuit benchmarking, and near-term algorithms.
- I. INTRODUCTION: The expected distance from uniformity has matching depth scaling: a lower bound exp[−O(d)] for local Pauli noise and an upper bound poly(n) exp[−Ω(d)] for heralded dephasing.These bounds are tight in their dependence on circuit depth because the exponent scales linearly with d.
- I. INTRODUCTION: At sublogarithmic depth, noisy and noiseless random circuits severely lack anticoncentration, while at higher depth noisy circuits anticoncentrate at least as fast as noiseless circuits.The results strengthen prior work by Dalzell et al. [26] and establish contrasting shallow- and deeper-depth behavior.
- 3. Consequences of our results on tightness of proof techniques: For sublogarithmic depth d=o(log n), most output probabilities are o(2^-n), so always outputting 0 approximates them within 2^-n with high probability.Consequently, hardness proofs targeting imprecision 2^-Θ(n) cannot work in this regime, extending the earlier d≤3 barrier of Napp et al. [37].
- 3. Consequences of our results on tightness of proof techniques: Theorem 1 rules out the hypothesized exp[−Θ(nd)] convergence for noisy circuits, leaving room for noise-agnostic hardness techniques when d=Ω(log n) and d=O(n).In this regime, hardness for noisy and noiseless circuits at imprecision 2−O(n) is not ruled out; Corollary 1 also shows that outputting 1/2^n fails with high probability for d≤c log n.
- 4. Surmounting barriers: Known hardness proofs perturb Θ(nd) gates, making their imprecision depend on nd rather than only n; the paper also identifies possible routes around both noise and depth barriers.The authors distinguish fixed-output algorithms from instance-dependent algorithms and leave open whether suitable techniques can rule out the latter.
B. Benchmarking noise using random circuits
Random circuit sampling is used for benchmarking noise and modeling near-term algorithms, but noise drives output distributions toward uniformity and can undermine information-based strategies. The paper establishes depth-tight decay bounds and shows that output-distribution postprocessing cannot avoid noise-induced trainability problems, while short depths retain information.
- B. Benchmarking noise using random circuits: Random circuit sampling supports quantum-advantage proposals and benchmarking because cross-entropy measures can predict fidelity, subject to exceptions.The usefulness of these proxies depends on how noisy output distributions approach uniformity.
- B. Benchmarking noise using random circuits: e^-c1ϵd ≤ EB[δ] ≤ Ke^-c2ϵd: in the natural constant-noise regime, the paper proves depth-tight bounds on distance from uniformity.The constants c1 and c2 differ, and matching them is identified as a future goal for sample-efficient fidelity benchmarking.
- C. Near-term algorithms: Theorem 2 implies that postprocessing the full output distribution cannot ameliorate noise-induced barren plateaus for random-circuit variational algorithms.The output distribution is information-theoretically close to uniform under the relevant noisy-circuit model.
- C. Near-term algorithms: At d = O(log n), Theorem 1 implies that noisy output distributions retain enough information for circuit trainability.This avoids the conclusion that constant-depth noisy circuits are necessarily untrainable, which would follow from an incorrect 2^-Θ(nd) convergence hypothesis.
- D. Monitored random circuits and entanglement phase transitions: Heralded dephasing models monitored random circuits, where a random fraction p of qubits is measured after each layer.These models exhibit entanglement and purity phase transitions as measurement strength crosses a critical point.
- III. PRIOR WORK: Earlier work showed exponential entropy growth or convergence bounds for several noise models, but dephasing remains difficult because computational-basis states are unaffected.For dephasing, arbitrary-circuit upper bounds cannot be obtained using the cited techniques, and Pauli twirling does not apply to this nonlinear quantity.
IV. DEFINITIONS
The paper defines noisy Haar-random circuits, local stochastic Pauli noise, parallel architectures, output-distribution distance, and anticoncentration for its analysis. It also distinguishes ordinary anticoncentration from a stronger collision-probability condition.
- IV. DEFINITIONS: A noisy Haar-random circuit applies noise channels to tensor products of two-qubit Haar-random gates.The circuit ensemble randomizes the unitary gates while the noise operations are treated separately.
- IV. DEFINITIONS: The analysis assumes local noise acting on at most k = Θ(1) qubits, with stochastic channels containing an identity Kraus operator and Pauli noise expressed probabilistically.The local Pauli-sector rate q^m_µi is defined as the marginal probability of applying Pauli µ at site i and depth m.
- IV. DEFINITIONS: A parallel architecture uses even n and applies a two-qubit gate to every qubit at each depth layer, with lightcones tracking causal influence.The grouping of qubits may change between layers, and lightcones have size at most 2^d.
- IV. DEFINITIONS: The output-distance measure is δ = ∥D − U∥TVD, comparing the noisy computational-basis output distribution D with the uniform distribution U.The random-circuit ensemble expectation is denoted E_B.
- IV. DEFINITIONS: Strong anticoncentration requires 2^n E_B[Z(U, E)] ≤ c, whereas the paper's weaker definition does not imply this condition.The stronger condition implies the weaker anticoncentration definition, but the converse does not hold.
A. Lower bound on the distance to the uniform distribution
The section proves lower bounds on expected total variation distance from uniform for noisy Haar-random circuits, with exponential dependence on depth and applicability to typical circuits at sufficiently low depths.
- A. Lower bound on the distance to the uniform distribution: E_B[δ] is lower bounded by an exponential in circuit depth for Haar-random circuits with local Pauli noise.The bound applies on any parallel architecture under a uniform upper bound on local noise rates.
- A. Lower bound on the distance to the uniform distribution: The proof lower-bounds total variation distance by considering rare Clifford circuits that preserve a single qubit's computational-basis information through all layers.For these circuits, only repeated single-qubit noise affects that qubit, producing a nonuniform output contribution.
- A. Lower bound on the distance to the uniform distribution: Perfect depolarizing noise makes the bound trivial because it immediately produces the uniform distribution, while the noiseless Porter–Thomas regime can make the bound underestimate the true distance.The lower bound is therefore not uniformly tight in noise strength or in the noiseless large-depth regime.
- A. Lower bound on the distance to the uniform distribution: The lower bound extends beyond Pauli noise whenever repeated application of the single-qubit noise channel preserves a deviation from one-half of at least exp[−ad].Under this condition, the proof changes the circuit-counting constant but retains exponential depth dependence.
- A. Lower bound on the distance to the uniform distribution: For depths below the Corollary 1 threshold, most circuits—not merely rare instances—have total variation distance at least e^(−cd).This typicality result rules out explaining the expectation lower bound solely through unusually nonuniform rare circuits.
B. Upper bound on the distance to uniform
The section derives an architecture-independent upper bound on average total variation distance for heralded dephasing noise, showing exponential decay with depth in the relevant model.
- B. Upper bound on the distance to uniform: Heralding makes the noise locations known but not the measurement outcomes, so the locations contribute additional randomness and differ from uniformly dephasing every site.The model interpolates to local dephasing as p approaches one and to unrecorded Z-basis measurements as q approaches one-half.
- B. Upper bound on the distance to uniform: Theorem 2 gives an architecture-independent upper bound on circuit-averaged total variation distance for heralded dephasing noise.The model randomly selects sites after each layer and applies local dephasing at selected sites.
- B. Upper bound on the distance to uniform: The proof converts total variation distance to entropy and collision-probability bounds using Pinsker's inequality and the second Rényi entropy.The resulting estimate controls variation distance through the output distribution's second moment.
- B. Upper bound on the distance to uniform: The second moment of total variation distance decays exponentially with depth, yielding an exponentially decaying average distance after optimizing the auxiliary threshold.The collision probability is bounded using a statistical-mechanics mapping for the heralded dephasing model.
C. No-go for anticoncentration at low depth
At sublogarithmic depth, noisy Haar-random circuits lack anticoncentration, and the same low-depth obstruction holds for noiseless circuits.
- C. No-go for anticoncentration at low depth: For sublogarithmic depth d=o(log n), noisy Haar-random circuits satisfy p_00...0=o(2^-n) with probability tending to one, indicating poor anticoncentration.The stated regime includes depths below a constant multiple of log n determined by the noise parameters.
- C. No-go for anticoncentration at low depth: The proof uses locality of lightcones and concentration of a lower bound on the logarithm of the all-zero output probability.A variance bound controls fluctuations around the mean and supports the high-probability conclusion.
- C. No-go for anticoncentration at low depth: The same no-anticoncentration conclusion applies to noiseless Haar-random circuits at sublogarithmic depth by setting the noise parameter b to zero.Thus, noise is not required for the low-depth obstruction established here.
- C. No-go for anticoncentration at low depth: The result closes a gap left by collision-probability analyses, which had established logarithmic-depth necessity for one anticoncentration criterion without excluding other definitions at sublogarithmic depth.The paper's anticoncentration definition is presented as more relevant to quantum computational advantage proofs.
D. Anticoncentration at large enough depth
At sufficiently large depth, Pauli noise does not prevent anticoncentration when the corresponding noiseless Haar-random circuit anticoncentrates.
- D. Anticoncentration at large enough depth: The collision probability is the second moment of the output probability and supplies the quantity used to establish anticoncentration in this section.The argument then applies a Paley–Zygmund bound to obtain a nonvanishing probability of sufficiently large output probabilities.
- D. Anticoncentration at large enough depth: Haar-random circuits with Pauli noise anticoncentrate at least as fast as their noiseless counterparts under the stated collision-probability condition.If 2^n E_B[Z(U,I)] is bounded by a constant, the noisy output is anticoncentrated.
- D. Anticoncentration at large enough depth: The proof compares noisy and noiseless collision probabilities by showing that adding Pauli noise decreases the collision probability for Clifford circuits.The two-design property transfers this comparison to the Haar-random circuit analysis.
- D. Anticoncentration at large enough depth: On reasonably well-connected architectures, noisy Haar-random circuits anticoncentrate after Θ(log n) depth because the noiseless collision-probability condition holds there.Theorem 3 simultaneously rules out anticoncentration at sublogarithmic depth for noisy circuits.
Appendix A: Proof of Lemma 2
Appendix A proves an upper bound on expected collision probability for noisy Haar-random circuits by reducing the analysis to noisy single-qubit channels and SWAP networks. The proof evaluates dephasing along qubit paths and averages over independent noise locations to establish Lemma 2.
- Lemma 2 gives an upper bound on expected collision probability for depth-d noisy Haar-random circuits with heralded dephasing.
- A single-qubit path with t_i dephasing events evolves through repeated averaged Haar-gate and dephasing composite channels.The heralded noise locations are modeled by independent Bernoulli variables, enabling pathwise averaging.
- Averaging each Bernoulli noise variable yields E[β^xij] = 1 − pγ, which is then inserted into the collision-probability bound.The proof uses independence of noise locations and exponential inequalities to obtain the final bound.
- The proof replaces the original ensemble with noisy single-qubit channels and SWAP gates without decreasing average collision probability.The replacement ensemble is constructed independently of fixed noise locations and may be completed with SWAP gates that preserve collision probability.
- Two-copy Haar averaging represents the state as a linear combination of tensor-product configurations built from identity and SWAP operators.This representation underlies the collision-probability calculation for random circuits.
Appendix B: Proof of Lemma 3
Appendix B proves the variance bound in Lemma 3 by expanding covariance terms and showing that almost all contributions vanish. The remaining terms imply σ^2 ≤ 2n.
- The proof applies a covariance bound to decompose the variance into terms that can be analyzed separately.
- The potentially nonzero remaining term also vanishes because the relevant three-copy Haar average is zero.
- Most covariance terms vanish unless the permutation conditions align, including σ(i) = j and related membership constraints.
- The variance in Eq. (B1) is at most 2n, establishing the stated bound σ^2 ≤ 2n.