PaperlayerView exact revision on arXiv

Source-linked AI summary

Random quantum circuits transform local noise into global white noise

Alexander M. Dalzell, Nicholas Hunter-Jones, Fernando G. S. L. Brandão

arXiv:2111.14907v1quant-ph

TL;DR

The paper asks whether low-fidelity random quantum computations remain meaningfully related to their ideal outputs despite frequent local errors. It analyzes noisy random circuits through stochastic processes governing second moments and proves that sufficiently weak incoherent noise is well approximated by global white noise. This yields a controlled approximation regime that supports signal recovery and complexity-theoretic applications.

  • Problem

    Low-fidelity random quantum circuits experience frequent errors, raising whether their output distributions retain a useful, theoretically defensible relation to ideal computations.

  • Method

    The authors map second-moment quantities of random quantum circuits to stochastic processes and derive bounds for local unital noise.

  • Results

    For Pauli noise, the white-noise approximation has small error when ϵ^2s ≪ 1, s ≥ Ω(nlog(n)), and ϵ ≪ 1/(nlog(n)).

  • Takeaways & Limitations

    Local errors can be treated as scrambled white noise in typical random circuits, enabling recovery of noiseless computational signal by repetition and supporting low-fidelity sampling arguments.

  • Takeaways & Limitations

    The analysis assumes sufficiently weak noise and has scope boundaries for errors occurring before scrambling, with the authors noting possible threshold-bound behavior and non-generic circuits that do not scramble errors.

Abstract

from arXiv · show

We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. We show that, for local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_{\text{noisy}}$ of a generic noisy circuit instance and the output distribution $p_{\text{ideal}}$ of the corresponding noiseless instance shrink exponentially with the expected number of gate-level errors, as $F=\text{exp}(-2s\epsilon \pm O(s\epsilon^2))$, where $\epsilon$ is the probability of error per circuit location and $s$ is the number of two-qubit gates. Furthermore, if the noise is incoherent, the output distribution approaches the uniform distribution $p_{\text{unif}}$ at precisely the same rate and can be approximated as $p_{\text{noisy}} \approx Fp_{\text{ideal}} + (1-F)p_{\text{unif}}$, that is, local errors are scrambled by the random quantum circuit and contribute only white noise (uniform output). Importantly, we upper bound the total variation error (averaged over random circuit instance) in this approximation as $O(F\epsilon \sqrt{s})$, so the "white-noise approximation" is meaningful when $\epsilon \sqrt{s} \ll 1$, a quadratically weaker condition than the $\epsilon s\ll 1$ requirement to maintain high fidelity. The bound applies when the circuit size satisfies $s \geq \Omega(n\log(n))$ and the inverse error rate satisfies $\epsilon^{-1} \geq \tilde{\Omega}(n)$. The white-noise approximation is useful for salvaging the signal from a noisy quantum computation; it was an underlying assumption in complexity-theoretic arguments that low-fidelity random quantum circuits cannot be efficiently sampled classically. Our method is based on a map from second-moment quantities in random quantum circuits to expectation values of certain stochastic processes for which we compute upper and lower bounds.

1 Introduction

The paper studies whether local errors in low-fidelity random quantum circuits can be treated as white noise, preserving useful computational signal despite frequent errors. It proves rigorous approximation bounds and identifies conditions under which the approximation supports sampling and benchmarking applications.

  • Local errors in typical random circuits are quickly scrambled and can be treated as white noise, allowing the noiseless signal to be extracted by repetition despite a large chance of errors.The paper frames this as a precise result for NISQ devices performing random computations.
  • The model targets low-fidelity experiments where maintaining an errorless computation is impractical because realistic devices have substantially higher error rates than high-fidelity operation requires.Experiments on 53–60 qubits reported fidelities from approximately 0.002 to 0.0004.
  • For Pauli noise, the white-noise approximation has small error when ϵ^2s ≪ 1, s ≥ Ω(nlog(n)), and ϵ ≪ 1/(nlog(n)).The condition ϵ^2s ≪ 1 is quadratically weaker than the ϵs ≪ 1 requirement for high fidelity.
  • The approximation is idealized: it focuses on local unital noise, while realistic readout bias and other non-unital effects may require extensions.The authors note that mid-circuit non-unital errors would likely complicate their method.
  • The work provides theoretical support for low-fidelity quantum computational supremacy arguments and for using linear cross-entropy to benchmark noisy random-circuit experiments [5] [6].It also relates approximate sampling from the white-noise distribution to sampling from the ideal output distribution within total variation distance.

