Decoders

A quantum error-correction decoder uses measured checks and a noise model to choose a recovery. It usually cannot determine the microscopic fault uniquely, and it does not need to. Errors differing by a stabilizer act identically on the code; errors differing by a logical operator can produce the same syndrome but require different recoveries.

The central task is therefore inference about logical classes. We will distinguish that task from finding a single likely error, explain how noisy measurement histories enter, and compare matching, message passing and class-summing methods. A decoder must also return useful decisions on the timescale required by the computation.

Required background. Why Quantum Error Correction Is Possible explains recovery conditions; Stabilizer Formalism defines syndromes and logical Paulis. Syndrome Measurement develops repeated outcomes and detector boundaries, while Surface Code supplies a geometric example.

Decoding is logical-class inference

First assume a stabilizer code, stochastic Pauli errors, and an exactly measured syndrome $s$. Let $\mathcal S$ be the stabilizer group. Choose a reference Pauli $T_s$ with that syndrome. Every compatible Pauli has, up to overall phase, the form

$$E=T_sL_\ell S,\qquad S\in\mathcal S,$$

where $L_\ell$ is a representative logical Pauli. An $[[n,k,d]]$ code has $4^k$ such logical classes for each syndrome. The syndrome fixes the commutation signs with checks, but not the logical label $\ell$.

The class weight is

$$W_\ell(s)=\sum_{S\in\mathcal S}\Pr(T_sL_\ell S).$$

Normalize by $\sum_jW_j(s)$ to obtain the posterior probability of each class. Choosing the largest class weight maximizes the chance of a successful Pauli recovery under this model. If $\widehat E$ is the chosen representative, applying $\widehat E^\dagger$ succeeds when $\widehat E^\dagger E$ is a stabilizer, up to phase.

This is often called maximum-likelihood logical decoding. More precisely, it maximizes a posterior incorporating the assumed fault prior. It differs from choosing the single most probable physical error. Bravyi, Suchara, and Vargo (2014) develop class-based decoding algorithms for surface codes.

A concrete degeneracy example

Consider the two-qubit code spanned by $|00\rangle,|11\rangle$, with check $Z_1Z_2$ and logical $X_L=X_1X_2$. It is an illustrative inference problem, not a code correcting arbitrary one-qubit faults. Suppose a Pauli channel assigns the following probabilities, with the remaining probability $0.29$ assigned to identity:

Error	Probability	Odd-syndrome class
$X_1$	0.30	A
$Y_1Z_2$	0.01	A
$X_2$	0.20	B
$Z_1Y_2$	0.20	B

Within each class, the two errors differ by the stabilizer up to phase. Between classes they differ by logical $X$. The most probable individual error is $X_1$, but class B has total probability $0.40$, exceeding class A’s $0.31$. Conditional on the odd syndrome, correcting class B succeeds with probability $40/71\simeq0.563$, whereas correcting A succeeds with $31/71\simeq0.437$.

Reconstructing the physical error more accurately is not always the same as protecting the logical state more accurately. The sum over stabilizer-equivalent alternatives is the useful feature of quantum degeneracy.

Nonuniform noise can favor a heavier error

For the Three-Qubit Code with checks $Z_1Z_2,Z_2Z_3$, restrict the channel to independent bit flips of probabilities $p_1,p_2,p_3$. Syndrome $(1,0)$ permits exactly two bit patterns: $X_1$ and $X_2X_3$. Their probabilities are

$$\begin{aligned} P_1&=p_1(1-p_2)(1-p_3),\\ P_{23}&=(1-p_1)p_2p_3. \end{aligned}$$

Equal probabilities $p_i=p<1/2$ favor the weight-one explanation. But if qubit 1 is much cleaner than the other two, the weight-two explanation can win. Minimum Hamming weight is justified by a particular prior; it is not the definition of decoding.

Noisy records require histories of faults

With imperfect measurements, the observed bits need not equal the true data-error syndrome. It is then incorrect to restrict inference to data errors having that observed syndrome as though it were exact.

Instead, let $f$ label a complete modeled history, including data faults and measurement faults. Let $y$ be the observed record, and let $\ell(f)$ denote the logical effect relative to a fixed reference correction and final logical readout convention. The posterior is

