Probabilistic Error Cancellation

A quantum computer is asked to run an ideal unitary $\mathcal{U}$ , but the hardware always delivers something slightly wrong: a noise channel $\mathcal{N}$ rides along, so the executed operation is the completely positive map $\tilde{\mathcal{U}}=\mathcal{N}\circ\mathcal{U}$ . The obvious repair — apply the inverse $\mathcal{N}^{-1}$ and undo the damage — is impossible. Undoing decoherence would run the second law backwards; formally $\mathcal{N}^{-1}$ is a perfectly good linear map on operators but it is not completely positive, so no dial on the machine implements it. Probabilistic error cancellation gets the effect of $\mathcal{N}^{-1}$ without ever performing it: it moves the inversion out of the hardware and into classical post-processing. The move rests on one algebraic fact. Although $\mathcal{N}^{-1}$ is not a channel, it is a real linear combination of channels — operations the device can run, such as Pauli or Clifford gates: $\mathcal{N}^{-1}=\sum_i c_i\,\mathcal{O}_i$ with $\sum_i c_i=1$ . Trace preservation forces the coefficients to sum to one, but irreversibility forces some negative. You cannot run a circuit "with probability $-0.17$ ", yet you can run it, measure, and attach a minus sign. Sampling each $\mathcal{O}_i$ with probability $|c_i|/\gamma$ (where $\gamma=\sum_i|c_i|$ ) and re-weighting every shot by $\gamma\,\mathrm{sgn}(c_i)$ builds a signed Monte Carlo estimator whose average is the noise-free expectation value — exactly, with zero bias, provided the noise model is right. Nothing is free. The price is variance: each mitigated gate multiplies the shot budget by $\gamma^2$ , and the factors compound, so the cost climbs like $e^{2n\epsilon}$ in the number of noisy gates. That exponential is why PEC is the sharpest tool of the pre-fault-tolerant era for modest circuits and a wall for large ones — an unbiased estimator that error correction, not more sampling, must eventually replace.

Key takeaways

Probabilistic error cancellation (PEC) recovers a noise-free expectation value by writing a characterized noise channel's inverse as a real combination of gates the hardware can run.
Because the inverse of a noisy (non-unitary) channel is not completely positive, that combination carries negative coefficients — a quasiprobability whose absolute weights sum to $\gamma>1$ .
You sample operations with probability $|c_i|/\gamma$ , weight each shot by $\gamma\,\mathrm{sgn}(c_i)$ , and average; the estimator is provably unbiased when the model is exact.
The cost is variance inflation by $\gamma^2$ per gate, so the overhead $\gamma_{\mathrm{tot}}^2=\prod_g\gamma_g^2\approx e^{2n\epsilon}$ grows exponentially with depth and error rate.
PEC lives or dies by calibration: a wrong noise model leaves a residual bias no sampling removes — a mitigation, not a correction.
Key idea: the noise-inverse super-operator $\mathcal{N}^{-1}$ , though not a valid channel, is a real linear combination of valid channels; sampling those channels with sign-corrected weights converts an impossible deterministic inversion into an unbiased — but variance-amplified — Monte Carlo estimator of the ideal expectation value.

Where this lives today

PEC is now a standard entry in the near-term quantum toolbox. Its flagship demonstration came from IBM in 2023, where the noise of each entangling layer of a superconducting processor was characterized as a sparse Pauli–Lindblad model — a few hundred to a few thousand Pauli error rates per layer rather than a full, exponentially large channel — and its inverse sampled to cancel the dominant two-qubit-gate noise, recovering expectation values across dozens of qubits at non-trivial depth. In practice PEC is rarely run alone: hybrid pipelines invert only the worst noise with partial PEC and mop up the residual with zero-noise extrapolation. It also doubles as a diagnostic — failure to converge to a known calibration answer fingerprints model error, gate drift, or non-Markovian correlations. Qiskit and Mitiq ship PEC, and the frontier pushes the mitigation horizon outward with better noise learning to shrink $\gamma_g$ and honest accounting of where the wall forces the handoff to error correction.

The physical picture

