Simple Algorithm
Quantum Computing · Rydberg State · 28 min

Zero-Noise Extrapolation & PEC

Amplify noise to remove it; invert it with quasi-probabilities.

Two ideas dominate quantum error mitigation. Zero-noise extrapolation treats a noisy expectation value as a smooth function of the noise strength and extrapolates to zero; probabilistic error cancellation writes the inverse of the noise as a signed mixture of operations you can run. Both are unbiased only under assumptions, and both pay in variance.

What you’ll learn

  • Derive the Richardson extrapolation coefficients, the O(λn+1)\order{\lambda^{n+1}} bias and the variance amplification, including ∑j∣γj∣=2n+1−1\sum_j\abs{\gamma_j}=2^{n+1}-1 for equally spaced scales.
  • Justify noise scaling by time rescaling, unitary folding and probabilistic error amplification, and state their assumptions.
  • Construct quasi-probability decompositions of Pauli channels, prove that PEC is unbiased, and derive γ=e2∑kλk\gamma=e^{2\sum_k\lambda_k} for sparse Pauli–Lindblad noise.
  • Compare ZNE and PEC by bias, variance and modelling requirements.

Noise as a dial

Let E(λ)=Tr⁡[Oρ(λ)]E(\lambda)=\Tr[O\rho(\lambda)], where λ\lambda scales the noise and λ=1\lambda=1 is what the hardware does natively. Temme, Bravyi and Gambetta observed that time-independent Markovian noise can be amplified by stretching time.

DerivationAmplifying noise by stretching time
  1. dρdt=−i[H(t),ρ]+λ L(ρ),0≤t≤T\frac{d\rho}{dt} = -i[H(t),\rho] + \lambda\,\mathcal{L}(\rho),\qquad 0\le t\le T

    A drive H(t)H(t) and a Lindblad noise generator L\mathcal{L} of strength λ\lambda, assumed independent of the drive.

  2. Hc(t)=1c H(t/c),0≤t≤cTH_c(t) = \tfrac1c\,H(t/c),\qquad 0\le t\le cT

    Run the same pulse cc times slower and cc times weaker.

  3. τ=t/c:dρdτ=−i[H(τ),ρ]+cλ L(ρ)\tau = t/c:\qquad \frac{d\rho}{d\tau} = -i[H(\tau),\rho] + c\lambda\,\mathcal{L}(\rho)

    In rescaled time the coherent part is unchanged while the noise is multiplied by cc: the stretched run measures E(cλ)E(c\lambda).

  4. E(λ)=E(0)+∑k=1nakλk+O(λn+1)E(\lambda) = E(0) + \sum_{k=1}^{n} a_k\lambda^k + \order{\lambda^{n+1}}

    For weak noise EE is smooth in λ\lambda, and ZNE exploits this expansion.

Hardware-agnostic alternatives scale the noise digitally:

  • Unitary folding: U↦U(U†U)mU\mapsto U(U^\dagger U)^m gives λ=2m+1\lambda=2m+1 (Giurgica-Tiron et al., 2020). It assumes U†U^\dagger suffers the same noise as UU. For depolarizing noise D\mathcal{D}, which commutes with every unitary channel, the noisy folded gate is exactly D∘U∘D∘U†∘D∘U=D3∘U\mathcal{D}\circ U\circ\mathcal{D}\circ U^\dagger\circ\mathcal{D}\circ U=\mathcal{D}^3\circ U.
  • Probabilistic error amplification (PEA): learn a Pauli noise model, then insert extra Pauli errors at random so that every rate is multiplied by exactly λ≥1\lambda\ge1.

Richardson extrapolation

Measure at n+1n+1 scales λ0<λ1<⋯<λn\lambda_0<\lambda_1<\dots<\lambda_n and combine ER=∑jγjE(λj)E_{\mathrm{R}}=\sum_j\gamma_jE(\lambda_j), choosing the γj\gamma_j so that the first nn powers of λ\lambda cancel.

