Surface Code Decoding & Thresholds
Matching decoders, thresholds and logical error rates.
A large surface code emits a fresh syndrome every microsecond. Turning that stream into corrections, fast and nearly optimally, is the decoding problem. Its solution ties together graph matching, a Peierls counting argument, and the phase diagram of a disordered magnet.
What you’ll learn
- Formulate minimum-weight and maximum-likelihood decoding, and explain why degeneracy makes them differ.
- Reduce surface-code decoding to minimum-weight perfect matching, and describe the union-find decoder and its almost-linear cost.
- Prove that a threshold exists with a Peierls counting argument, and map optimal decoding to the random-bond Ising model on the Nishimori line.
- Interpret circuit-level thresholds, the scaling , and the reported below-threshold experiments.
From syndromes to corrections
Fix a stabilizer code and a noise model on Paulis. After measuring the syndrome , the decoder outputs a correction with . Then has trivial syndrome, so it lies in : the decoder succeeds if and fails if is a non-trivial logical operator. Only the logical class of matters.
For general stabilizer codes exact MLD is intractable (#P-hard; Iyer & Poulin, 2015). The surface code is special: its geometry makes minimum-weight decoding efficient, and MLD can be approximated well by tensor-network contraction (Bravyi, Suchara & Vargo, 2014).
Take independent and errors, each with probability , and perfect syndrome measurements (code-capacity noise). The two error types are detected by different checks and can be decoded separately, so focus on errors and the -type checks.
For i.i.d. noise the most likely error is the smallest edge set with .
A minimal such splits into edge-disjoint paths, each joining two defects (lit checks) or a defect to the boundary; any leftover cycle could be deleted to lower the weight.
Build a complete graph on the defects with shortest-path weights. Give each defect a boundary twin , and join all twins to each other at zero cost, so that any number of defects can be matched to the boundary.
A minimum-weight perfect matching of this graph, with every matched pair replaced by a shortest path, is a minimum-weight correction. Edmonds' blossom algorithm (1965) finds it in polynomial time, and modern implementations such as sparse blossom (Higgott & Gidney, 2023) run in nearly linear time on typical syndromes.
Why a threshold exists
Does matching keep working as ? The cleanest proof is a Peierls-type counting argument in the spirit of Dennis, Kitaev, Landahl and Preskill (2002).
Failure needs a long chain. If the decoder fails, (as edge sets) has no syndrome and contains a path joining the top and bottom boundaries. Such a path has length .
At least half of is error. Each edge of lies in exactly one of and . If , then has the same syndrome and weight , contradicting minimality.
A fixed path is unlikely. Union bound over the at most subsets of of size , each entirely erroneous with probability .
There are few paths. A self-avoiding walk on a graph of degree at most 4 has at most 3 choices per step after the first, and there are starting edges along the top boundary.
Sum the geometric series, which converges for . Counting self-avoiding walks with the connective constant of the square lattice instead of 3 improves the bound to .
The bound is crude: the true threshold of matching is about . Pinning it down requires statistical mechanics.
Decoding as a disordered magnet
Optimal decoding sums over all errors in a logical class, and that sum is a partition function.
Equivalent errors differ by -type stabilizers. Put an Ising spin on each -type check , with meaning "multiply by this check". A data qubit in checks and is flipped by the product exactly when (a boundary qubit couples to one fixed boundary spin).
Qubit is in error in if and only if .
Up to an -independent factor this is the partition function of the random-bond Ising model: ferromagnetic bonds, each flipped to antiferromagnetic independently with probability . The coupling is tied to the disorder by : the Nishimori line.
Multiplying by flips the bonds along a boundary-to-boundary line: it inserts a domain wall of free-energy cost . In the ordered (ferromagnetic) phase grows like , so the wrong class is exponentially suppressed and MLD succeeds; in the disordered phase it does not. The optimal threshold is the critical point on the Nishimori line, .
Minimum-weight matching ignores the entropy of equivalent errors: it corresponds to the same model at zero temperature, whose ordering transition gives the matching threshold of about . Noisy syndrome measurements add a time dimension and map to a 3D random-plaquette gauge theory (Wang, Harrington & Preskill, 2003).
| Noise model | Matching threshold | Optimal threshold |
|---|---|---|
| Code capacity: independent /, perfect syndromes | (Nishimori point of the 2D model) | |
| Phenomenological: noisy qubits and noisy syndrome bits | (3D random-plaquette gauge model) | |
| Circuit level: every gate, preparation and measurement noisy | – | not known exactly |
In the random-bond Ising mapping, what does the zero-temperature version of the model correspond to?
- Maximum-likelihood decoding
- Decoding with perfect knowledge of the error
- Minimum-weight decoding, which keeps only the most likely error and ignores the entropy of its class
- The noiseless code
Show the answer
C. Minimum-weight decoding, which keeps only the most likely error and ignores the entropy of its class
At the partition function is dominated by its ground state, the minimum-energy domain-wall configuration, which is what matching computes. MLD sums over all configurations at the Nishimori temperature, which is why its threshold () beats matching's ().
Fast decoders, space-time decoding and experiments
Union-find (Delfosse & Nickerson) trades a little accuracy for speed. Grow a cluster around each defect by half-edges; whenever clusters touch, merge them with a union-find data structure; stop growing a cluster once it contains an even number of defects or touches the boundary. Then take a spanning forest of each cluster and peel it from the leaves, choosing edges that pair up the defects inside. The total cost is , where is the inverse Ackermann function (effectively constant), with a threshold only slightly below matching's.
With noisy measurements, repeat the syndrome round about times and compare consecutive rounds: a detection event is a check whose value changed. A data error creates two space-like neighboring events; a measurement error creates two time-like events on the same check. Matching and union-find work unchanged on this 3D graph, and correlated faults ( errors, hook errors) add diagonal edges.
Take and per cycle. If the scaling continued, roughly what distance would a memory with error per cycle need?
Show the answer
A.
You need a factor of about . Each step of gives , and , so about 10 steps: , roughly physical qubits.
Key takeaways
- Decoding succeeds when the correction differs from the error by a stabilizer. MLD maximizes the probability of the logical class; minimum-weight decoding maximizes that of a single error.
- For the surface code, minimum weight is minimum-weight perfect matching on the defect graph (Edmonds' blossom algorithm); union-find gives almost-linear time at a slightly lower threshold.
- A Peierls argument proves a threshold of at least for code-capacity noise; the random-bond Ising mapping gives for matching () and for optimal decoding (Nishimori point).
- With noisy syndromes decoding is three-dimensional; circuit-level thresholds are –, and below threshold .
- Experiments now report with real-time decoding; rare correlated events and decoder speed are the next bottlenecks.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Why does minimum-weight decoding of the surface code reduce to perfect matching?
- Because the surface code is a classical code
- Because defects are the endpoints of error chains, so a lightest correction pairs defects (or sends them to a boundary) along shortest paths
- Because every error has weight one
- Because matching computes the maximum-likelihood class
Show the answer
B. Because defects are the endpoints of error chains, so a lightest correction pairs defects (or sends them to a boundary) along shortest paths
Each error flips the checks at the two ends of its edge, so an error chain lights checks only at its endpoints. Minimizing total weight subject to a given set of endpoints is minimum-weight perfect matching on shortest-path distances.
When can maximum-likelihood decoding beat minimum-weight decoding?
- Never: for i.i.d. noise they always agree
- Only when the syndrome is trivial
- Only for non-degenerate codes
- When a logical class containing many slightly heavier errors is more probable than the class of the single lightest error
Show the answer
D. When a logical class containing many slightly heavier errors is more probable than the class of the single lightest error
MLD weighs whole classes, . Degenerate codes such as the surface code have many equivalent errors, so class probabilities can disagree with the lightest error.
In the Peierls argument, why must at least half of a failing chain consist of actual errors?
- Otherwise flipping the correction along would give a lighter correction with the same syndrome, contradicting minimality
- Because errors always come in pairs
- Because the decoder knows the error locations
- Because has length exactly
Show the answer
A. Otherwise flipping the correction along would give a lighter correction with the same syndrome, contradicting minimality
has no syndrome, so is also a valid correction, with weight . Minimality of forces , i.e. at least .
A memory has . By what factor does drop from to ?
Show the answer
C.
is four steps of , each dividing by : .
Further reading
- E. Dennis, A. Kitaev, A. Landahl & J. Preskill, "Topological quantum memory", J. Math. Phys. 43, 4452 (2002).
- C. Wang, J. Harrington & J. Preskill, "Confinement-Higgs transition in a disordered gauge theory and the accuracy threshold for quantum memory", Annals of Physics (2003).
- N. Delfosse & N. H. Nickerson, "Almost-linear time decoding algorithm for topological codes", Quantum (2021); arXiv preprint (2017).
- A. G. Fowler, M. Mariantoni, J. M. Martinis & A. N. Cleland, "Surface codes: Towards practical large-scale quantum computation", Phys. Rev. A 86, 032324 (2012).
- Google Quantum AI, "Suppressing quantum errors by scaling a surface code logical qubit", Nature 614, 676 (2023); and "Quantum error correction below the surface code threshold", Nature (2025).