$$\Pr(\ell\mid y)\propto \sum_{f:\,\ell(f)=\ell}\Pr(y\mid f)\Pr(f).$$

An exact observation imposes a hard constraint on this sum; a noisy observation supplies a likelihood. The model must specify which preparation, intermediate and final measurements are available. An offline decoder seeing the final boundary has more information than a streaming decoder asked to decide earlier.

Repeated checks are often converted to detectors: parities of measurement outcomes that are deterministic without faults. In a simple bulk region,

$$d_a(t)=m_a(t)\oplus m_a(t-1).$$

A wrong readout bit usually creates two adjacent time changes; a persistent data error can change the underlying syndrome. Initial and terminal detectors require their own boundary definitions. The derivation belongs to the extraction circuit, rather than to a generic difference formula applied everywhere.

For binary elementary faults collected in a vector $f$, a detector model can be written

$$d=Hf,\qquad \ell=\Lambda f,$$

over $\mathbb F_2$. Each column specifies the detectors and tracked logical observables flipped by one mechanism. Two histories can have identical $Hf$ and different $\Lambda f$, which is precisely the ambiguity the decoder must resolve. Independent Bernoulli faults are one convenient model; mutually exclusive Pauli outcomes, bursts and persistent leakage need more care.

Hard and soft information

A hard decoder receives thresholded bits. A soft decoder also uses reliability information, such as analog voltages, erasure flags or GKP residues. Suppose a readout value has distributions $r\mid s=0\sim\mathcal N(+1,\nu^2)$ and $r\mid s=1\sim\mathcal N(-1,\nu^2)$. Its likelihood ratio is

$$\log\frac{p(r\mid s=0)}{p(r\mid s=1)}=\frac{2r}{\nu^2}.$$

The posterior log odds also include the prior log odds of the two hypotheses. Replacing $r$ by its sign discards how reliable the outcome was. Soft information helps only if its likelihood model is calibrated; an underestimated variance makes the decoder overconfident.

Code-capacity studies assume perfect checks and noisy data. Phenomenological studies add prescribed readout errors without a complete gate circuit. Circuit-level studies propagate faults through preparation, gates, idles and measurement. These answer different questions; a threshold or runtime from one model should not be transferred to another without its assumptions.

Matching and clustering on a detector graph

When every modeled elementary fault flips at most two detectors, it can be represented as an edge between them, or between one detector and a boundary. Faults with no detector flips can still carry a logical effect and must remain in the model. A fault flipping three or more detectors is a hyperedge; replacing it with unrelated pair faults can change the posterior.

For independent Bernoulli edges, a candidate set $F$ has probability

$$\Pr(F)=\prod_{e\in F}p_e\prod_{e\notin F}(1-p_e).$$

Factoring out $\prod_e(1-p_e)$ gives additive negative-log weights

$$w_e=\log\frac{1-p_e}{p_e}.$$

Thus minimizing the sum of selected weights finds a most probable fault configuration under these assumptions. It does not sum the probabilities of all configurations in a logical class. Geometric path length is equivalent only when the relevant step probabilities are uniform.

Minimum-weight perfect matching pairs observed detection events with one another or permitted boundaries, using shortest-path weights from the detector graph. The recovered paths give a compatible correction. Sparse implementations work directly with the sparse graph rather than explicitly constructing every pair distance; Higgott and Gidney (2025) describe sparse blossom. Correlated matching can retain additional relations between fault types, but ordinary graph matching does not exactly represent arbitrary hyperedges or class sums.

Weights can be negative when $p_e>1/2$. This need not invalidate the probability model. Replacing that fault variable by its complement gives probability $1-p_e<1/2$, while shifting the reference detector pattern and logical effect. A solver must handle those offsets consistently, rather than silently replacing the weight by its absolute value.

Union–find decoding grows and merges syndrome clusters until local parity or boundary conditions permit a correction, then uses a forest-peeling step. Delfosse and Nickerson (2021) prove an almost-linear $O(n\alpha(n))$ bound for their specified topological-code decoder; $\alpha$ is the inverse Ackermann function. That result is not a blanket runtime bound for every weighted or circuit-level variant. Growth rules, boundaries and fault correlations still affect accuracy.