DerivationRichardson coefficients and bias
  1. ∑jγj=1,∑jγjλjk=0(k=1,…,n)\sum_j\gamma_j = 1,\qquad \sum_j\gamma_j\lambda_j^k = 0\quad(k=1,\dots,n)

    Keep E(0)E(0) and kill a1,…,ana_1,\dots,a_n: a Vandermonde system with a unique solution.

  2. γj=∏m≠jλmλm−λj\gamma_j = \prod_{m\neq j}\frac{\lambda_m}{\lambda_m-\lambda_j}

    These are the Lagrange basis polynomials ℓj(x)=∏m≠jx−λmλj−λm\ell_j(x)=\prod_{m\ne j}\frac{x-\lambda_m}{\lambda_j-\lambda_m} evaluated at x=0x=0. Interpolation is exact for polynomials of degree at most nn, which is exactly the system above.

  3. ER−E(0)=∑jγj O(λjn+1)=O(∑j∣γj∣ λjn+1)E_{\mathrm{R}}-E(0) = \sum_j\gamma_j\,\order{\lambda_j^{n+1}} = \order{\textstyle\sum_j\abs{\gamma_j}\,\lambda_j^{n+1}}

    Only the remainder survives: the bias is of order n+1n+1 in the noise.

  4. λj=j+1:γj=(−1)j(n+1j+1),∑j∣γj∣=2n+1−1\lambda_j=j+1:\qquad \gamma_j = (-1)^j\binom{n+1}{j+1},\qquad \sum_j\abs{\gamma_j} = 2^{n+1}-1

    For equally spaced scales 1,2,…,n+11,2,\dots,n+1 the coefficients are (2,−1)(2,-1), then (3,−3,1)(3,-3,1), then (4,−6,4,−1)(4,-6,4,-1).

The variance is the price. With NjN_j shots at scale λj\lambda_j, N=∑jNjN=\sum_jN_j in total, and single-shot variance σ2\sigma^2,

Var⁡(ER)=σ2∑jγj2Nj  ≥  σ2N(∑j∣γj∣)2\operatorname{Var}(E_{\mathrm{R}}) = \sigma^2\sum_j\frac{\gamma_j^2}{N_j}\ \ \ge\ \ \frac{\sigma^2}{N}\Big(\sum_j\abs{\gamma_j}\Big)^2
Equality holds for the optimal allocation Nj∝∣γj∣N_j\propto\abs{\gamma_j} (Cauchy–Schwarz). For equally spaced scales the overhead (2n+1−1)2(2^{n+1}-1)^2 grows exponentially with the order nn, so in practice n≤2n\le2 or 33.
Predict before you look

Four equally spaced noise scales λ=1,2,3,4\lambda=1,2,3,4 (third-order Richardson). What is ∑j∣γj∣\sum_j\abs{\gamma_j}?

Show the answer

15

γ=(4,−6,4,−1)\gamma=(4,-6,4,-1), so ∑j∣γj∣=15=24−1\sum_j\abs{\gamma_j}=15=2^4-1. Even with optimal shot allocation the variance grows by 152=22515^2=225 relative to a single run at native noise, before counting the larger noise at high λ\lambda.

If the noise is close to global depolarizing, E(λ)=E(0) e−bλE(\lambda)=E(0)\,e^{-b\lambda} fits better than a polynomial, and then E(0)=E(1)2/E(2)E(0)=E(1)^2/E(2) from two points. Choosing the model is the art of ZNE: a wrong model gives a confidently biased answer.

Probabilistic error cancellation

DerivationInverting depolarizing noise
  1. Dp(ρ)=(1−p)ρ+p3(XρX+YρY+ZρZ),Dp(P)=f P,f=1−4p3\mathcal{D}_p(\rho) = (1-p)\rho + \tfrac p3\big(X\rho X+Y\rho Y+Z\rho Z\big),\qquad \mathcal{D}_p(P) = f\,P,\quad f=1-\tfrac{4p}{3}

    Each non-identity Pauli PP commutes with itself and anticommutes with the other two, so it shrinks by ff.

  2. Dp−1=qI id+qP∑P∈{X,Y,Z}P,qI−qP=1f,qI+3qP=1\mathcal{D}_p^{-1} = q_I\,\mathrm{id} + q_P\sum_{P\in\{X,Y,Z\}}\mathcal{P},\qquad q_I-q_P=\tfrac1f,\quad q_I+3q_P=1

    Here P(ρ)=PρP\mathcal{P}(\rho)=P\rho P. A mixture of Pauli conjugations multiplies a non-identity Pauli by qI−qPq_I-q_P and the identity by qI+3qPq_I+3q_P.

  3. qP=−14(1f−1)<0,γ=qI+3∣qP∣=12(3f−1)=1+2p+O(p2)q_P = -\tfrac14\Big(\tfrac1f-1\Big)<0,\qquad \gamma = q_I+3\abs{q_P} = \tfrac12\Big(\tfrac3f-1\Big) = 1+2p+\order{p^2}

    Solve the two equations. The negative weight on the Pauli corrections is the price of "un-depolarizing".

