PaperlayerView exact revision on arXiv

Source-linked AI summary

Exponentially tighter bounds on limitations of quantum error mitigation

Yihui Quek, Daniel Stilck França, Sumeet Khatri, Johannes Jakob Meyer, Jens Eisert

arXiv:2210.11505v3quant-phmath-ph

TL;DR

Quantum error mitigation seeks to recover noiseless results from noisy near-term circuits without fault-tolerant hardware overhead, but its scalability is unclear. The paper formulates mitigation as statistical inference and proves exponential or super-polynomial worst-case sample requirements, while identifying connectivity and input-state assumptions that delimit the conclusions.

  • Problem

    The paper asks how far classical post-processing can correct quantum noise as system size and circuit depth grow.

  • Method

    The paper reduces error mitigation to noisy-state discrimination and analyzes weak and strong mitigation using information-theoretic bounds for noisy quantum circuits.

  • Results

    Worst-case mitigation requires super-polynomially many samples even at poly log log(n) depth, with exponential sample requirements also shown for local depolarizing and non-unital noise.

  • Takeaways & Limitations

    Scaling error mitigation depends strongly on circuit connectivity and light-cone growth, while input-state-aware protocols face either exponential sampling or classical indistinguishability.

  • Takeaways & Limitations

    The fastest shallow-depth constructions require all-to-all connectivity, although analogous bounds are established for geometrically local circuits.

Abstract

from arXiv · show

