Simple Algorithm
Quantum Computing · Rydberg State · 26 min

The Limits of Error Mitigation

Exponential sampling costs and what they imply.

Every mitigation method in the previous lessons pays a sampling cost that grows exponentially with the size of the circuit. Is that a failure of ingenuity or a law of nature? Recent theorems say it is a law: noise destroys distinguishability, and no amount of clever post-processing restores it cheaply.

What you’ll learn

  • Formalize error mitigation as statistical inference from noisy quantum data.
  • Prove a two-point lower bound: undoing global depolarizing noise of depth LL needs Ω((1−p)−2L/ε2)\Omega\big((1-p)^{-2L}/\varepsilon^2\big) samples, even with joint measurements.
  • Prove the distinguishability bound on unbiased mitigated estimators, and explain how Takagi et al. and Quek et al. extend it to local noise.
  • Assess what these limits imply for near-term quantum advantage and for the role of error correction.

Mitigation as inference

Abstractly, a mitigation protocol receives quantum data, namely noisy output states E(ρ)\mathcal{E}(\rho) of (possibly modified) circuits. It performs measurements, possibly joint across several copies as in virtual distillation, and post-processes the outcomes into an estimate E^\hat E of Tr⁡(Oρ)\Tr(O\rho). How many copies it needs is a question of statistics, and statistics has a standard tool for lower bounds: find two hypotheses that are hard to tell apart but must be told apart.

DerivationProof
  1. ρ±=I±2ε Od,Tr⁡(Oρ±)=±2ε\rho_\pm = \frac{\id\pm2\varepsilon\,O}{d},\qquad \Tr(O\rho_\pm)=\pm2\varepsilon

    Two valid states (since ∥2εO∥≤1\norm{2\varepsilon O}\le1) whose ideal values differ by 4ε4\varepsilon. An ε\varepsilon-accurate estimate has the sign of the truth, so the protocol distinguishes ρ+\rho_+ from ρ−\rho_- with probability at least 23\tfrac23.

  2. τ±=EL(ρ±)=I±b Od,b=2qε\tau_\pm = \mathcal{E}_L(\rho_\pm) = \frac{\id\pm b\,O}{d},\qquad b = 2q\varepsilon

    Noise shrinks the distinguishing signal by the factor qq.

  3. F(τ+,τ−)=1−b2,F(τ+⊗M,τ−⊗M)=(1−b2)M/2F(\tau_+,\tau_-) = \sqrt{1-b^2},\qquad F\big(\tau_+^{\otimes M},\tau_-^{\otimes M}\big) = (1-b^2)^{M/2}

    The two states commute, with eigenvalues (1±b)/d(1\pm b)/d on the ±1\pm1 eigenspaces of OO. The root fidelity F=Tr⁡∣τ+τ−∣F=\Tr\abs{\sqrt{\tau_+}\sqrt{\tau_-}} is multiplicative on tensor powers.

  4. 13 ≤ D(τ+⊗M,τ−⊗M) ≤ 1−(1−b2)M ≤ bM\tfrac13\ \le\ D\big(\tau_+^{\otimes M},\tau_-^{\otimes M}\big)\ \le\ \sqrt{1-(1-b^2)^M}\ \le\ b\sqrt{M}

    Helstrom: success probability 23\tfrac23 requires trace distance at least 13\tfrac13. Fuchs–van de Graaf gives D≤1−F2D\le\sqrt{1-F^2}, and 1−(1−x)M≤Mx1-(1-x)^M\le Mx.

  5. M ≥ 19b2=136 q2ε2M\ \ge\ \frac{1}{9b^2} = \frac{1}{36\,q^2\varepsilon^2}

    Rearrange. □\square

The bound is tight up to constants: the naive estimator E^=oˉ/q\hat E=\bar o/q, which rescales the measured mean oˉ\bar o of OO, is unbiased with variance at most 1/(q2M)1/(q^2M). So for this model the optimal mitigation cost is exactly the inverse squared attenuation of the signal, (1−p)−2L≈e2pL(1-p)^{-2L}\approx e^{2pL}: the same kind of exponential that ZNE and PEC pay.