Known erasure locations can make the problem simpler: a correction can be sought only on the flagged support. Exact correction of all errors on that support is possible when it contains no nontrivial logical operator. A false flag and a missed flag have different consequences, so a noisy flag is information to combine with the model, not an infallible statement.

Message passing, joint decisions and class sums

For binary parity constraints $He=s$, belief propagation (BP) passes log-likelihood messages on the variable–check graph. A variable starts with prior

$$L_i=\log\frac{\Pr(e_i=0)}{\Pr(e_i=1)}.$$

Its message to check $a$ adds incoming messages from the other checks:

$$L_{i\to a}=L_i+\sum_{b\in\mathcal N(i)\setminus a}L_{b\to i}.$$

The message from check $a$ to variable $i$ is

$$L_{a\to i} =2\operatorname{atanh}\!\left[ (-1)^{s_a} \prod_{j\in\mathcal N(a)\setminus i}\tanh(L_{j\to a}/2) \right].$$

A positive message favors zero, and a negative one favors one. On a tree with the stated factorized prior, sum-product BP computes exact single-variable marginals. Quantum-code graphs commonly have loops and degeneracy that complicate convergence; Poulin and Chung (2008) analyze these difficulties.

Even exact marginals need not form a valid error word

Consider just one check $e_1\oplus e_2\oplus e_3=1$, with independent priors $\Pr(e_i=1)=0.1$. The posterior gives the three single-error words equal probability $81/244\simeq0.332$, and word $111$ probability $1/244$. Each marginal is

$$\Pr(e_i=1\mid s=1)=\frac{82}{244}\simeq0.336.$$

Rounding all three marginals toward their more likely value gives $000$, which violates the measured check. There are no graph loops here: the problem is converting correct marginals into an inconsistent joint decision. A joint assignment must choose a compatible word, and a quantum decoder must also consider its logical class.

The check requires odd parity. Each bit individually is more likely to be zero, yet the all-zero word has posterior probability zero. The three single-error words are tied joint maxima. Correct local marginals are useful information, but they are not themselves a syndrome-consistent recovery.

BP with ordered-statistics decoding uses reliabilities to rank variables, solves an independent set of syndrome constraints, and searches selected changes to candidate assignments. It can repair an inconsistent BP output, though it does not generally compute the exact logical-class posterior. Roffe and collaborators (2020) study this approach across qLDPC examples. Iteration count, damping, search order and early stopping all affect its accuracy and runtime.

Tensor-network methods instead express class probabilities as sums over local fault variables. Approximate contraction controls the computational cost through parameters such as bond dimension. Renormalization methods combine local regions while passing effective probabilities between scales. They can retain degeneracy and correlations beyond a single-path approximation; finite approximation settings still need convergence checks. Chubb and Flammia (2021) develop statistical-mechanical formulations for correlated Pauli noise.

Learned decoders fit a map from measurement histories to decisions or class probabilities. They can use analog data and leakage indicators, as demonstrated by Bausch and collaborators (2024), but a numerical output between zero and one is not automatically a calibrated posterior. Calibration means that outcomes assigned a probability near $p$ occur with frequency near $p$ on suitable held-out data. Training and evaluation should be separated by independent runs when nearby shots share drift or hidden states.

Correlations and model mismatch

For CSS Codes, separate $X$- and $Z$-component decoding is convenient. A physical $Y$ error has both components, however, so their prior need not factorize. Joint Pauli messages, correlated matching or other joint methods can use information that independent decoders discard. Noise bias changes the appropriate weights, and persistent leakage can couple several successive rounds.

Detector means and pair correlations are helpful calibration statistics, but they do not determine a general joint distribution. For example, uniform distributions on the even-parity and odd-parity three-bit strings have the same individual means and pair correlations, yet opposite total parities. A model fitted only to pair statistics can miss precisely the higher-order feature relevant to a logical outcome.

The class-probability formulas also assume a stochastic fault model. Under coherent noise, amplitudes associated with the same measurement branch may interfere. Syndrome extraction does not automatically turn every coherent process into independent Pauli samples. Pauli Noise and Depolarizing Channels explains when a Pauli model is justified and what a twirling approximation discards.

