PaperlayerView exact revision on arXiv

Source-linked AI summary

A polynomial-time classical algorithm for noisy quantum circuits

Thomas Schuster, Chao Yin, Xun Gao, Norman Y. Yao

arXiv:2407.12768v2quant-phcs.CCcs.ITmath-phmath.ITmath.MPphysics.atom-ph

TL;DR

The paper asks how noise limits the classical-versus-quantum computational advantage of general circuits. It develops classical simulation algorithms that track low-weight Pauli information, and shows expectation values can be approximated on most inputs, with runtime depending on the noise model and observable.

  • Problem

    The computational power of general quantum circuits with low noise rates and no error correction is not well understood, despite the relevance of this intermediate regime to near-term devices.

    Source: §I · p. 1

  • Method

    The algorithms simulate Heisenberg evolution in the Pauli basis and truncate high-weight operators that are strongly affected by noise.

    Source: §I · p. 1

  • Results

    For most inputs from a broad class of ensembles, the algorithms approximate expectation values for any noisy circuit in polynomial or quasi-polynomial time, depending on the observable and noise model.

    Source: §I · p. 1

  • Takeaways & Limitations

    At constant noise rates, efficient error mitigation on most inputs is possible only for circuits that are classically simulable on most inputs.

    Source: §I · pp. 1–2

    The guarantee is over most input states from an allowed ensemble, rather than for every fixed input state.

    Source: §I · p. 1

Abstract

from arXiv · show

We provide a polynomial-time classical algorithm for noisy quantum circuits. The algorithm computes the expectation value of any observable for any circuit, with a small average error over input states drawn from an ensemble (e.g. the computational basis). Our approach is based upon the intuition that noise exponentially damps non-local correlations relative to local correlations. This enables one to classically simulate a noisy quantum circuit by only keeping track of the dynamics of local quantum information. Our algorithm also enables sampling from the output distribution of a circuit in quasi-polynomial time, so long as the distribution anti-concentrates. A number of practical implications are discussed, including a fundamental limit on the efficacy of noise mitigation strategies: for constant noise rates, any quantum circuit for which error mitigation is efficient on most input states, is also classically simulable on most input states.

I. INTRODUCTION

The paper addresses the limited understanding of general noisy quantum circuits in the regime between high-noise classical simulation and low-noise fault-tolerant computation. It presents classical algorithms for expectation values on most input states and discusses implications for error mitigation, advantage tests, and sampling.

I. INTRODUCTION

  • For most inputs drawn from a broad class of ensembles, the algorithms approximate expectation values for any noisy circuit, with polynomial or quasi-polynomial runtime depending on the observable and noise model.The computational basis is one allowed ensemble.Source: §I · p. 1
  • The method simulates Heisenberg evolution in the Pauli basis and truncates high-weight operators, which noise strongly affects.The paper states that this is the first rigorous proof that Pauli truncation succeeds for non-random circuits.Source: §I · p. 1
  • At constant noise rates, efficient error mitigation on most inputs is possible only for circuits that are classically simulable on most inputs.The paper also states that circuits exhibiting quantum advantage on most inputs must be macroscopically sensitive to noise.Source: §I · pp. 1–2
  • The algorithms also extend to sampling from anti-concentrating circuits and to random circuits with non-unital noise.For the latter setting, the paper reports improved runtime and generality over existing algorithms.Source: §I · p. 2

II. CLASSICAL ALGORITHM FOR NOISY QUANTUM CIRCUITS

The paper studies noisy circuits with uniform or gate-based noise and gives classical algorithms whose performance is stated over low-average ensembles of input states. The approach exploits noise-dependent damping of Pauli operators, with different runtime guarantees across the two noise models.