Predict before you look

Noise has attenuated a signal to q=e−1≈0.37q=e^{-1}\approx0.37 of its ideal value. By what factor must the number of shots grow to estimate the ideal value with the same precision as without noise?

Show the answer

7.4

Rescaling by 1/q1/q multiplies the standard deviation by ee and the variance by e2≈7.39e^2\approx7.39. The two-point bound shows that no protocol can beat this by more than a constant factor.

Local noise and general protocols

Global depolarizing noise is a caricature, but the mechanism is general. The key lemma bounds what any unbiased estimator can extract from noisy data.

So the range Δ\Delta of any unbiased estimator, which controls its sample complexity through Hoeffding's inequality (M≈Δ2log⁡(1/δ)/ε2M\approx\Delta^2\log(1/\delta)/\varepsilon^2), must grow as fast as noise shrinks distinguishability. For noise that drives every state toward the maximally mixed state, that shrinkage is exponential in depth. Under layers of local depolarizing noise, the relative entropy D(EL(ρ) ∥ I/2n)D(\mathcal{E}_L(\rho)\,\|\,\id/2^n) starts at most at nn and contracts by a pp-dependent factor c<1c<1 per layer; Pinsker's inequality turns this into an exponentially small trace distance once L≳log⁡n/log⁡(1/c)L\gtrsim\log n/\log(1/c).

Check your understanding

Virtual distillation measures several noisy copies jointly. Can such multi-copy strategies escape the exponential sample cost?

  1. Yes: joint measurements on NN copies cancel the noise exactly
  2. Yes, if the copies are entangled with each other before the circuit runs
  3. Only for Pauli observables
  4. No: the distinguishability bound allows arbitrary joint measurements, so it covers multi-copy protocols too; they can reduce bias but not remove the exponential cost
Show the answer

D. No: the distinguishability bound allows arbitrary joint measurements, so it covers multi-copy protocols too; they can reduce bias but not remove the exponential cost

The bound involves D(E(ρ)⊗N,E(σ)⊗N)D\big(\mathcal{E}(\rho)^{\otimes N},\mathcal{E}(\sigma)^{\otimes N}\big), which already accounts for the best possible joint measurement on all copies. Multi-copy methods change constants and bias, not the exponential scaling.

What the limits mean

Write λ=∑locationspℓ\lambda=\sum_{\text{locations}}p_\ell for the expected number of faults per run, the noise budget. Every method you have met pays eΘ(λ)e^{\Theta(\lambda)}: rescaling (readout, global depolarizing) costs about e2λe^{2\lambda}, PEC about e4λe^{4\lambda}, postselection keeps a fraction of about e−λe^{-\lambda}. The theorems say that no method does fundamentally better on worst-case circuits.

Noise budget λ\lambdae2λe^{2\lambda}e4λe^{4\lambda}Verdict
0.50.52.72.77.47.4cheap
2255553×1033\times10^3feasible
552×1042\times10^45×1085\times10^8at the edge
20202×10172\times10^{17}5.5×10345.5\times10^{34}impossible

There is a second squeeze. The same noise that makes mitigation expensive also makes circuits easier to simulate classically: Pauli-path and tensor-network methods approximate noisy expectation values efficiently for many circuit families once noise has damped the high-weight contributions (for example Aharonov et al., 2023, for noisy random circuit sampling, and Schuster et al., 2024, for broad classes of noisy circuits). Useful mitigated computations therefore live in a window: enough qubits and depth to be classically hard, yet a noise budget of order a few.