2 A model of noisy random quantum circuits

The paper models random circuits with local single-qudit noise inserted after two-qudit gates and studies their ideal, noisy, and white-noise output distributions. The analysis uses channel infidelity and unitarity to characterize noise and applies to specified random-circuit architectures and broader exact 2-design gate sets.

  • 2.1 Local noise model: The framework covers 1D periodic and complete-graph architectures, with anti-concentration established when s ≥ Ω(nlog(n)).Extension to D-dimensional architectures depends on a conjectured anti-concentration result from Ref. [8].
  • 2.2 Output distributions: For each random circuit instance, the ideal and noisy output distributions are compared with a white-noise mixture of the ideal distribution and the uniform distribution.The mixture parameter F is treated as free and selected to minimize the total variation distance.
  • 2.1 Local noise model: Each two-qudit gate is followed by independent single-qudit unital noise channels on the involved qudits, while single-qudit gates and measurements remain noiseless.The channels are assumed identical for simplicity, although the authors expect the conclusions to extend to location-dependent noise strengths.
  • 2.1 Local noise model: The study considers depolarizing, dephasing, and coherent rotation channels, characterized by average infidelity and unitarity.Unitarity measures the expected purity of outputs for random pure inputs, scaled between 0 and 1.
  • 2.2 Output distributions: The analysis tracks randomness from Haar-random noiseless circuits separately from randomness introduced by the noise channels.For depolarizing noise, the noisy state is mixed even after fixing the circuit instance.
  • 2.3 Gate sets: Because the analysis uses second moments, it directly applies to exact unitary 2-design gate distributions, including random Clifford circuits.The authors connect this generality to scrambling-depth behavior for universal gate sets.

3 Overview of contributions

The paper proves that weak local noise in sufficiently large random quantum circuits rapidly loses structure, while incoherent noise preserves an ideal signal mixed with uniform noise. The resulting white-noise approximation is substantially more accurate than worst-case error accumulation under stated architectural and noise-strength conditions.

  • 3 Overview of contributions: The results are established for 1D periodic and complete-graph architectures, with broader spatial architectures requiring an anti-concentration conjecture or yielding weaker bounds.The stated regime assumes anti-concentration around Θ(nlog(n)); the general architecture parameter s_AC is conjectured to have that scaling but currently has an O(n^2) upper bound.
  • 3.1 Fidelity decay: Theorem 1 gives exponential fidelity decay with the expected number of errors, while requiring anti-concentration and sufficiently weak noise.The relevant regime includes circuit size at least Ω(nlog(n)) and noise strength small enough that correction terms are negligible.
  • 3.2 Convergence to uniform: Theorem 2 bounds distance to uniform by a quantity that decays exponentially in (1−u)(1−q^-2)s under weak-noise conditions.The bound applies to the same 1D and complete-graph architectures and requires anti-concentration together with constraints on 1−u.
  • 3.2 Convergence to uniform: For depolarizing noise, convergence of p_noisy to uniform occurs at rate e^-2sϵ, matching the fidelity-decay rate; coherent rotations need not converge to uniform.The distinction follows from unitarity: depolarizing noise has decreasing unitarity, whereas rotation noise has u = 1 and preserves pure states.
  • 3.3 Distance to white-noise distribution: Theorem 3 shows that, for sufficiently weak noise in 1D or complete-graph random circuits, p_noisy is close to a white-noise mixture p_wn when its error bound is below the fidelity.The mixture uses F chosen as the expected fidelity, and the result bounds expected total variation distance over random circuits.
  • 3.3 Distance to white-noise distribution: For incoherent noise, the signal error after renormalization grows as O(D√s), quadratically slower than the worst-case O(Ds) bound for arbitrary circuits and channels.Depolarizing and dephasing noise have cancellation in δ at leading order, whereas coherent rotations make the white-noise approximation useful only near high fidelity.