Real-time decoding

Throughput is the rate at which completed work can be sustained. Latency is the time from a record becoming available to its usable decision. A pipeline can have high throughput and long latency simultaneously.

If $N$ bits arrive every cycle of duration $\tau$, the raw input rate is $N/\tau$. For a standard stationary single-server queue with arrival rate $\lambda$ and mean service time $\mathbb E[S]$, stable stochastic operation requires load $\rho=\lambda\mathbb E[S]<1$ under the usual queueing assumptions. This mean-load test alone gives no deadline guarantee. Acquisition, transport, boundary reconciliation and actuation also contribute to the delay.

A useful requirement is a bound on the probability of missing the actual adaptive deadline:

$$\Pr(T_{\rm decision}>T_{\rm deadline})\le\epsilon_{\rm late}.$$

For example, a stream arriving every microsecond can have mean service time $0.7$ microseconds yet occasionally require $2.5$ microseconds for one item. Its queue need not grow indefinitely, but a two-microsecond decision deadline can still fail.

Streaming decoders process new records incrementally. Windowed methods decode overlapping spacetime regions and delay decisions near uncertain boundaries. The overlap and commitment rule affect logical accuracy as well as latency. Receiving a final measurement can resolve an ambiguity that a shorter window could not.

Most inferred Pauli corrections can be tracked as a Pauli frame rather than physically applied. Clifford operations propagate that frame classically. This permits delayed decisions until an operation actually depends on them—for example, an adaptive non-Clifford measurement basis. Some surgery outcomes can likewise be tracked until their first dependent operation. There is no universal requirement to physically correct every cycle, nor unlimited freedom to postpone all inference.

To compare decoders, give them the same circuit, noise conditions and available measurements, then compare logical failure and timing on those same inputs. Count rejected runs and missing decisions as defined outcomes. A decoder with simulator-only fault labels is a reference bound, and an offline decoder can be an accuracy baseline without satisfying online deadlines. Logical Benchmarking develops uncertainty, acceptance and scaling comparisons.

Exercises

1. Recover the equivalence criterion

If two Paulis $E,E'$ have the same syndrome, why is $E'^\dagger E$ in the normalizer? When are they equivalent recoveries?

Solution

For each stabilizer generator, commuting through the product gives two identical signs, whose product is positive. The product therefore commutes with every check and belongs to the normalizer. If it is a stabilizer up to phase, it acts trivially on the encoded state. A nontrivial logical Pauli in the normalizer instead changes the encoded information despite preserving the syndrome.

2. Choose the heavier repetition-code explanation

For syndrome $(1,0)$, take $p_1=0.001$ and $p_2=p_3=0.1$. Which recovery is preferred, and what is its conditional success probability?

Solution

The probabilities are $P_1=0.00081$ and $P_{23}=0.00999$. Correcting $X_2X_3$ therefore succeeds conditionally with probability $0.00999/0.01080=0.925$. The weight-one correction succeeds only with probability $0.075$ under this prior. Both candidates satisfy the observed checks.

3. Normalize the degenerate class probabilities

Use the two-qubit channel above to compare the overall success probability of the single-error MAP decoder and the logical-class decoder, including the even syndrome.

Solution

Identity is the only supported even-syndrome event, with probability $0.29$. On the odd syndrome, single-error MAP chooses class A and succeeds on total probability $0.31$; class decoding chooses B and succeeds on total probability $0.40$. Their overall successes are therefore $0.60$ and $0.69$. Choosing class B need not identify whether $X_2$ or $Z_1Y_2$ happened, since their actions differ only by a stabilizer and overall phase.

4. Interpret a negative edge weight

An independent graph fault has $p=0.8$, detector column $h$ and logical column $l$. Replace its binary variable $f$ by $f'=1-f$. What changes besides the probability?

Solution