Key takeaways

  • Error mitigation is inference from noisy data; noise contracts distinguishability, and every estimator must pay for the contraction.
  • Two-point bound: undoing global depolarizing noise needs M≥(1−p)−2L/(36ε2)M\ge(1-p)^{-2L}/(36\varepsilon^2) samples, matched by simple rescaling; joint measurements on many copies do not help.
  • Any unbiased estimator obeys ∣Tr⁡O(ρ−σ)∣≤Δ D(E(ρ)⊗N,E(σ)⊗N)\abs{\Tr O(\rho-\sigma)}\le\Delta\,D\big(\mathcal{E}(\rho)^{\otimes N},\mathcal{E}(\sigma)^{\otimes N}\big); for local noise this forces costs exponential in depth (Takagi et al.) and, in the worst case, superpolynomial costs at polylogarithmic depth (Quek et al.).
  • Costs scale like eΘ(λ)e^{\Theta(\lambda)} in the noise budget λ\lambda. The useful window is λ\lambda of order a few, squeezed further by classical algorithms for noisy circuits; large computations need error correction.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

In the two-point argument, why does noise force a protocol to use more samples?

  1. It shrinks the trace distance between the noisy outputs of states with different ideal values, and telling nearly identical states apart needs many copies
  2. It makes measurement outcomes deterministic
  3. It increases the number of qubits
  4. It makes the observable non-Hermitian
Show the answer

A. It shrinks the trace distance between the noisy outputs of states with different ideal values, and telling nearly identical states apart needs many copies

The ideal values of ρ±\rho_\pm differ by 4ε4\varepsilon, but their noisy versions differ only by b=2qεb=2q\varepsilon in each eigenvalue. Distinguishing them needs M=Ω(1/b2)M=\Omega(1/b^2) copies.

Question 2

For global depolarizing noise with p=0.01p=0.01 per layer and L=500L=500 layers, the factor (1−p)−2L(1-p)^{-2L} is about…

  1. 1010
  2. 150150
  3. 2×1042\times10^4
  4. 10810^{8}
Show the answer

C. 2×1042\times10^4

(1−p)−2L=e2Lln⁡(1/0.99)≈e1000×0.01005=e10.05≈2.3×104(1-p)^{-2L}=e^{2L\ln(1/0.99)}\approx e^{1000\times0.01005}=e^{10.05}\approx2.3\times10^4.

Question 3

Why does quantum error correction not run into these limits?

  1. Because it uses better estimators
  2. Because syndrome measurements with fresh ancillas remove entropy during the computation, so the encoded state never becomes indistinguishable
  3. Because logical qubits are immune to noise
  4. Because it postselects on trivial syndromes
Show the answer

B. Because syndrome measurements with fresh ancillas remove entropy during the computation, so the encoded state never becomes indistinguishable

The bounds concern post-processing of noisy outputs. QEC intervenes mid-circuit, pumping out entropy, so distinguishability of logical states is preserved up to the small logical error rate.

Question 4

What is the main practical implication of the mitigation lower bounds?

  1. Error mitigation never helps
  2. Error mitigation can replace error correction if enough shots are taken
  3. Only PEC is affected; ZNE escapes the bounds
  4. Mitigation is effective when the expected number of errors per circuit is of order one; scaling to large circuits requires error correction
Show the answer

D. Mitigation is effective when the expected number of errors per circuit is of order one; scaling to large circuits requires error correction

Costs scale like eΘ(λ)e^{\Theta(\lambda)} in the noise budget. For λ∼1\lambda\sim1 that is cheap, which is why mitigation is useful today; for large computations it is hopeless without QEC.

Further reading

  • R. Takagi, S. Endo, S. Minagawa & M. Gu, "Fundamental limits of quantum error mitigation", npj Quantum Information (2022).
  • R. Takagi, H. Tajima & M. Gu, "Universal sampling lower bounds for quantum error mitigation", Phys. Rev. Lett. (2023).
  • Y. Quek, D. Stilck França, S. Khatri, J. J. Meyer & J. Eisert, "Exponentially tighter bounds on limitations of quantum error mitigation", Nature Physics (2024).
  • D. Stilck França & R. García-Patrón, "Limitations of optimization algorithms on noisy quantum devices", Nature Physics (2021).
  • Z. Cai et al., "Quantum error mitigation", Rev. Mod. Phys. 95, 045005 (2023).