4 Related work and implications

The paper connects white-noise behavior in noisy random circuits to benchmarking, classical-hardness arguments, and recovery of ideal-circuit signals. It derives fidelity-decay results, sampling requirements, and scope conditions for these implications.

  • 4.1.1 Linear cross-entropy benchmarking: e^-2ϵs bounds the expected fidelity decay under the local noise model, enabling inference of ϵ from measured fidelity and circuit size.The result requires ϵ ≪ 1/(n log(n)) and ϵ^2s ≪ 1, with matching upper and lower bounds.
  • 4.1.1 Linear cross-entropy benchmarking: The linear cross-entropy benchmark provides an empirical measure of circuit fidelity and estimates how much ideal-computation signal survives noise.The inferred error rate can be compared with independently measured component noise to verify device behavior.
  • 4.1.2 Classical hardness of sampling from the noisy output distribution: White-noise random circuit sampling requires 1/2∥p_noisy − p_wn∥_1 ≤ ηF, and the paper shows local noise can satisfy this task when sufficiently weak relative to the qubit count.This gives experimenters a way to support the white-noise condition when they trust the local error model, despite exponential sample requirements for direct verification.
  • 4.1.2 Classical hardness of sampling from the noisy output distribution: Inverse-polynomial fidelity can coexist with white-noise behavior when ϵ = Θ(1/n) and s = Θ(n log(n)), whereas deeper circuits make fidelity exponentially small.The formal connection to standard complexity-theoretic claims becomes more difficult in the exponentially small-fidelity regime.
  • 4.1.2 Classical hardness of sampling from the noisy output distribution: Approximate sampling from p_wn is essentially as hard as approximate sampling from p_ideal, with classical cost differing by at most a linear factor of F.This strengthens the theoretical case that noisy random-circuit sampling can retain classical computational hardness.
  • 4.3 Signal extraction in noisy experiments: White-noise behavior permits ideal-circuit signal extraction by repetition, but estimating a mean to distinguish it from zero requires Ω(1/F^2) samples.The procedure assumes the uniform contribution is understood and generally requires knowing F.

5 Summary of method and intuition

The paper explains white-noise behavior by expanding noisy outputs over Pauli error patterns and analyzing associated stochastic processes. Random circuits scramble local errors, while anti-concentration and error-rate conditions control the approximation error.

  • Conditions: The analysis additionally requires anti-concentration after s ≥ Ω(nlog(n)) gates and εnlog(n) ≪ 1, although the latter condition may be relaxable toward ε^-1 ≥ n/c.The restriction keeps errors from occurring before sufficient scrambling or near circuit boundaries, while the authors identify O(1/n) as a fundamental scaling barrier.
  • Error scrambling: Random circuits scramble local Pauli errors into operators with support over many qubits, making distinct error patterns generally behave as weakly correlated effective noises.The analysis commutes errors toward the circuit output, where later random gates transform local operators into global operators O_E.
  • Error-pattern expansion: The noisy output is expanded as a mixture over Pauli error patterns, with pattern probabilities determined by their number of non-identity errors; the zero-error term equals the ideal output.The resulting measurement distribution is obtained from p_noisy(x)=⟨x|ρ_noisy|x⟩, while the remaining mixture defines the error contribution.
  • White-noise error bound: Assuming distinct error-pattern probabilities are approximately independent and anti-concentrated, each output deviation is O(F2^-nε√s), yielding a total variation error much smaller than F when ε^2s ≪ 1.Without anti-concentration, the contribution of each term would be larger, so anti-concentration is needed for the bound.
  • White-noise error bound: The independence heuristic can fail when different error patterns produce the same effective operator, but random circuits make such collisions unlikely for most error-pattern pairs.The rigorous proof is presented as a justification of this scrambling-based intuition.
  • Stochastic-process intuition: In the toy stochastic process, probability mass relaxes toward fixed points I_n and S_n; the fraction remaining at S_n after noise acts equals the fidelity decay.The quantity F̄=(Z1−1)/(Z0−1) measures the surviving S_n-destined mass, connecting stochastic-process leakage to fidelity.