II. CLASSICAL ALGORITHM FOR NOISY QUANTUM CIRCUITS

  • Uniform noise acts on every qubit at every layer, whereas gate-based noise acts only on qubits participating in non-identity gates.The uniform model becomes close to maximally mixed after depth logarithmic in the number of qubits; gate-based noise allows fresh qubits unaffected by idle errors.Source: §II · p. 2
  • Under uniform noise, a Pauli operator of weight w is damped by e^-γw, while high-weight operators are more strongly affected than low-weight ones.The paper identifies the exponentially many high-weight operators and the need to bound truncation error for general circuits as central challenges.Source: §II · pp. 2–3
  • Uniform-noise circuits admit a polynomial-time algorithm for normalized observables under the stated efficient-coefficient and low-average-ensemble assumptions.Theorem 1 states the algorithm computes expectation values; the supplied theorem passage does not include its full runtime expression.Source: §II · p. 3
  • Gate-based-noise circuits admit a quasi-polynomial-time classical algorithm for normalized observables, with root-mean-square error ε over the ensemble.The supplied theorem excerpts do not give the full runtime expression.Source: §II · p. 3
  • A low-average ensemble has a mixture close to maximally mixed; any complete pure-state basis, including the computational basis, qualifies.The paper defines the metric of success as root-mean-square error over the ensemble.Source: §II · p. 4

A. Classical algorithm for quantum circuits with uniform noise

For uniform noise, the algorithm approximates the Heisenberg-evolved observable by summing low-weight Pauli paths. It bounds the discarded contribution by organizing paths by their weights across circuit layers and using their noise damping.

A. Classical algorithm for quantum circuits with uniform noise

  • The uniform-noise algorithm estimates the expectation value by approximating the Heisenberg-evolved observable with a sum of low-weight Pauli paths.A path is a sequence of Pauli operators across circuit layers, and the approximation keeps paths below threshold ℓ.Source: A. Classical algorithm for quantum… · p. 4
  • Grouping paths by layer weights in a tree lets the analysis bound the Frobenius norm of the truncated contribution using path orthogonality and noise damping.The Frobenius-norm bound controls the root-mean-square error over the input ensemble.Source: A. Classical algorithm for quantum… · p. 5
  • The error analysis recursively groups discarded paths by the earliest sequence of layer weights whose sum exceeds the truncation threshold.The recursion uses cumulative damping to bound the remaining contribution.Source: A. Classical algorithm for quantum… · p. 5
  • The runtime is determined by the number of paths below threshold ℓ, with bounds depending on whether the observable is arbitrary or a sum of m Pauli operators.The threshold is set using circuit depth, noise strength, and target error; uniform-noise circuits become trivially simulable after depth O(γ^-1 log(1/ε)).Source: A. Classical algorithm for quantum… · p. 5

B. Classical algorithm for quantum circuits with gate-based noise

For gate-based noise, the algorithm truncates the evolving observable to low-weight Pauli operators at each layer. A bound on lossy operator-weight flow controls the resulting error, including at large circuit depth.

B. Classical algorithm for quantum circuits with gate-based noise

  • Algorithm 2 truncates operators above weight ℓ at each layer, using only d + 1 truncations to avoid Algorithm 1’s exponential depth blow-up.It updates low-weight Pauli coefficients through Heisenberg evolution and computes the final expectation value from the truncated operator.Source: B. Classical algorithm for quantum… · pp. 5–6
  • Algorithm 2 performs d updates on O(nℓ) low-weight Pauli coefficients, with a moderate runtime increase over Algorithm 1 at the same ℓ.The challenge is that gate-based noise accumulates gradually, so uniform-noise bounds on one-step damping do not directly apply.Source: B. Classical algorithm for quantum… · p. 6
  • Gate-by-gate, operator norm flows between adjacent weights, and noise damps inward flow while leaving outward decreases undamped.Tracking this flow captures damping during weight growth without over-counting components that shrink and later regrow.Source: B. Classical algorithm for quantum… · p. 6
  • Summing the gate-wise flow bounds cancels currents among higher weights and bounds the tail above ℓ by e^-2γ(ℓ+1).The argument bounds the net current across the ℓ to ℓ + 1 boundary, then iterates the bound across weights.Source: B. Classical algorithm for quantum… · p. 7
  • Applying the lemma to Algorithm 2, total truncation error is less than (d + 1)e^(-2γ(ℓ+1)); setting ℓ ≈ γ^(-1) log(d/ε) ensures small root-mean-square error.Source: B. Classical algorithm for quantum… · p. 7

III. APPLICATIONS AND IMPLICATIONS

The applications connect noisy-circuit simulation to error mitigation, quantum-advantage criteria, and several computational settings. In particular, at constant noise rates, efficient mitigation on most input states implies classical simulability on most input states.