Think of a noisy gate as a known smudge stamped on your data. You cannot physically un-smudge a quantum state — that is decoherence run in reverse, forbidden like unscrambling an egg. But an expectation value is an average over many runs, and averages can be repaired in software: run a small family of slightly different circuits, add some results and subtract others with carefully chosen frequencies, so the smudge cancels in the mean while the clean signal survives. The negative signs are the whole point — the software stand-in for an operation the hardware cannot perform. Concretely, the inverse is expanded over gates the machine can run, $\mathcal{N}^{-1}=\sum_i c_i\,\mathcal{O}_i$ , and the negative $c_i$ are unavoidable whenever the noise is lossy. The first figure shows this for a depolarized qubit: one tall positive weight on "do nothing" and three small negative weights on the Pauli corrections. The one-norm $\gamma=\sum_i|c_i|$ measures how far outside the physical channels the inverse reaches — exactly the factor by which sampling costs inflate.

Figure

Quasiprobability decomposition of the depolarizing inverse at p = 0.4. One positive weight on the identity, three negative weights on the Pauli corrections X, Y, Z. The signed weights sum to Σᵢ cᵢ = 1 so trace is preserved, while their absolute values sum to the overhead γ = 2.0, the per-gate sampling cost

The overhead $\gamma$ is small for weak noise — a $1\%$ gate gives $\gamma\approx1.015$ — so one gate is nearly free. But $\gamma$ multiplies down the circuit, so the cost is exponential in size. The second figure plots this for the depolarizing channel: $\gamma$ sits just above one for realistic error but curves sharply upward and diverges as the noise approaches the point where the channel erases its input. That divergence is the physical wall — where information is destroyed, no post-processing can retrieve it, and PEC has nothing to invert.

Figure

The per-gate sampling overhead γ = (1 + p/2)/(1 − p) for a single-qubit depolarizing channel of strength p. Manageable for small p (p = 0.1 gives γ = 1.17, p = 0.4 gives γ = 2.0) but diverging as p → 1, where the channel sends every state to the maximally mixed I/2 and becomes non-invertible

The core equations

Start from what the hardware does. Programming a gate $\mathcal{U}$ executes it followed by a characterized noise channel $\mathcal{N}$ ; if $\mathcal{N}$ is invertible we can name — but not run — the operation that would undo it.

\tilde{\mathcal{U}} = \mathcal{N}\circ\mathcal{U},\qquad \mathcal{U} = \mathcal{N}^{-1}\circ\tilde{\mathcal{U}} \qquad (1)

where: $\mathcal{U}$ — ideal unitary super-operator, $\mathcal{U}(\rho)=U\rho U^\dagger$ ; $\mathcal{N}$ — characterized CPTP noise channel; $\tilde{\mathcal{U}}$ — the noisy operation the device runs; $\mathcal{N}^{-1}$ — linear inverse of the noise map, existing but not CPTP in general. Reading: the ideal circuit is one $\mathcal{N}^{-1}$ away from the noisy one — the method realizes that inverse without a device that implements it. The realization is a quasiprobability decomposition: expand $\mathcal{N}^{-1}$ over operations the machine can run, with the coefficients summing to one by trace preservation.

\mathcal{N}^{-1} = \sum_i c_i\,\mathcal{O}_i,\qquad \sum_i c_i = 1,\qquad c_i\in\mathbb{R} \qquad (2)

where: $\mathcal{O}_i$ — implementable (CPTP) basis operations, typically Paulis or Cliffords; $c_i$ — real quasiprobability coefficients, at least one negative; $\sum_i c_i=1$ is trace preservation. Reading: an honest equality of super-operators — the negativity is what stops the right-hand side from being a physical channel. Two derived quantities run the sampler: the one-norm $\gamma$ is the total absolute weight, and dividing each $|c_i|$ by it gives a probability distribution.

\gamma = \sum_i |c_i| \;\ge\; 1,\qquad p_i = \frac{|c_i|}{\gamma} \qquad (3)