6 Numerical estimates of error in white-noise approximation

Numerical analysis of complete-graph circuits finds that the white-noise approximation improves after initial scrambling, but realistic experimental parameters remain inconclusive and the bound requires sufficiently low error rates.

  • 6.2 Numerical bound for realistic circuit parameters: 2ε√s/3 bounds the relative approximation error at large circuit sizes, indicating an O(ε√s) scaling with a prefactor below 1 for depolarizing noise.The bound initially spikes, then decreases as anti-concentration catches up with fidelity decay.
  • 6.2 Numerical bound for realistic circuit parameters: The O(ε√s) regime generally begins after Θ(nlog(n)) + Θ(n) gates, combining initial anti-concentration with the time needed to overcome fidelity decay.The second contribution grows with the error rate because fidelity decays more rapidly.
  • 6.2 Numerical bound for realistic circuit parameters: Google’s 430-gate and USTC’s 594-gate circuit sizes lie where the relative bound is decreasing, but the bound is close to 1 for Google and above 1 for USTC.These upper bounds alone cannot establish whether the white-noise approximation actually holds.
  • 6.2 Numerical bound for realistic circuit parameters: The numerical conclusions are limited by an unproven tightness of the bound, complete-graph rather than experimental 2D architecture, omitted readout errors, and idealized depolarizing noise.The authors therefore do not claim to validate specific supremacy experiments.
  • 6.3 Threshold error rate for good white-noise bound: For each n, error rates below a threshold yield O(Fε√s) bounds at large s, whereas rates above it produce empirically O(Fe^Θ(s)) bounds.Because only an upper bound is available, the above-threshold behavior is not known to equal the actual approximation error.
  • 6.3 Threshold error rate for good white-noise bound: The observed threshold is roughly ε = 0.3/n, decreasing from about 0.0057 at n = 53 to 0.0014 at n = 212.The threshold may be larger in architectures with faster anti-concentration.

7 Outlook

The paper concludes that weak incoherent local noise in typical random circuits is scrambled into global white noise, preserving an ideal-distribution signal despite low fidelity. This supports theoretical analyses of noisy sampling while limiting the claim to suitable noise models and generic scrambling circuits.

  • 7 Outlook: Random circuits drive noisy outputs toward uniformity while retaining a residual component aligned with the ideal distribution, at a decay rate like e^-2εs.This white-noise behavior had been conjectured and used in quantum computational supremacy arguments but lacked rigorous analytical study.
  • 7 Outlook: The white-noise approximation is not generally good for coherent noise, and the technical results require incoherent noise below an n-dependent threshold.Thus the conclusion does not extend uniformly across local noise models.
  • 7 Outlook: The result strengthens complexity-theoretic arguments by showing that sampling from the white-noise distribution with fidelity F and error ηF is essentially as hard as sampling from the ideal distribution with O(η) error.The related ideal-distribution sampling problem has received substantial theoretical scrutiny, although formal hardness remains unresolved.
  • 7 Outlook: For some applications, noise rates need only decrease like 1/√s rather than 1/s if experiments are repeated enough to extract the signal from global white noise.This provides a broader potential utility for NISQ devices.
  • 7 Outlook: The phenomenon is expected for generic scrambling circuits but not necessarily for structured computations such as quantum error-correcting circuits designed to avoid scrambling errors.Whether chaotic Hamiltonian-simulation circuits show similar behavior remains an open question.

A Framework for noisy circuit analysis