Lower bound on quantum error mitigation

  • For constant noise rates, error mitigation that estimates an ideal expectation value in polynomial time also yields a polynomial-time classical algorithm for that value.The result applies to most input states and to inverse-polynomial error ε under the stated low-average ensemble conditions.Source: §III · pp. 7–8

Noisy DQC1 ⊆BPP

  • Noisy DQC1 computations can be classically simulated in polynomial time because a single highly mixed input state forms a low-average ensemble.The result covers experiments with highly mixed inputs, including nuclear magnetic resonance spectroscopy and solid-state quantum simulators.Source: §III · p. 8

Sampling from anti-concentrated circuits

  • For anti-concentrated output distributions, the algorithms yield sampling within small total variation distance in quasi-polynomial time.The approach uses a reduction from noisy circuit sampling to expectation values in the presence of anti-concentration.Source: §III · p. 8

Random circuits with non-unital noise

  • For random circuits with non-unital noise, Algorithm 1 computes expectation values in polynomial time; this extension does not apply directly to general non-random circuits.The text notes that general circuits with non-unital noise can perform fault-tolerant computation.Source: §III · p. 8

Quantum advantage beyond sampling

  • If classical computation of an ideal expectation value requires exponential time, a noisy implementation succeeds only at noise rates γ = O(log2(n)/n).The paper proposes this noise-sensitivity criterion as a rigorous test for quantum advantage.Source: §III · p. 8

IV. OUTLOOK

The outlook emphasizes that experiments without error correction need noise rates that improve with system size for scalable quantum advantage. It also identifies open directions involving other dynamics, noise models, and simulation methods.

IV. OUTLOOK

  • The outlook presents the results as evidence that noisy circuits without error correction can be efficiently classically simulated.It connects this evidence to the long-term necessity of quantum error correction for scalable quantum advantage.Source: §IV · p. 8
  • For experiments without error correction, the results indicate that noise rates must improve proportionally with the number of qubits.The outlook frames quantum error correction as necessary for achieving scalable quantum advantage over classical computation.Source: §IV · pp. 8–9
  • The paper identifies continuous-time dynamics, dephasing or thermal noise, and improved simulation of highly connected architectures as open research directions.The authors speculate that their approach may help simulate highly connected circuits where tensor-network methods typically struggle.Source: §IV · p. 9

D. Classical algorithm for gate-based noise (Theorem 2)

The supplied passage lists two topics under a section on classical sampling algorithms for noisy quantum circuits: a reduction using anti-concentration and proofs of sampling algorithms.

D. Classical algorithm for gate-based noise (Theorem 2)

Appendix A: Comparison to existing results

Appendix A compares the paper’s algorithms with classical simulation methods across noise models, observables, and circuit architectures. Appendix B defines low-average input ensembles and bounds the expectation-value error caused by approximating an observable.

Appendix A: Comparison to existing results

  • For general circuits with gate-based noise, Theorem 2 gives an exponential improvement over naive 2^O(n) simulation; prior noise-aware algorithms cover only IQP and random circuits.The comparison concerns general circuits, unlike the cited prior algorithm classes.Source: Appendix A · p. 12
  • For all-to-all circuits with uniform noise, Theorem 1 gives an exponential improvement over naive 2^O(n) simulation at logarithmic depth.Uniform-noise expectation values become ε-close to their maximally mixed-state values at depth d ≥ γ^-1 log(1/ε).Source: Appendix A · p. 12
  • For local observables in general circuits, light-cone simulation takes 2^(1/ε)^O(γ^-1) time, while Algorithm 1 is polynomial in ε^-1.The light-cone contains 2^d qubits; Algorithm 1 has runtime (1/ε)^~O(γ^-2).Source: Appendix A · p. 12
  • For tensor-product observables in 1D circuits, the paper reports no improvement because matrix product state simulation is already efficient.The cited matrix product state runtime is 2^O(d), which is polynomial in ε^-1 for uniform noise.Source: Appendix A · p. 13
  • In 2D circuits, the algorithms generally improve existing runtimes from quasi-polynomial to polynomial, with the advantage depending on observable and parameter scaling.For local observables, Algorithm 1 is polynomial; for general tensor-product observables, its runtime may be better or worse than Ref., depending on n, d, ε, and γ.Source: Appendix A · p. 13
  • For 3D circuits, Theorem 1 improves tensor-product-observable runtimes from sub-exponential to polynomial or quasi-polynomial, and local-observable runtimes from quasi-polynomial to polynomial.The comparison is against the runtimes described for Ref. [105] and direct light-cone simulation.Source: Appendix A · p. 13