Quantum error mitigation has been proposed as a means to combat unwanted and unavoidable errors in near-term quantum computing without the heavy resource overheads required by fault tolerant schemes. Recently, error mitigation has been successfully applied to reduce noise in near-term applications. In this work, however, we identify strong limitations to the degree to which quantum noise can be effectively `undone' for larger system sizes. Our framework rigorously captures large classes of error mitigation schemes in use today. By relating error mitigation to a statistical inference problem, we show that even at shallow circuit depths comparable to the current experiments, a superpolynomial number of samples is needed in the worst case to estimate the expectation values of noiseless observables, the principal task of error mitigation. Notably, our construction implies that scrambling due to noise can kick in at exponentially smaller depths than previously thought. They also impact other near-term applications, constraining kernel estimation in quantum machine learning, causing an earlier emergence of noise-induced barren plateaus in variational quantum algorithms and ruling out exponential quantum speed-ups in estimating expectation values in the presence of noise or preparing the ground state of a Hamiltonian.

Introduction to the technique

The paper defines error mitigation as classical post-processing of noisy-circuit measurements to recover noiseless expectation values or computational-basis samples. It reframes mitigation as noisy-state discrimination, linking successful mitigation to the number of noisy-state copies required for statistical inference.

  • Operational definition: Error mitigation appends measurements and classical post-processing to noisy quantum algorithms, producing noiseless expectation values or computational-basis samples.The framework includes protocols that may know the noise model exactly, as well as protocols that learn it during operation.
  • Two mitigation tasks: Weak error mitigation estimates observables of the noiseless circuit output, whereas strong error mitigation samples from its computational-basis output distribution.The two tasks correspond respectively to expectation-value estimation and approximate sampling from the clean state.
  • Statistical formulation: The framework gives the algorithm a noiseless-circuit description, noisy output copies, and collective measurements, then requires recovery of noiseless information.For state discrimination, the unknown noisy output is one of several states, and the algorithm must identify its label with high probability.
  • Reduction to discrimination: Weak mitigation can solve a noisy-state discrimination problem by estimating observables that distinguish computational-basis states from the maximally mixed state.For basis state ρx, the relevant Pauli expectation values are 2x_i − 1, while they vanish for the maximally mixed state.
  • Information-theoretic bound: The inverse decay rate of a noisy-state distinguishability quantity bounds mitigation sample complexity, with unitary 2-design tools controlling relative entropies under noise.The construction uses circuits whose noisy outputs become difficult to distinguish while retaining a formal connection to mitigation.

Results

The results establish exponential or super-polynomial worst-case sample requirements for mitigating noisy, highly entangling circuits, including under non-unital noise. They also identify connectivity and input-state knowledge as important boundaries for interpreting these lower bounds.

  • Depolarizing noise: s^-1p^-Ω(nD/s) noisy-state copies are required for weak mitigation under local depolarizing noise at depths D ≥ Ω(log^2(n/s)).Setting s = O(1) yields exponentially many samples in qubit number for polylogarithmic depth.
  • Depolarizing noise: Super-polynomially many samples are required already at depth poly log log(n) in the worst case.The hard circuits rapidly entangle and shift weight onto high-Hamming-weight Pauli operators, increasing sensitivity to noise.
  • Local connectivity: For geometrically local circuits on a d-dimensional lattice, exponentially many samples arise at depths O(n^(1/d) poly log(n)), with super-polynomial costs at slightly larger polylogarithmic depths.The onset occurs when light-cones become proportional to system size, tying mitigation difficulty to observable light-cone size rather than circuit size alone.
  • Non-unital noise: c^-Ω(nD) copies are required for weak mitigation of n-qubit, D-layer circuits alternating unitary 2-designs with local non-unital noise.The constant c depends on the noise channel, and the bound is exponential in both qubit number and depth.
  • Input-state awareness: With input-state information, either exponentially many noisy-state copies are needed or a purely classical algorithm produces an indistinguishable output.This qualification is necessary because classical simulation otherwise provides a zero-sample mitigation strategy, though it may be computationally hard.
  • Strong versus weak mitigation: At least exp(n) distinct expectation-value estimates may be needed to generate samples in their common eigenbasis.The result separates strong mitigation from weak mitigation even when the queried observables share an eigenbasis.

1. The interplay of entanglement and noisy computation

Highly entangling circuits can scramble rapidly under noise, making their outputs approach the maximally mixed state faster than less-entangling circuit ensembles. The authors attribute this faster mixing to entanglement.

  • 1. The interplay of entanglement and noisy computation: Highly entangling gates let the constructed circuits scramble quickly toward the maximally mixed state.The authors use this construction to illustrate that such circuits can be especially sensitive to noise.
  • 1. The interplay of entanglement and noisy computation: The reference ensemble B mixes exponentially in depth, whereas the authors’ structured ensemble has relative entropy decaying exponentially in both width n and depth D.The comparison concerns noisy random circuits built from uniformly random 2-qubit Clifford gates versus the authors’ more structured ensemble.
  • 1. The interplay of entanglement and noisy computation: The authors attribute the faster mixing of their ensemble to stronger entanglement than in ensemble B.They explain that product gates in ensemble B can leave a qubit’s noise effect independent of system size.

2. Loss of quantum advantage at log log n depth

Existing results place noise-induced loss of quantum advantage at logarithmic depth, but the authors’ construction produces relevant limitations at exponentially smaller depths. These effects extend to quantum machine learning and variational algorithms.

  • 2. Loss of quantum advantage at log log n depth: Earlier convergence results typically become inverse-polynomial in system width when the circuit depth is D = O(log(n)).This depth regime corresponds to shallow NISQ processors.
  • 2. Loss of quantum advantage at log log n depth: Noise-induced convergence constrains kernel estimation and causes earlier noise-induced barren plateaus in variational quantum algorithms.These applications are among the consequences associated with rapid convergence of noisy circuit outputs.
  • 2. Loss of quantum advantage at log log n depth: At log log(n) depth, the authors’ circuits already exhibit exponentially fast convergence in n, causing the associated effects to emerge exponentially earlier.The passage contrasts this onset with the inverse-polynomial convergence expected for typical NISQ depth scaling.
  • 2. Loss of quantum advantage at log log n depth: No exponential quantum speedup is available for estimating expectation values in noise, because classical algorithms have the same exponential complexity scaling.Quantum algorithms can at best improve the exponent for this task.

3. No noisy circuits for ground state preparation

For noisy ground-state preparation, the authors show that generic concentration bounds can be loose in the worst case. Their stronger bound imposes a stricter condition on the error probability at polylogarithmic depth.

  • 3. No noisy circuits for ground state preparation: For sufficiently high depth D polylogarithmic in n, avoiding concentration around non-advantageous strings requires p = O((nD)^-1) in the worst case.This condition follows from the authors’ exponentially faster decrease of the 2-Rényi entropy.
  • 3. No noisy circuits for ground state preparation: The authors’ worst-case bound is stricter than the generic loss-of-advantage condition p = Ω(D^-1).They state that the generic condition can be loose because the 2-Rényi entropy may decrease exponentially faster.
  • 3. No noisy circuits for ground state preparation: Because many important local Hamiltonians require at least logarithmic-depth circuits for ground-state preparation, this noise constraint applies within a relevant depth regime.The passage notes that highly entangled ground states of non-local Hamiltonians may require even greater depth.

Outlook

The paper establishes severe worst-case limitations for broad classes of current error-mitigation schemes, while identifying circuit locality and entanglement as important boundaries. It does not rule out mitigation at suitably small noise levels and points toward intermediate forms of error correction.

  • Outlook: The framework captures large classes of error-mitigation schemes used on noisy processors and identifies information-theoretic limitations exponentially tighter than previous bounds.The tighter bounds arise from a dependence of sampling cost on circuit width.
  • Outlook: The worst-case construction reaches circuits as shallow as poly log log(n), but still requires global connectivity.The authors suggest studying whether removing this requirement narrows the gap to practice.
  • Outlook: Suitably local circuits may improve error-mitigation performance, potentially at the cost of reduced expressivity.The authors present this as a possible practitioner prescription rather than an established general result.
  • Outlook: The results do not rule out quantum error mitigation for suitably small noise levels in existing architectures.The authors call for deeper study of which features of their worst-case construction occur in typical use cases.
  • Outlook: Extensive entanglement can support quantum advantage while also helping noise spread rapidly, creating a central tension in near-term quantum computing.The paper suggests that less-entangling regimes may be more amenable to tensor-network simulation.
  • Outlook: The authors anticipate intermediate schemes between error mitigation and resource-intensive fault tolerance, including parsimonious quantum error correction with limited redundancy.They identify the required amount of redundancy as an open question for practical quantum computing.

Author contributions statement

The authors’ contributions span conceptualization, formal analysis, methodology, and manuscript preparation. Writing responsibilities included both original drafting and review/editing.

  • Y.Q. and D.S.F. contributed to conceptualization, formal analysis, methodology, and writing the original draft.
  • S.K., J.J.M., and J.E. contributed to conceptualization, methodology, and writing through review and editing.

METHODS

The Methods section supplies background concepts, defines the error-mitigation setting, and develops weak and strong variants. It also connects the framework to protocols used in practice.

  • Preliminaries: The Methods section defines relative entropies, Pauli-group elements, and unitary 2-designs used in the proofs.
  • Error-mitigation setting: It introduces an error-mitigation setting together with weak and strong error-mitigation variants.
  • Practical protocols: The framework is argued to encompass virtual distillation, CDR, ZNE, and PEC protocols used in practice.

DERIVED QUANTITIES

The paper develops distance measures, Pauli operators and channels, depolarizing-noise properties, and unitary-design tools for analyzing noisy circuits and mitigation tasks.

  • Relative entropies: Relative entropy generalizes classical KL divergence to quantum states, with Rényi variants providing ordered distance measures.
  • Pauli operators and channels: Pauli operators form the basis for defining Pauli weight, Pauli channels, and the action of depolarizing noise on circuit states.
  • Depolarizing channels: Depolarizing noise acts on single-qubit X, Y, and Z operators by multiplying them by p while leaving I unchanged.
  • Unitary 2-designs: Clifford 2-designs are characterized by Pauli mixing, which makes them useful for the paper’s noisy-circuit analysis.
  • Error-mitigation variants: Strong error mitigation can imply weak mitigation by estimating observables through clean samples in an observable’s eigenbasis.

1. Weak error mitigation implies strong error mitigation only with exponentially-many observables

The paper studies whether weak error mitigation can produce clean samples, using statistical-query hardness to show that exponentially many same-basis observables are required in the worst case.

  • The paper asks whether polynomially many weakly mitigated expectation values can produce samples from a noiseless circuit.
  • Weak mitigation estimates observables, whereas strong mitigation outputs computational-basis samples from the noiseless circuit.
  • PARITIES can be learned with polynomially many samples but requires exponentially many statistical queries under the stated query model.
  • The reduction encodes PARITIES distributions into Clifford-circuit output states, connecting mitigation to a statistical-query learning problem.
  • Exponentially many same-eigenbasis expectation values are required to output samples from that basis in the worst case.
  • The bound holds against adaptive observable choices, but the result is restricted to observables sharing the desired sampling eigenbasis.
  • The broader circuit constructions make mitigation sample complexity exponential in both qubit number and depth under depolarizing noise.

I. RELATION TO PRACTICAL ERROR MITIGATION PROTOCOLS AND RELATED WORK

The framework applies to broad practical error-mitigation protocols by reducing their performance to noisy-state distinguishability and relative-entropy bounds. It covers virtual distillation, learning-based schemes, and zero-noise extrapolation, yielding exponential or super-polynomial worst-case sample requirements.

  • Framework: The central lemma links error-mitigation algorithms to relative-entropy bounds on the distributions of their outputs across different inputs.This interface allows the same argument to cover multiple protocol classes.
  • Virtual distillation: Virtual distillation remains subject to the framework even when it applies a short quantum post-processing circuit to noisy states.For unital noise, its success probability is known to decay exponentially with qubit number and circuit depth.
  • Learning-based schemes: Learning-based schemes train a functional relation between noisy and classically simulated noiseless expectation values, then apply it to the target circuit.The lower-bound analysis applies to the final inference step and therefore also lower-bounds total circuit usage, including training.
  • Zero-noise extrapolation: Zero-noise extrapolation combines estimates from circuits run at amplified noise levels to infer the zero-noise expectation value.Using the minimum amplified noise level already gives a bound; higher noise levels make convergence to the identity faster.
  • Relation to prior work: The framework extends prior limitation results from exponential dependence on depth to sample bounds exponential in both qubit number and depth.The stronger result captures protocols beyond the basic depolarizing-noise theorem.

A. Appetizer: mitigating depolarizing noise requires exponential-in-D samples

The appetizer theorem reduces weak error mitigation under depolarizing noise to noisy state discrimination. Because noise makes candidate outputs less distinguishable, mitigation requires exponentially many samples in circuit depth in the worst case.

  • A. Appetizer: mitigating depolarizing noise requires exponential-in-D samples: The proof embeds weak error mitigation into a state-identification problem and then applies Fano’s lower bound to the resulting distinguisher.The candidate inputs are the maximally mixed state and all n-bit computational-basis states.
  • A. Appetizer: mitigating depolarizing noise requires exponential-in-D samples: For any n-qubit depth-D circuit, Theorem 1 establishes an exponential-in-depth lower bound on the noisy copies needed for accurate expectation-value estimation.The theorem concerns input-state-agnostic weak error mitigation under local depolarizing noise, with additive error ϵ < 1/2.
  • A. Appetizer: mitigating depolarizing noise requires exponential-in-D samples: The reduction works because accurate noiseless expectation values distinguish the maximally mixed input from computational-basis inputs and recover the encoded n-bit label.Approximate estimates still suffice when ϵ < 1/2.
  • A. Appetizer: mitigating depolarizing noise requires exponential-in-D samples: m = p^-2D(1 − δ) samples are required for a constant failure probability in the associated noisy state-discrimination test.The bound follows by setting the distinguishability parameter to α = p^2Dm.
  • A. Appetizer: mitigating depolarizing noise requires exponential-in-D samples: The same conclusions apply when mitigation includes limited quantum post-processing, including the single-layer two-qubit circuit used in virtual distillation.The information-theoretic inequality is preserved in this setting.

B. The input-state aware case

Input-state awareness avoids a trivial impossibility argument only when classical simulation is excluded as an equivalent solution. Under that condition, rapidly mixing circuits still force exponential sample requirements or make quantum outputs indistinguishable from maximally mixed inputs.

  • B. The input-state aware case: Without further assumptions, input-state-aware mitigation has no general sample lower bound because classical simulation can achieve the target with zero quantum samples.The paper therefore asks whether successful low-sample mitigation produces outcomes meaningfully different from classical computation.
  • B. The input-state aware case: Theorem 2 states that input-state awareness does not remove exponential sample complexity when mitigation must meaningfully use the quantum device.The algorithm receives noisy copies plus classical descriptions of the circuit, noise, and input state.
  • B. The input-state aware case: In Case I, m c^-˜O(nD) = Ω(1), so even input-state-aware mitigation requires samples exponential in n and D.Case II instead says no algorithm can reliably distinguish the mitigation output from one obtained using maximally mixed states.
  • B. The input-state aware case: The improved bound depends exponentially on both width and depth, unlike the earlier generic-circuit bound whose exponent lacked n-dependence.This refinement is inserted into the same information-theoretic argument to obtain the stronger sample lower bound.
  • B. The input-state aware case: A rapidly mixing circuit C* maps computational-basis and maximally mixed inputs to output states with exponentially small distinguishability.The construction concatenates independently sampled circuit blocks and obtains an explicit n-dependent improvement over generic circuits.

E. Strengthening our results

The paper strengthens its lower bounds to local circuits, smaller depths, light-cone dependence, and non-unital noise, while identifying important scope boundaries for these results.

  • E. Strengthening our results: Local-gate constructions extend the limitations to geometrically local circuits and introduce dependence on light-cone size.The strengthened results apply to circuits restricted to local gates and explicitly track light-cone size.
  • E. Strengthening our results: O(n^(1/d)) depth is required in d-dimensional architectures before every qubit’s light-cone covers the entire system.With limited connectivity, the exponential-in-n mitigation cost appears when the full-system light-cone is reached.
  • E. Strengthening our results: Poly(log log(n)) depth can already require a super-polynomial number of samples for error mitigation.This follows by choosing s proportional to n/log^2(n), with polylogarithmic factors hidden in the bound.
  • E. Strengthening our results: The non-unital analysis finds exponentially small expected trace distance between outputs in both depth and qubit number for product noise channels.The result is established for circuits built from global 2-designs followed by repeated noisy channels.
  • E. Strengthening our results: For non-unitary channels, input-agnostic mitigation requires exponentially many copies even at constant iteration depth.The stated lower bound has the form Ω(c^-nD) for some c<1 when D=O(1).
  • E. Strengthening our results: The input-aware non-unital case remains subtler because the common limiting state may itself be computationally valuable.The paper leaves unclear whether classical simulation or practical mitigation can exploit access to samples from that unknown fixed state.

C. Bounds on the probability of successful virtual distillation

The paper bounds virtual distillation under non-unital noise by analyzing output purity, finding exponentially small success probabilities except for unitary or pure-state replacer channels.

  • C. Bounds on the probability of successful virtual distillation: Virtual distillation’s success probability is bounded by the purity of the relevant noisy state.The analysis introduces quantities controlling this purity bound for n-qubit product channels.
  • C. Bounds on the probability of successful virtual distillation: Both q_n and r_n are exponentially small in n unless each channel is unitary or a pure-state replacer.A pure-state replacer maps every input to the same pure state.
  • C. Bounds on the probability of successful virtual distillation: Virtual distillation therefore succeeds with exponentially small probability after one noise layer outside the unitary and replacer cases.Unitary errors leave the input pure, while replacer channels output a fixed pure product state.
Loading 2210.11505v3…