Real devices are characterized more efficiently by twirling the noise of each layer into a Pauli channel and fitting a sparse Pauli–Lindblad model (van den Berg et al., 2023): N=exp⁡(∑kλk(Pk−id))\mathcal{N}=\exp\big(\sum_k\lambda_k(\mathcal{P}_k-\mathrm{id})\big) with Pk(ρ)=PkρPk\mathcal{P}_k(\rho)=P_k\rho P_k and only low-weight, local PkP_k. Its inverse is easy because all the factors commute.

DerivationCost of inverting Pauli–Lindblad noise
  1. eλ(P−id)=e−λ(cosh⁡λ id+sinh⁡λ P)e^{\lambda(\mathcal{P}-\mathrm{id})} = e^{-\lambda}\big(\cosh\lambda\,\mathrm{id}+\sinh\lambda\,\mathcal{P}\big)

    P2=id\mathcal{P}^2=\mathrm{id}, so the exponential series splits into even and odd parts.

  2. e−λ(P−id)=eλ(cosh⁡λ id−sinh⁡λ P),γk=eλ(cosh⁡λ+sinh⁡λ)=e2λe^{-\lambda(\mathcal{P}-\mathrm{id})} = e^{\lambda}\big(\cosh\lambda\,\mathrm{id}-\sinh\lambda\,\mathcal{P}\big),\qquad \gamma_k = e^{\lambda}(\cosh\lambda+\sinh\lambda) = e^{2\lambda}

    Flip the sign of λ\lambda to invert one factor, then add the absolute values of its weights.

  3. γ=∏ke2λk=exp⁡(2∑kλk),N∝γ2=exp⁡(4∑kλk)\gamma = \prod_k e^{2\lambda_k} = \exp\Big(2\sum_k\lambda_k\Big),\qquad N\propto\gamma^2 = \exp\Big(4\sum_k\lambda_k\Big)

    Each λk\lambda_k is approximately the probability of the error PkP_k, so the shot overhead is e4×(expected number of errors)e^{4\times(\text{expected number of errors})}, matching e4pLe^{4pL} for depolarizing noise.

Check your understanding

A learned Pauli–Lindblad model gives ∑kλk=1.5\sum_k\lambda_k=1.5, summed over all layers of a circuit. What is the PEC shot overhead?

  1. e3≈20e^{3}\approx20
  2. e6≈400e^{6}\approx400
  3. e1.5≈4.5e^{1.5}\approx4.5
  4. e12≈1.6×105e^{12}\approx1.6\times10^5
Show the answer

B. e6≈400e^{6}\approx400

γ=e2⋅1.5=e3\gamma=e^{2\cdot1.5}=e^3, and the shot count scales as γ2=e6≈403\gamma^2=e^6\approx403.

ZNE versus PEC

PropertyZNEPEC
BiasO(λn+1)\order{\lambda^{n+1}} if the model holds; uncontrolled otherwiseZero for an exact noise model; model error enters linearly
Variance overhead(∑j∣γj∣)2(\sum_j\abs{\gamma_j})^2, modest at low orderγtot2=e4∑kλk\gamma_{\mathrm{tot}}^2=e^{4\sum_k\lambda_k}, exponential in the total noise
NeedsA reliable noise dialAn accurate, stable noise model of every layer
Typical useLarge circuits where a small residual bias is acceptableSmaller circuits where unbiasedness matters

The two combine naturally. PEA uses the learned Pauli–Lindblad model of PEC not to cancel the noise, which is too expensive at scale, but to amplify it exactly, feeding a ZNE fit. This was the strategy of the 127-qubit experiments of Kim et al. (2023).