where: $\gamma$ — one-norm of the quasiprobability, the sampling cost (the decomposition's negativity); $p_i$ — normalized probability of drawing $\mathcal{O}_i$ . Reading: $\gamma\ge1$ always, equal to one precisely when $\mathcal{N}^{-1}$ is already a physical channel; every unit above is irreversibility paid for in variance. Each shot draws an $\mathcal{O}_i$ , measures the observable, and multiplies by the sign-and-scale factor; in expectation it is the ideal value — PEC's central promise.

\hat{O}_{\mathrm{PEC}} = \gamma\,\mathrm{sgn}(c_i)\,o_i,\qquad \mathbb{E}\!\left[\hat{O}_{\mathrm{PEC}}\right] = \langle O\rangle_{\mathrm{ideal}} \qquad (4)

where: $\hat{O}_{\mathrm{PEC}}$ — single-shot mitigated estimator for $O$ ; $o_i$ — value of $O$ on the run using $\mathcal{O}_i$ ; $\mathrm{sgn}(c_i)$ — sign correction restoring the quasiprobability weight. Reading: the machine only runs physical circuits; the impossible part lives in the classical factor $\gamma\,\mathrm{sgn}(c_i)$ . The catch is the spread: each shot is inflated by $\gamma$ , so its variance is inflated by $\gamma^2$ .

\mathrm{Var}\!\left[\hat{O}_{\mathrm{PEC}}\right] \;\le\; \gamma^2\,O_{\max}^2 \qquad (5)

where: $O_{\max}$ — largest magnitude eigenvalue of $O$ , bounding a single shot's range; $\gamma^2$ — variance amplification relative to unmitigated sampling. Reading: reaching a target error needs about $\gamma^2$ times as many shots — the exponential wall lives here once $\gamma$ compounds. Across a circuit the inverses of independent layers multiply, so do their one-norms, and the shot budget scales as the product squared.

\gamma_{\mathrm{tot}} = \prod_{g=1}^{n}\gamma_g,\qquad N_{\mathrm{shots}} \sim \frac{\gamma_{\mathrm{tot}}^2}{\delta^2} \qquad (6)

where: $n$ — number of noisy gates each carrying an independent inverse; $\gamma_g$ — per-gate overhead $\ge1$ ; $\delta$ — target standard error. Reading: for weak noise $\gamma_g=1+O(\epsilon)$ , so $\gamma_{\mathrm{tot}}^2\approx e^{2n\epsilon}$ — tame while $n\epsilon\lesssim1$ , exponential after. Finally, the workhorse: the inverse of a single-qubit depolarizing channel over identity and Pauli operations (convention $\mathcal{D}_p(\rho)=(1-p)\rho+p\,\tfrac{I}{2}$ , $p$ the full-depolarization probability).

\mathcal{D}_p^{-1} = \frac{4-p}{4(1-p)}\,\mathcal{I} \;-\; \frac{p}{4(1-p)}\big(\mathcal{X}+\mathcal{Y}+\mathcal{Z}\big) \qquad (7)

where: $\mathcal{D}_p$ — depolarizing channel $\rho\mapsto(1-p)\rho+p\,\tfrac{I}{2}$ ; $\mathcal{I},\mathcal{X},\mathcal{Y},\mathcal{Z}$ — Pauli super-operations $\rho\mapsto P\rho P$ . Reading: coefficients sum to one, absolute values to $\gamma_{\mathcal{D}_p}=(1+p/2)/(1-p)$ — the curve above. Over $M$ circuits, $\langle O\rangle_{\mathrm{ideal}}\approx\tfrac{1}{M}\sum_m \gamma_{\mathrm{tot}}\big(\prod_g\mathrm{sgn}\,c_{i_g^{(m)}}\big)o_m$ . The three derivations below establish why the weights go negative, why the signed average is unbiased, and how much it costs.

Derivation AWhy the noise inverse must carry negative weight

The goal is to prove that the negativity in the quasiprobability decomposition is not a modeling choice but a theorem: whenever $\mathcal{N}$ is a genuinely noisy (non-unitary) channel, its inverse can never be written with all coefficients non-negative, so at least one $c_i<0$ and $\gamma>1$ strictly. The argument needs no calculation, only that a convex mixture of channels is again a channel.

Step 1. Suppose, for contradiction, that $\mathcal{N}^{-1}=\sum_i c_i\mathcal{O}_i$ with every $\mathcal{O}_i$ CPTP, every $c_i\ge0$ , and $\sum_i c_i=1$ . Then $\mathcal{N}^{-1}$ is a convex combination of channels, hence itself CPTP. Why: the set of CPTP maps is convex, so a probability-weighted average of channels is a legitimate channel.

Step 2. If $\mathcal{N}^{-1}$ is CPTP, then $\mathcal{N}$ is a channel with a CPTP inverse — reversible within the physical operations. But a reversible CPTP map is necessarily a unitary conjugation $\rho\mapsto U\rho U^\dagger$ . Why: reversibility forbids leakage to an environment, since a non-trivial dilation would lose distinguishability no channel can restore (data-processing inequality).

Step 3. By assumption $\mathcal{N}$ is noisy, hence not a unitary conjugation — a contradiction. So Step 1 fails: at least one $c_i<0$ , and $\gamma=\sum_i|c_i|>|\sum_i c_i|=1$ . Why: the triangle inequality is saturated only when all terms share a sign, so any negative weight pushes $\gamma$ above one, measuring how far the inverse sits outside the physical set.

Go deeper · Derivation B · 1 minUnbiasedness of the signed Monte Carlo estimator

Derivation BUnbiasedness of the signed Monte Carlo estimator

The goal is to show that the sampling recipe — draw $\mathcal{O}_i$ with probability $p_i=|c_i|/\gamma$ , insert it, measure $O$ , report $\gamma\,\mathrm{sgn}(c_i)$ times the outcome — has expectation equal to the ideal, noise-free value exactly, with no bias, so long as the characterized channel matches the true one. The proof is a short chain of identities whose one non-trivial move is that the sampling weight and sign correction conspire to rebuild the true coefficient $c_i$ .

Step 1. Condition on the drawn index $i$ . The device runs $\mathcal{O}_i$ after the noisy gate, so the conditional mean is $\mathbb{E}[o\mid i]=\mathrm{Tr}\!\left[O\,(\mathcal{O}_i\circ\tilde{\mathcal{U}})(\rho)\right]$ and the reported value is $\hat O=\gamma\,\mathrm{sgn}(c_i)\,o$ . Why: the hardware executes only the physical operation $\mathcal{O}_i\circ\tilde{\mathcal{U}}$ ; the sign and $\gamma$ are applied afterward in software.

Step 2. Average over the sampling: $\mathbb{E}[\hat O]=\sum_i p_i\,\gamma\,\mathrm{sgn}(c_i)\,\mathrm{Tr}\!\left[O\,(\mathcal{O}_i\circ\tilde{\mathcal{U}})(\rho)\right]$ . Why: the total expectation is the weighted sum of the conditional means.

Step 3. Collapse the weights: $p_i\,\gamma\,\mathrm{sgn}(c_i)=\tfrac{|c_i|}{\gamma}\,\gamma\,\mathrm{sgn}(c_i)=c_i$ . Why: the engine of the method — the probability cancels $\gamma$ and the sign turns $|c_i|$ back into the signed quasiprobability, recovering the exact coefficient a deterministic inversion would use.

Step 4. Reassemble by linearity: $\mathbb{E}[\hat O]=\mathrm{Tr}\!\left[O\,\big(\sum_i c_i\mathcal{O}_i\big)\circ\tilde{\mathcal{U}}(\rho)\right]=\mathrm{Tr}\!\left[O\,(\mathcal{N}^{-1}\circ\tilde{\mathcal{U}})(\rho)\right]$ . Why: the sum $\sum_i c_i\mathcal{O}_i$ is, by (2), exactly $\mathcal{N}^{-1}$ — the average has rebuilt it.

Step 5. Cancel the noise: since $\tilde{\mathcal{U}}=\mathcal{N}\circ\mathcal{U}$ and $\mathcal{N}^{-1}\circ\mathcal{N}=\mathrm{id}$ , $\mathbb{E}[\hat O]=\mathrm{Tr}\!\left[O\,\mathcal{U}(\rho)\right]=\langle O\rangle_{\mathrm{ideal}}$ . Why: the inverse annihilates the noise — holding only if the modeled $\mathcal{N}$ equals the true noise, the estimator's single assumption.

Go deeper · Derivation C · 1 minSampling cost of inverting the depolarizing channel

Derivation CSampling cost of inverting the depolarizing channel

The goal is to compute the quasiprobability coefficients and overhead $\gamma$ for the single-qubit depolarizing channel from scratch, verify the coefficients preserve trace, and locate the noise strength at which the inverse ceases to exist. The Pauli-transfer basis makes the channel diagonal, so inversion just reciprocates eigenvalues; the only care is to fix one parametrization, since the literature carries two with different-looking $\gamma$ .

Step 1. Fix $\mathcal{D}_p(\rho)=(1-p)\rho+p\,\tfrac{I}{2}\,\mathrm{Tr}\rho$ ; since $\tfrac{I}{2}\mathrm{Tr}\rho=\tfrac14(\rho+X\rho X+Y\rho Y+Z\rho Z)$ , the completely depolarizing map is $\mathcal{D}_*=\tfrac14(\mathcal{I}+\mathcal{X}+\mathcal{Y}+\mathcal{Z})$ , and $\mathcal{D}_p=(1-p)\,\mathrm{id}+p\,\mathcal{D}_*$ has eigenvalue $1$ on $I$ , $1-p$ on $X,Y,Z$ . Why: on Paulis both $\mathrm{id}$ and $\mathcal{D}_*$ are diagonal, so the channel inverts eigenvalue-by-eigenvalue.

Step 2. Invert on the diagonal: $\mathcal{D}_p^{-1}=\alpha\,\mathrm{id}+\beta\,\mathcal{D}_*$ needs eigenvalue $1/(1-p)$ on the Paulis (where $\mathcal{D}_*$ vanishes), so $\alpha=1/(1-p)$ ; and $1$ on $I$ , so $\alpha+\beta=1$ , $\beta=-p/(1-p)$ . Why: the $\{\mathrm{id},\mathcal{D}_*\}$ basis that diagonalizes the channel turns operator inversion into two scalar equations.

Step 3. Expand $\mathcal{D}_*=\tfrac14(\mathcal{I}+\mathcal{X}+\mathcal{Y}+\mathcal{Z})$ : $c_{\mathcal{I}}=\alpha+\tfrac{\beta}{4}=\tfrac{4-p}{4(1-p)}$ and $c_X=c_Y=c_Z=\tfrac{\beta}{4}=-\tfrac{p}{4(1-p)}$ . Trace check: $\sum_i c_i=\tfrac{4-p-3p}{4(1-p)}=1$ . Why: the coefficients must sum to one since $\mathcal{D}_p^{-1}$ inverts a trace-preserving map — an independent check on the algebra.

Step 4. One-norm and limits: $\gamma=|c_{\mathcal{I}}|+3|c_X|=\tfrac{4-p+3p}{4(1-p)}=\tfrac{1+p/2}{1-p}$ . As $p\to0$ , $\gamma\to1$ ; as $p\to1$ , $\gamma\to\infty$ . Why: at $p=1$ the channel sends every input to $I/2$ , its eigenvalue $1-p$ hits zero, the map is singular, and no finite-weight inverse exists — the information-destroyed wall.

Limiting cases

How $\gamma$ and PEC's feasibility depend on the noise structure:

Case	Result	Meaning
Weak local noise	$\gamma=1+O(\epsilon),\;\; \gamma_{\mathrm{tot}}^2\approx e^{2n\epsilon}$	For per-gate error $\epsilon\ll1$ across $n$ gates, the cost is tame while $n\epsilon\lesssim1$ — this is PEC's practical operating regime.
Depolarizing channel	$\gamma=\dfrac{1+p/2}{1-p}$ (single qubit)	Closed form in the depolarizing strength $p$ ; diverges as $p\to1$ , where the channel is non-invertible and information is irretrievably lost.
Amplitude damping	$\mathcal{N}_{\mathrm{AD}}^{-1}$ not a Pauli mixture	Non-unital noise needs a richer basis (Paulis plus resets), so the decomposition is less compact and $\gamma$ larger for the same average error.
Deep / high-error circuits	$\gamma_{\mathrm{tot}}^2=\prod_g\gamma_g^2\to\infty$	The multiplicative blow-up makes PEC infeasible past a depth set by the error budget — the wall that motivates fault-tolerant error correction.

Common trapMore sampling cannot fix a wrong noise model

Two traps recur. First, $\gamma$ multiplies across gates, it does not add: every mitigated layer scales variance by $\gamma^2$ , so the shot budget grows exponentially with depth, and a circuit that looks "only twice as noisy" can cost thousands of times more shots. Second, PEC's unbiasedness is only as good as your characterization of $\mathcal{N}$ : if the model drifts from the true channel, the estimator converges (as $M\to\infty$ ) not to $\langle O\rangle_{\mathrm{ideal}}$ but to $\mathrm{Tr}[O\,(\mathcal{N}_{\mathrm{est}}^{-1}\mathcal{N}_{\mathrm{true}}\,\mathcal{U})(\rho)]$ , a residual bias infinite sampling never removes. PEC turns a systematic error into a statistical one only to the extent calibration is trustworthy — a mitigation, not a correction.

Worked examples

1 · The quasiprobability of a single depolarized qubit (fully worked)

A single-qubit gate is followed by a depolarizing channel of strength $p=0.4$ (convention $\mathcal{D}_p(\rho)=(1-p)\rho+p\,I/2$ ). Build the quasiprobability decomposition, find the sampling distribution and signs, compute $\gamma$ , and state the shot cost.

Step 1. Coefficients from equation (7): $c_{\mathcal{I}}=\dfrac{4-p}{4(1-p)}=\dfrac{3.6}{2.4}=\mathbf{1.500}$ , and each Pauli weight $c_X=c_Y=c_Z=-\dfrac{p}{4(1-p)}=-\dfrac{0.4}{2.4}=\mathbf{-0.1667}$ . Trace check: $1.500-3(0.1667)=\mathbf{1}$ .

Step 2. Overhead. $\gamma=|c_{\mathcal{I}}|+3|c_X|=1.500+3(0.1667)=\mathbf{2.0}$ , matching $(1+p/2)/(1-p)=1.2/0.6$ — the amber marker on the second figure.

Step 3. Sampling and signs. Draw the identity with probability $p_{\mathcal{I}}=1.500/2.0=\mathbf{0.75}$ ; each of $X,Y,Z$ with probability $0.1667/2.0=\mathbf{0.0833}$ (summing to $0.25$ ). Identity draws take sign $+1$ , Pauli draws $-1$ ; every outcome is multiplied by $\gamma\,\mathrm{sgn}=\pm2.0$ .

Step 4. Shot cost. Variance is inflated by $\gamma^2=\mathbf{4}$ , so matching an unmitigated run's error needs about four times as many shots for this gate. Decomposition $\mathcal{D}_{0.4}^{-1}=1.5\,\mathcal{I}-0.1667(\mathcal{X}+\mathcal{Y}+\mathcal{Z})$ , $\gamma=2.0$ , sampling $(0.75,\,0.0833\times3)$ with sign $-1$ on the Paulis, shot cost $\times4$ .

2 · Overhead of a hundred-gate circuit

A circuit contains $100$ two-qubit gates, each with per-gate overhead $\gamma_g=1.02$ . Estimate the total overhead and shot budget, and read off the "mitigation horizon".

Step 1. Overhead multiplies (eq. 6): $\gamma_{\mathrm{tot}}=1.02^{100}=e^{100\ln1.02}=e^{1.9803}\approx\mathbf{7.24}$ .

Step 2. Shot budget scales as the square: $\gamma_{\mathrm{tot}}^2\approx\mathbf{52}$ , roughly 50 times more shots than unmitigated for the same error — expensive but feasible.

Step 3. Push the depth. At $500$ such gates $\gamma_{\mathrm{tot}}^2\approx e^{19.8}\approx4\times10^{8}$ . The exponential $e^{2n\epsilon}$ is gentle until $n\epsilon\sim1$ then brutal — solving $e^{2n\epsilon}\lesssim N\delta^2$ gives the largest rescuable circuit. $\gamma_{\mathrm{tot}}\approx7.2$ and a $\sim50\times$ shot cost at $100$ gates; the same $2\%$ noise makes $500$ gates cost $\sim10^{8}\times$ — the wall where mitigation must yield to correction.

Physics of the portrait

Probabilistic error cancellation is barely a decade old, born from a specific realization about quasiprobabilities that a small group of theorists turned into working hardware protocols. It belongs to quantum error mitigation — squeezing accurate answers from imperfect, uncorrected devices — which crystallized around 2017 and now sits between raw NISQ hardware and the still-distant fault-tolerant machine.

Origins · 1 minquantum error mitigation and how this was discovered

quantum error mitigation

the quasiprobability toolkit for pre-fault-tolerant devices · near-term quantum computing

Quantum error mitigation is the youngest idea in this chapter and the most pragmatic: unlike error correction, it accepts uncorrected qubits and asks only for accurate expectation values, paid for in extra runs rather than extra qubits. PEC was introduced in 2017 by Kristan Temme, Sergey Bravyi, and Jay Gambetta, who expanded the non-physical inverse of a characterized noise channel as a quasiprobability over physical gates and estimated it by signed sampling — an unbiased estimator with a controllable, if exponential, cost. The next year Suguru Endo, Simon Benjamin, and Ying Li generalized it to realistic gate sets, making it a practical recipe rather than a theorem. Its mathematics is inherited: quasiprobability representations of completely positive maps (the negativity that powers PEC is the same that marks non-classicality in Wigner functions), and Monte Carlo estimation of signed integrals from the fermionic sign problem, where $\gamma$ plays the role of sign-problem severity. By 2023 Ewout van den Berg, Zlatko Minev, Abhinav Kandala, and Temme had scaled PEC to superconducting processors via sparse Pauli–Lindblad noise learning, and the review by Zhenyu Cai and collaborators placed it alongside zero-noise extrapolation as one of the two rigorously grounded mitigation methods — the exact, expensive one against the cheap, biased one.

History

2017

— Temme, Bravyi and Gambetta introduce probabilistic error cancellation via quasiprobability sampling

2018

— Endo, Benjamin and Li build a practical gate-set quasiprobability construction and hybrid schemes

2019

— Kandala and collaborators extend the computational reach of a noisy superconducting processor with error mitigation

2023

— van den Berg, Minev, Kandala and Temme scale PEC using learned sparse Pauli–Lindblad noise models

2023

— Cai and collaborators publish a comprehensive review of quantum error mitigation

Going further

References. Temme, Bravyi and Gambetta, "Error mitigation for short-depth quantum circuits", Phys. Rev. Lett. 119, 180509 (2017) · Endo, Benjamin and Li, "Practical quantum error mitigation for near-future applications", Phys. Rev. X 8, 031027 (2018) · van den Berg, Minev, Kandala and Temme, "Probabilistic error cancellation with sparse Pauli–Lindblad models", Nat. Phys. 19, 1116 (2023) · Cai et al., "Quantum error mitigation", Rev. Mod. Phys. 95, 045005 (2023) · Nielsen and Chuang, Quantum Computation and Quantum Information (2010), Ch. 8 · Watrous, The Theory of Quantum Information (2018), Ch. 2.

Provenance. The unbiasedness proof and the identity $p_i\,\gamma\,\mathrm{sgn}(c_i)=c_i$ follow Temme–Bravyi–Gambetta (2017) and Endo–Benjamin–Li (2018). The depolarizing coefficients and overhead are derived here from scratch in the Nielsen–Chuang convention $\mathcal{D}_p(\rho)=(1-p)\rho+p\,I/2$ : eigenvalue $1-p$ on the Paulis, $c_{\mathcal{I}}=(4-p)/[4(1-p)]$ , $c_{X,Y,Z}=-p/[4(1-p)]$ , $\sum_i c_i=1$ , $\gamma=(1+p/2)/(1-p)$ diverging at $p=1$ . The alternative $\mathcal{D}_p(\rho)=(1-p)\rho+\tfrac{p}{3}\sum_{P\neq I}P\rho P$ has eigenvalue $1-\tfrac{4p}{3}$ and diverges at $p=3/4$ ; the two must not be mixed. A verifier should confirm the CP/unitarity argument forcing at least one $c_i<0$ (Watrous Ch. 2, Nielsen–Chuang Ch. 8), the coefficients giving $\gamma=2.0$ at $p=0.4$ , and $1.02^{100}\approx7.24$ with $\gamma_{\mathrm{tot}}^2\approx52$ .

Prerequisites. CPTP Maps and Quantum Operations · Kraus Representation · Pauli and Bit/Phase-Flip Channels · Depolarizing Channel · Lindblad / GKSL Master Equation. Leads to. Zero-Noise Extrapolation · Quantum Error Correction · Markovian vs Non-Markovian Dynamics.

Ask the tutor: Ask me to walk through building the quasiprobability decomposition for your own noise channel, or to work out exactly where the exponential sampling wall stops your circuit.

If the inverse of the noise cannot be run on the machine, what exactly does the hardware do?

The hardware only ever runs physically legal circuits — the noisy gate followed by one implementable operation $\mathcal{O}_i$ (a Pauli, a Clifford, sometimes a reset). The impossible part, the inversion, lives entirely in software: after each run you look up which $\mathcal{O}_i$ was inserted, multiply the outcome by $\gamma\,\mathrm{sgn}(c_i)$ , and add it to a running average. The negative signs and the factor $\gamma>1$ are numbers in a spreadsheet, not settings on the device — an operation forbidden as a channel is perfectly legal as a post-processing rule on already-collected data.

Is PEC a form of quantum error correction?

No, and the distinction matters. Error correction protects a quantum state in real time using redundant qubits and syndrome measurements, so a corrected computation runs to arbitrary depth. PEC touches no state and adds no qubits; it recovers only expectation values, as a statistical average over many runs, and pays a cost exponential in circuit size — whereas fault-tolerant correction costs only polynomially once below threshold. PEC is a near-term mitigation that stretches what uncorrected hardware can measure accurately; correction is the long-term architecture that removes the depth limit altogether.

Why is PEC called unbiased when its results are so noisy?

"Unbiased" and "low-variance" are different virtues. Unbiased means the estimator's expected value is exactly the ideal answer — average enough runs and you converge with no systematic offset. High-variance means any finite sample scatters widely around that truth. PEC deliberately trades one for the other: it removes the systematic bias of the noise channel and pays in variance, inflating the shot count by $\gamma^2$ per gate. That is a good trade when you can afford the shots, since variance shrinks as $1/M$ while bias would never shrink — provided the noise model is correct.

Where do the negative quasiprobabilities come from, physically?

They are the fingerprint of irreversibility. A noisy channel loses information to its environment, and no physical operation can pull it back — the data-processing inequality forbids it. So the map that would undo the noise cannot itself be a channel, and the only way to write a non-channel as a combination of channels is to allow negative weights. Their size, $\gamma-1$ , measures how much information was scrambled: weak noise gives tiny negatives and $\gamma\approx1$ , while a channel that erases the qubit drives $\gamma$ to infinity. The same negativity marks non-classicality in Wigner functions and the fermionic sign problem.

Why does the reported overhead formula differ between textbooks?

Because the depolarizing channel has two common parametrizations that define $p$ differently. Here, $\mathcal{D}_p(\rho)=(1-p)\rho+p\,I/2$ : $p$ is the probability of full depolarization, the Pauli eigenvalue is $1-p$ , and $\gamma=(1+p/2)/(1-p)$ diverges at $p=1$ . In the alternative $\mathcal{D}_p(\rho)=(1-p)\rho+\tfrac{p}{3}\sum_{P\neq I}P\rho P$ , the eigenvalue is $1-\tfrac{4p}{3}$ and the channel is singular already at $p=3/4$ . Both are correct, related by a rescaling of $p$ . The one fatal mistake — which careful sources still make — is to write the channel in one convention and quote the overhead from the other.

Can PEC be combined with zero-noise extrapolation, and why would you?

Yes, and the combination often beats either alone. Their weaknesses are complementary: PEC is unbiased but its cost $\gamma_{\mathrm{tot}}^2$ explodes with depth, while zero-noise extrapolation is cheap but biased by its extrapolation model. A hybrid pipeline uses partial PEC to invert only the most damaging noise — the two-qubit-gate errors — lowering the effective error rate, then extrapolates the residual. Because only part of the noise was inverted, $\gamma$ stays small and the shot budget manageable — a deliberate slide along the bias–variance–cost trade-off, tuned to the machine at hand.