The framework maps second-moment quantities of noisy random circuits to stochastic transformations on tensor products of normalized identity and swap operators. Noise modifies these trajectories through asymmetric S-to-I transitions, yielding weighted trajectory or Ising-like representations.

  • Initialization: The initial single-qudit Haar averaging assigns I and S in the starting configuration probabilities q/(q+1) and 1/(q+1).This initializes the stochastic trajectory used to express second-moment quantities.
  • Noiseless dynamics: Haar-averaged two-qudit gates leave equal configurations unchanged and map mixed I,S pairs to II or SS with probabilities q^2/(q^2+1) and 1/(q^2+1).These are the transition rules for the noiseless stochastic process.
  • Stochastic representation: Second-moment evolution is represented on configurations in {I,S}^n using trace-one operators I/q^2 and S/q.The averaged circuit maps linear combinations of these tensor products to other such combinations, with coefficients transforming stochastically.
  • Noise dynamics: For weak noise, r is near 0 and u near 1, producing small S-to-I leakage but no I-to-S leakage and therefore an asymmetry absent from the noiseless process.The averaged noise channel preserves the relevant operator space and acts stochastically on its coefficients.
  • Trajectory formulation: The noisy quantities Z1 and Z2 become expectations over modified stochastic trajectories, equivalently expressible as partition functions of an Ising-like model.Adjacent configuration variables interact when gates or noise locations couple them.

B.1 Definitions and main lemmas

The analysis assumes layered, regularly connected or complete-graph architectures and establishes lemmas under weak noise and anti-concentration conditions. Regular connectivity ensures interactions across bipartitions, while layering defines circuit depth and supports the bounds.

  • Definitions: Regular connectivity requires gates to couple across every bipartition at least once within O(n) time steps, preventing circuit decomposition that would hinder scrambling.The proofs use h-regular connectivity with constant h=O(1).
  • Definitions: Layered architectures arrange gates into non-overlapping layers of n/2 gates, giving depth d=2s/n and anti-concentration depth dAC=2sAC/n.The analysis generally takes s to be a multiple of n/2.
  • Scope: The upper bound in the lemma estimates holds generally for all σ, although the stated weak-noise regime supplies the sharper controlled setting.The architecture-dependent constants depend on q and, for regularly connected circuits, h.
  • Main lemmas: For regularly connected layered architectures, Lemma 1 provides bounds when σ≤c5/n after anti-concentration depth dAC, with constants independent of n and σ.The upper-bound proof absorbs an O(nσ) contribution because dAC=Ω(log(n)).
  • Main lemmas: For complete-graph architectures, Lemma 2 applies for σ≤c′5/n and any circuit size, with anti-concentration size sAC=Θ(nlog(n)).Its bound contains terms scaling with s, sAC, and nσ log(1/(nσ)).

B.2.1 Proof of Theorem 1: fidelity decay

Theorem 1 bounds fidelity decay for random circuits with weak local noise on complete-graph or regularly connected layered architectures. The result connects the fidelity expression to the stochastic-process bounds through average infidelity.

  • Theorem 1: For complete-graph or regularly connected layered circuits, Theorem 1 bounds the fidelity quantity F̄ when average infidelity r≤c/n and n≥n0.The circuit has n qudits, local dimension q, s gates, and anti-concentration size sAC.
  • Proof strategy: The theorem follows by identifying F̄=(Z1−1)/(Z0−1)=(Zσ−1)/(Z0−1) with σ=rq/(q−1), then applying the architecture-specific lemmas.The relation nd=2s converts depth-dependent bounds into circuit-size statements.

B.2.2 Proof of Theorem 2: convergence to the uniform distribution

Theorem 2 bounds convergence toward the uniform output distribution for weakly non-unitary noise on complete-graph or regularly connected layered circuits. Its proof uses the stochastic-process bounds with the noise parameter set by non-unitarity.

  • Theorem 2: For the stated circuit architectures, Theorem 2 bounds convergence to punif when v=1−u≤c/n and n≥n0.Here u is the local noise unitarity and punif is the uniform distribution.
  • Proof strategy: The proof applies the 1-norm to 2-norm and Jensen inequalities, then invokes the upper bounds from the architecture-specific lemmas with σ=v.As in Theorem 1, nd=2s converts depth dependence into circuit-size dependence.

B.2.3 Proof of Theorem 3: approximation by white noise