Key takeaways

  • Noise can be amplified by time rescaling (for drive-independent Markovian noise), unitary folding or probabilistic error amplification; ZNE then extrapolates E(λ)E(\lambda) to λ=0\lambda=0.
  • Richardson coefficients γj=∏m≠jλm/(λm−λj)\gamma_j=\prod_{m\ne j}\lambda_m/(\lambda_m-\lambda_j) cancel the first nn orders; the variance overhead (∑j∣γj∣)2(\sum_j\abs{\gamma_j})^2 grows exponentially with the order.
  • PEC is exactly unbiased for an exact noise model; its shot overhead is γtot2\gamma_{\mathrm{tot}}^2, with γ=12(3/f−1)≈1+2p\gamma=\tfrac12(3/f-1)\approx1+2p per depolarizing gate and γ=e2∑kλk\gamma=e^{2\sum_k\lambda_k} for Pauli–Lindblad noise.
  • ZNE trades a model-dependent bias for a low overhead; PEC trades unbiasedness for an exponential overhead and heavy characterization.

Check yourself

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

Question 1

For noise scales λ∈{1,3}\lambda\in\{1,3\}, the first-order Richardson coefficients (γ0,γ1)(\gamma_0,\gamma_1) are…

  1. (3/2, −1/2)(3/2,\ -1/2)
  2. (2, −1)(2,\ -1)
  3. (1/2, 1/2)(1/2,\ 1/2)
  4. (3, −2)(3,\ -2)
Show the answer

A. (3/2, −1/2)(3/2,\ -1/2)

γ0=λ1/(λ1−λ0)=3/2\gamma_0=\lambda_1/(\lambda_1-\lambda_0)=3/2 and γ1=λ0/(λ0−λ1)=−1/2\gamma_1=\lambda_0/(\lambda_0-\lambda_1)=-1/2. Check: 3/2−1/2=13/2-1/2=1 and 32⋅1−12⋅3=0\tfrac32\cdot1-\tfrac12\cdot3=0.

Question 2

Why is high-order Richardson extrapolation rarely used?

  1. Because its bias grows with the order
  2. Because it requires an exact noise model
  3. Because ∑j∣γj∣\sum_j\abs{\gamma_j} grows exponentially with the order, amplifying shot noise, and large-λ\lambda data are poorly described by the Taylor expansion
  4. Because it only works for a single qubit
Show the answer

C. Because ∑j∣γj∣\sum_j\abs{\gamma_j} grows exponentially with the order, amplifying shot noise, and large-λ\lambda data are poorly described by the Taylor expansion

For equally spaced scales ∑j∣γj∣=2n+1−1\sum_j\abs{\gamma_j}=2^{n+1}-1, so the variance overhead grows like 4n+14^{n+1}; the highest scales also push E(λ)E(\lambda) into a regime where low-order polynomials fit badly.

Question 3

PEC is unbiased provided that…

  1. the circuit is shallow
  2. the quasi-probability decomposition inverts the actual noise of every gate exactly
  3. all qiq_i are positive
  4. the noise is amplified to at least λ=3\lambda=3
Show the answer

B. the quasi-probability decomposition inverts the actual noise of every gate exactly

Unbiasedness follows from ∑iqiBi=N−1\sum_iq_i\mathcal{B}_i=\mathcal{N}^{-1} exactly. Any mismatch between the model and the real noise leaves a residual bias.

Question 4

For single-qubit depolarizing noise with Pauli error probability p≪1p\ll1 per gate, PEC over LL gates needs about how many times more shots?

  1. 1+2pL1+2pL
  2. e2pLe^{2pL}
  3. (1+p)L(1+p)^L
  4. e4pLe^{4pL}
Show the answer

D. e4pLe^{4pL}

γg≈1+2p\gamma_g\approx1+2p, so γtot≈e2pL\gamma_{\mathrm{tot}}\approx e^{2pL} and the shot overhead is γtot2≈e4pL\gamma_{\mathrm{tot}}^2\approx e^{4pL}.

Further reading

  • K. Temme, S. Bravyi & J. M. Gambetta, "Error mitigation for short-depth quantum circuits", Phys. Rev. Lett. 119, 180509 (2017).
  • Y. Li & S. C. Benjamin, "Efficient variational quantum simulator incorporating active error minimization", Phys. Rev. X 7, 021050 (2017).
  • S. Endo, S. C. Benjamin & Y. Li, "Practical quantum error mitigation for near-future applications", Phys. Rev. X 8, 031027 (2018).
  • E. van den Berg, Z. K. Minev, A. Kandala & K. Temme, "Probabilistic error cancellation with sparse Pauli–Lindblad models on noisy quantum processors", Nature Physics (2023).
  • Z. Cai et al., "Quantum error mitigation", Rev. Mod. Phys. 95, 045005 (2023).