Appendix B: Low-average ensembles of states

  • A low-average ensemble with purity c has average state operator norm at most c/2^n; computational-basis states with n−m random bits and m fixed bits have c = 2^m.Any complete basis of pure states has c = 1.Source: Appendix B · p. 13
  • For a low-average ensemble of purity c, the root-mean-square expectation-value difference between O and ˜O is less than √c times their Frobenius-norm difference.Source: Appendix B · p. 14

Appendix C: Classical algorithm for uniform noise (Theorem 1)

The appendix analyzes classical expectation-value simulation under uniform and gate-based noise, using suppression of non-identity observable components and bounds on operator growth to establish algorithm accuracy and runtime. It also bounds resource requirements, including space use in terms of coefficient count and effective system size.

Appendix C: Classical algorithm for uniform noise (Theorem 1)

  • The non-identity component contracts by e^-γ(d+1), so circuits with depth d ≥ γ^-1 log(1/ε) can use the maximally mixed-state expectation within the stated RMS error.The bound applies over a low-average input ensemble of purity c; the replacement value is tr(O)/2^n.Source: Appendix C · p. 15
  • Theorem 1’s runtime scalings follow from two alternative bounds on Pauli-path counts; the second applies when O contains poly(n) Pauli terms.The count depends on the circuit depth and truncation weight, and the observable’s Pauli-term count can be used in the alternative bound.Source: Appendix C · pp. 16–17

1. Bounding noisy operator growth

  • Gate-based noise discounts increases in operator weight by e^-4γ or e^-2γ, while decreases are undiscounted, yielding cumulative-weight bounds.For an initial weight-one observable, the resulting bound can be strengthened to e^-4γ(w+1/2) times its squared Frobenius norm.Source: §1 · pp. 18–19

2. Analysis of algorithm

  • The gate-based algorithm’s Frobenius-norm error bound yields a root-mean-square expectation error bound for any low-average input ensemble.The analysis applies the cumulative-weight bound to truncation after each circuit layer.Source: §2 · p. 20
  • Updating retained Pauli coefficients takes O(Dℓ·12^ℓ·ℓ) time per circuit layer by exploiting sparse transitions and local gate amplitudes.Each transition amplitude factors into two-qubit amplitudes, and only transitions within the support expanded by the layer’s gates need be computed.Source: §2 · p. 21
  • Using ℓ·36^ℓ/ℓ! = O(1) simplifies the resource expression, though for moderate ℓ≲36 it may leave a large constant prefactor, still below the naive algorithm’s n^ℓ factor.Source: §2 · p. 21
  • Space is proportional to the number of coefficients c(t), and the requirements are comparable to exact time-evolution on neff ∼ ℓlog(n) qubits.Source: §2 · p. 21
  • For a desired error ε, the analysis chooses ℓ according to Eq. (D23) and substitutes it into the resource bound.Source: §2 · p. 21

Appendix E: Classical algorithms for sampling from noisy quantum circuits

The appendix extends the expectation-value algorithms to sampling, where reproducing the output distribution is a harder task. Under anti-concentration, the paper gives quasi-polynomial-time sampling algorithms for noisy circuits and for certain low-depth circuits with read-out noise.

Appendix E: Classical algorithms for sampling from noisy quantum circuits

  • Sampling is harder than computing expectation values because the output distribution contains information about exponentially many computational-basis expectation values.Source: Appendix E · p. 21
  • For uniform or gate-based noise, anti-concentrating output distributions can be sampled within root-mean-square total variation distance ε in quasi-polynomial time.The circuits and input ensembles must satisfy the theorem’s stated coefficient-computability and anti-concentration assumptions.Source: Appendix E · p. 22
  • For anti-concentrating circuits with read-out noise, sampling is possible in quasi-polynomial time at depth O(log n) for geometrically local circuits or O(log log n) more generally.The result holds even when the circuit gates are noiseless.Source: Appendix E · p. 22
  • The authors conclude that even a small amount of read-out noise can preclude sampling advantage for low-depth circuits in many cases.Source: Appendix E · p. 22