The proof couples noiseless and noisy stochastic processes to control how local noise alters the output distribution. It combines this coupling with bounds on the resulting stochastic dynamics under weak noise.

  • Theorem 3: Theorem 3 bounds white-noise approximation error for random circuits when noise parameters and system size satisfy explicit weak-noise conditions.The theorem assumes v ≤ c1/n, r ≤ c2/n, and n ≥ n0, with F chosen as the optimizing value F̄.
  • Optimization of F: The proof minimizes the distance bound by choosing F̄ = (Z1 − 1)/(Z0 − 1), then bounds the resulting expression using stochastic-process quantities Z0, Z1, and Z2.After anti-concentration, Z0 − 1 rapidly approaches q^n − 1, enabling the subsequent estimates.
  • Coupled stochastic processes: The argument compares two correlated copies of the random walk, applying noise only to the noisy copy to isolate the noise-induced deviation.The coupled transition matrix preserves the appropriate marginals while the auxiliary W system records disagreements between copies.
  • Coupled stochastic processes: The accessible subspace is preserved because the noise can transition S to I but not I to S, allowing the coupled evolution to be analyzed within a restricted state space.The construction uses projectors on paired X and Y bits and excludes the inaccessible fixed point |In⟩⊗|Sn⟩.
  • Coupled stochastic processes: The W system captures the difference between noiseless and noisy trajectories and begins at the Sn fixed point, avoiding the initial convergence problem of directly analyzing the noisy copy.This choice is the main reason the auxiliary W system is introduced.

B.8.6 Proof of Lemma 8

The proof of Lemma 8 analyzes how coupled gates change a configuration’s Hamming weight and shows that repeated interactions reduce a suitable discrepancy quantity.

  • B.8.6 Proof of Lemma 8: The resulting bounds establish exponentially decaying contributions under the stated parameter conditions, completing the lemma.The proof combines the contraction estimates with bounds on the relevant sums and auxiliary quantities.
  • B.8.6 Proof of Lemma 8: Each coupling of disagreeing bits decreases the inner product with (⟨q| − ⟨1|)Δ by the constant factor 2q/(q^2 + 1).The two possible Hamming-weight changes have probabilities 1/(q^2 + 1) and q^2/(q^2 + 1), yielding the contraction bound.
  • B.8.6 Proof of Lemma 8: For regularly connected architectures, within a window of hn steps there is at least a 1/2 chance of coupling a disagreeing pair unless the configuration is already at a fixed point.Such a coupling triggers the constant-factor decrease in the discrepancy quantity.
  • B.8.6 Proof of Lemma 8: Noise acts only on the noisy copy and can flip a 1 to 0, decreasing the disagreement configuration’s Hamming weight while modifying the same discrepancy measure.This behavior is incorporated into the contraction analysis alongside noiseless gate transitions.

B.8.8 Proof of Lemma 10

The proof of Lemma 10 bounds the persistence of S-destined probability mass by tracking noise-induced transitions and the subsequent noiseless return dynamics.

  • B.8.8 Proof of Lemma 10: After noise redirects mass to the I-destined sector, noiseless dynamics rapidly move it downward in Hamming weight.The proof separates the evolution according to when the mass is redirected and how far it lies from the fixed point.
  • B.8.8 Proof of Lemma 10: The lemma follows by combining the separate bounds for redirected mass and the subsequent stochastic evolution.The argument uses the previously established equations for the two time regimes.
  • B.8.8 Proof of Lemma 10: Under σ ≤ χ7/n and sufficiently large n, the relevant contributions decay exponentially with time.The proof obtains this by combining bounds for different time ranges and requiring χ5/n to exceed 2log(1/(1 − σ)).

B.8.9 Proof of Lemma 11