Now $\Pr(f'=1)=0.2$, so its weight is $\log4$ instead of $-\log4$. Over binary arithmetic $f=1\oplus f'$, giving $hf=h\oplus hf'$ and $lf=l\oplus lf'$. The observed detector pattern and reference logical label must therefore be offset by $h$ and $l$. Taking the absolute weight without these offsets solves a different inference problem.

5. Calculate the exact one-check marginals

For three independent bits of error probability $p=0.1$ conditioned on odd parity, derive the marginal $82/244$. Check the result with one BP update.

Solution

Odd parity has probability $3p(1-p)^2+p^3=0.244$. Bit 1 is one in the compatible words $100$ and $111$, with combined probability $p(1-p)^2+p^3=0.082$. Their ratio is $82/244$.

The prior LLR is $\log9$, with $\tanh(\log9/2)=0.8$. The odd check sends $-2\operatorname{atanh}(0.64)$, so the posterior LLR is

$$L=\log9-2\operatorname{atanh}(0.64).$$

Then $\Pr(e_1=1\mid s)=1/(1+e^L)=82/244$. By symmetry every bit has this marginal. Rounding them independently gives the forbidden word $000$; the exact marginals were not the mistake.

6. Find a deadline failure in a stable stream

Items arrive at times $0,1,2,\ldots$ microseconds. In every ten-item block, the first service takes $2.5$ microseconds and each other service takes $0.5$. A first-in-first-out server starts empty. Find the mean service time and the first four latencies. Does a two-microsecond deadline always pass?

Solution

The mean service time is $(2.5+9\times0.5)/10=0.7$ microseconds. The first completion times are $2.5,3.0,3.5,4.0$, giving latencies $2.5,2.0,1.5,1.0$. The queue subsequently clears before the next long item. Throughput is adequate, but one item in each block misses the two-microsecond deadline. A mean-speed statement would hide that failure.

7. Quantify a lost Pauli correlation

Let $(P_I,P_X,P_Y,P_Z)=(0.97,0.01,0.015,0.005)$. Compare the true probability of simultaneous binary components with a product-of-marginals model.

Solution

The two component probabilities are $P(x=1)=0.025$ and $P(z=1)=0.020$. Their product is $0.0005$, whereas the true joint probability is $P_Y=0.015$, thirty times larger. The covariance is $0.0145$. Treating the components independently changes the relative likelihoods of fault histories, even though it preserves both marginal error rates.

8. Show that pair statistics miss a logical feature

Compare the uniform distributions on $\{000,011,101,110\}$ and $\{001,010,100,111\}$. Calculate each bit mean, each distinct-pair product mean, and total parity.

Solution

In either distribution every bit is one in two of the four strings, so its mean is $1/2$. Every distinct pair is jointly one in exactly one string, so its product mean is $1/4$ and its covariance is zero. Yet total parity is always even in the first distribution and always odd in the second. A decoder whose logical label depends on this parity needs information that pair statistics alone do not supply.

References

• J. Bausch et al., “Learning high-accuracy error decoding for quantum processors,” Nature 635, 834–840 (2024), doi:10.1038/s41586-024-08148-8.
• S. Bravyi, M. Suchara, and A. Vargo, “Efficient algorithms for maximum likelihood decoding in the surface code,” Physical Review A 90, 032326 (2014), doi:10.1103/PhysRevA.90.032326, arXiv:1405.4883.
• C. T. Chubb and S. T. Flammia, “Statistical mechanical models for quantum codes with correlated noise,” Annales de l’Institut Henri Poincaré D 8, 269–321 (2021), doi:10.4171/AIHPD/105, arXiv:1809.10704.
• N. Delfosse and N. H. Nickerson, “Almost-linear time decoding algorithm for topological codes,” Quantum 5, 595 (2021), doi:10.22331/q-2021-12-02-595.
• O. Higgott and C. Gidney, “Sparse blossom: correcting a million errors per core second with minimum-weight matching,” Quantum 9, 1600 (2025), doi:10.22331/q-2025-01-20-1600, arXiv:2303.15933.
• D. Poulin and Y. Chung, “On the iterative decoding of sparse quantum codes,” Quantum Information and Computation 8, 987–1000 (2008), doi:10.26421/QIC8.10-8, arXiv:0801.1241.
• J. Roffe, D. R. White, S. Burton, and E. Campbell, “Decoding across the quantum low-density parity-check code landscape,” Physical Review Research 2, 043423 (2020), doi:10.1103/PhysRevResearch.2.043423, arXiv:2005.07016.