1. Reduction from noisy circuit sampling with anti-concentration to expectation values

  • The reduction approximates output probabilities by truncating high-weight terms and estimating the remaining low-weight expectation values; the resulting approximation may be negative but remains close in mean-square total variation distance.The low-weight estimates are assumed to have bounded root-mean-square error over the ensemble.Source: §1 · pp. 22–23

2. Proofs of sampling algorithms

The proofs establish classical sampling algorithms for noisy circuits and for low-depth circuits with read-out noise. General-circuit sampling is quasi-polynomial when the mean collision probability grows polynomially, while low-depth sampling uses exact computation of low-weight expectations.

General noisy circuits

  • When α = poly(n), the general-circuit sampling algorithms run in quasi-polynomial time for both uniform and gate-based noise.The main-text presentation takes α = O(1), termed anti-concentration.Source: §2 · p. 24

Low-depth circuits

  • For low-depth circuits with read-out noise, classical sampling applies to geometrically local depth O(log(n)) circuits or general depth O(log(log(n))) circuits.The theorem permits noiseless circuit gates and requires anti-concentration of the output distribution.Source: §2 · p. 25
  • Low-weight Pauli expectations can be computed exactly at sufficiently low depth by restricting their Heisenberg evolution to a bounded support.The support grows as O(ℓ_s·d^D) for geometrically local circuits or O(ℓ_s·2^d) for general circuits.Source: §2 · p. 25
  • Setting ε′ = 0 and ℓ_s = γ^-1 log(α/ε) yields the low-depth sampling runtime stated for the two circuit classes.The proof substitutes these choices into the sampling bound; the resulting scalings depend on depth, locality, noise, and anti-concentration.Source: §2 · p. 25

Appendix F: Extension to circuits with noise only in non-Clifford gates

The algorithms extend to circuits where noise acts only in non-Clifford gates, with Clifford gates noiseless. The extension tracks Pauli evolution by non-Clifford distance, which is unchanged by Clifford gates and increases by at most one at each non-Clifford gate.

Appendix F: Extension to circuits with noise only in non-Clifford gates

  • The stated results extend to noise only in non-Clifford layers and read-out, with the gate-based runtime scaling modified as specified by the extension.The extension covers the settings of Theorems 1 and 2.Source: Appendix F · p. 25
  • The extension remains valid with noiseless read-out when the observable is a sum of polynomially many Pauli operators.The condition is m = poly(n).Source: Appendix F · p. 25
  • For uniform noise, grouping Pauli paths across non-Clifford layers preserves the runtime of Theorem 1.The path count remains the same as before, with the number of non-Clifford layers playing the depth role.Source: Appendix F · pp. 25–26
  • For gate-based noise, the modified weight lower-bounds the non-Clifford gates needed to transform an initial operator into a target Pauli.This weight depends on circuit architecture and the choice of Clifford gates.Source: Appendix F · p. 26
  • Non-Clifford distance counts the minimum non-Clifford gates along a Pauli path from an operator in O, and Clifford gates preserve the resulting distribution.The distribution shifts by at most one under each non-Clifford gate.Source: Appendix F · p. 26

Appendix G: Extension to random non-unital noise

The algorithms also apply to random non-unital noise, including spontaneous emission in independently random directions, by controlling operator growth on average. The extension has a stated noise-rate condition, and random circuits with uniform spontaneous-emission noise admit an improved runtime.