The proof of Lemma 11 controls S-destined mass across layers by splitting the process according to the noisy copy’s Hamming weight and applying bounds for early and late evolution.

  • B.8.9 Proof of Lemma 11: The lower bound is obtained by recursively applying the transition estimate across increasing depth.The proof also establishes the corresponding upper bound by combining the Hamming-weight decomposition with the earlier estimates.
  • B.8.9 Proof of Lemma 11: The proof divides the noisy-copy mass according to whether the noiseless copy has reached the Sn fixed point and according to the noisy copy’s Hamming weight.This decomposition provides the basis for separate upper bounds on the relevant contributions.
  • B.8.9 Proof of Lemma 11: The proof combines bounds for configurations with different Hamming weights and uses Lemma 10 whenever w < n.The resulting estimates inherit the requirement σ ≤ χ7/n and sufficiently large n.
  • B.8.9 Proof of Lemma 11: Layered circuit structure limits how quickly the number of I-assigned bits can grow, constraining which earlier configurations can reach a given Hamming weight.Because each qudit participates in at most one gate per layer, the number of I bits can at most double over the specified interval.
  • B.8.9 Proof of Lemma 11: Early evolution before anti-concentration is handled separately using the anti-concentration depth dAC = 2sAC/n.The recursion incorporates exponential decay estimates and conditions ensuring terms remain controlled for σ = O(1/n).

B.8.11 Proof of Lemma 13

The proof analyzes how error configurations evolve under the complete-graph architecture and establishes a lower bound through recursive stochastic-process estimates.

  • B.8.11 Proof of Lemma 13: The quantity Jw increases with w and is bounded above by Jn, while Gw is shown to satisfy Gw ≥ Jn for all relevant n and w.The lower bound includes the boundary case w = n by the definition Gw = Jn.
  • B.8.11 Proof of Lemma 13: The proof tracks configurations by Hamming weight, distinguishing whether each acted-on qudit is assigned S or I.The quantities φSS,w, φIS,w, and φII,w describe the probabilities of the three possible pair assignments at weight w.
  • B.8.11 Proof of Lemma 13: Errors change the Hamming weight by flipping I to S or S to I, with transition probabilities determined by the pair configuration.When one qudit is I and the other S, the two possible flips move the weight by one.
  • B.8.11 Proof of Lemma 13: Recursive application of the derived inequalities proves the lower bound, after separately controlling the initial and later portions of the gate sequence.The argument uses a naive recursion for the first roughly sAC gates and collects the resulting O(nσ) contribution with O(sACσ) because sAC ≥ Ω(nlog(n)).
  • B.8.11 Proof of Lemma 13: The upper-bound portion requires σ ≤ χ7/n and n ≥ n0, so these assumptions are inherited by the resulting estimate.The proof splits the initial weight according to whether the noiseless copy has reached the Sn fixed point and applies Lemma 10 to the remaining term.

C Complexity theory of the white-noise sampling problem

This section formalizes the complexity-theoretic status of white-noise random-circuit sampling and relates it to approximate noiseless sampling under anti-concentration.

  • Limitations: The hardness claims remain conjectural, and existing evidence concerns strong simulation at very small error tolerance rather than sampling with O(1) total variation error.The paper notes that these results are multiple steps away from proving the sampling conjecture.
  • Motivation: The practical challenge is that noisy devices cannot sample exactly from pideal, while achieving small total variation distance from ideal may require exceedingly small error rates.Sampling close to pwn may therefore be more tractable in the near term than sampling close to pideal.
  • Theorem 4: Theorem 4 shows that approximate white-noise sampling and approximate random-circuit sampling are essentially equivalent up to a linear factor in fidelity F for anti-concentrated architectures.The reduction uses approximate rejection sampling and Stockmeyer approximate counting with an NP oracle.
  • Corollary 1: Corollary 1 states that, for anti-concentrated architectures, Conjecture 1 is true if and only if Conjecture 2 is true.Thus the conjectured hardness of approximate RCS and white-noise RCS are equivalent within the stated complexity framework.
  • Corollary 1: The linear F dependence is optimal for the reduction because white-noise sampling can be simulated by querying an ideal sampler only an F fraction of the time.Theorem 4 also gives the matching upper bound on the classical-easiness factor.
  • Theorem 4: The reduction runs in expected time F^-1 poly(n) and produces approximate-RCS parameters ε′ = 4ε + 1/poly(n) and δ′ = δ + 1/poly(n).The factor of 4 is noted as potentially improvable.
Loading 2111.14907v1…