Appendix G: Extension to random non-unital noise

  • Unlike the cited prior setting, the algorithms achieve polynomial time for large observable classes across architectures and quasi-polynomial time otherwise.The comparison is with Ref. [36], whose stated runtimes are exponential for non-local observables or circuits without geometric locality.Source: Appendix G · p. 27
  • The required randomness is that each non-unital channel acts in a random direction; spontaneous emission uses either transition direction with equal probability.The algorithm simulates a specific random instance with high success probability, and performance is evaluated over an input-state ensemble.Source: Appendix G · p. 27
  • For spontaneous emission in independently random directions with γ_s ≤ 4/7, the stated results continue to hold with γ = log(1/(1 − γ_s/2)) ≈ γ_s/2.The theorem replaces the factor d in the main-text Eq. (3) with 1.Source: Appendix G · p. 27
  • For random circuits with uniform spontaneous-emission noise, the runtime is poly(n) · (1/ε)^O(1/γ) when O is a sum of polynomially many Paulis.The improvement is stated for any circuit architecture.Source: Appendix G · p. 27
  • The analysis uses spontaneous emission as a prototypical non-unital channel and treats γ_s ≤ 4/7 as a proof simplification.The authors expect generalization to strictly contractive non-unital channels and do not expect larger rates to make simulation harder.Source: Appendix G · p. 27
  • The proof decomposes spontaneous emission into a depolarizing channel and a random-direction component whose average action does not increase Frobenius norm.This supports applying the algorithms under random non-unital noise.Source: Appendix G · pp. 27–28
  • For γ_s ≤ 4/7, the non-identity component of the evolved observable has root-mean-square Frobenius norm at most e^-γ(d+1)∥O∥_F.Consequently, beyond depth γ^-1 log(1/ε), the observable can be approximated by its identity component for most input states in a low-average ensemble.Source: Appendix G · p. 29

Appendix H: Implications for quantum error mitigation

The appendices connect efficient error mitigation to classical simulation and give a sufficient noise-sensitivity test for possible quantum advantage. They also describe exceptions to the mitigation result and explain why the proposed test is not a converse characterization.

Appendix H: Implications for quantum error mitigation

  • The mitigation corollary covers zero-noise extrapolation, probabilistic error cancellation, and Clifford data regression, but not virtual distillation.Virtual distillation uses multiple copies of each input state; noise suppression can lower effective noise and increase potential classical complexity.Source: Appendix H · p. 29
  • If an error-mitigation strategy estimates the observable to error ε/2 efficiently, the ideal expectation can be computed classically in polynomial time to root-mean-square error ε.The argument uses Theorem 1 with polynomially bounded ε^-1 and number of noisy circuits M.Source: Appendix H · p. 30

Appendix I: Test for the hardness of a given quantum circuit

  • Noise sensitivity is a necessary condition in the proposed test, not a sufficient one: highly noise-sensitive many-body observables or Loschmidt echoes need not be classically hard.The cited examples do not guarantee classical hardness.Source: Appendix I · p. 30
  • Efficient estimation of a noiseless expectation from a noisy experiment implies a classical algorithm computing it to root-mean-square error 4ε in the stated runtime.The argument combines the experiment's error bound with the classical approximation from Theorem 2.Source: Appendix I · p. 30

Appendix J: Noisy quantum circuits on any highly mixed input state

The appendix extends classical simulation to highly mixed inputs and to ensembles of noisy circuits with spatial disorder. It specifies the conditions and error guarantees for these extensions.

Appendix J: Noisy quantum circuits on any highly mixed input state

  • For input states with Renyi-2 entropy S(2)(ρ) = n − log2(c) and efficiently computable Pauli coefficients, a classical algorithm approximates C{ρ} within trace-norm error ε · √c.Its runtime is as in Theorems 1 and 2.Source: Appendix J · p. 31

Appendix K: Noisy quantum circuits with spatial disorder

  • For computational-basis inputs, estimating expectations over the input ensemble can be recast as estimating over circuits {CXs} applied to the fixed state |0n⟩⟨0n|.The appendix also extends beyond Pauli observables by decomposing them in the Pauli basis, with error scaled by the observable’s Pauli 1-norm.Source: Appendix K · p. 31
  • Spatial disorder means invariance under conjugation by any single-qubit Pauli; invariance under only single-qubit X conjugations gives a weaker setting tied to particular input states.Invariance under any single-qubit Pauli also permits extending the result to arbitrary input states.Source: Appendix K · p. 31
  • For noisy circuit ensembles with spatial disorder, a classical algorithm estimates tr(C{ρ}O) within root-mean-square error ε · ∥O∥Pauli,1, assuming efficiently computable Pauli coefficients of ρ and O.Its runtime is as in Theorems 1 and 2 of the main text.Source: Appendix K · p. 32
Loading 2407.12768v2…