Simple Algorithm
Quantum Computing · Rydberg State · 32 min

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 pL∝(p/pth)(d+1)/2p_L\propto(p/p_{\mathrm{th}})^{(d+1)/2}, and the reported below-threshold experiments.

From syndromes to corrections

Fix a stabilizer code and a noise model Pr⁡(E)\Pr(E) on Paulis. After measuring the syndrome s=s(E)s=s(E), the decoder outputs a correction CC with s(C)=ss(C)=s. Then CECE has trivial syndrome, so it lies in N(S)\mathcal{N}(\mathcal{S}): the decoder succeeds if CE∈SCE\in\mathcal{S} and fails if CECE is a non-trivial logical operator. Only the logical class of CC 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 XX and ZZ errors, each with probability pp, and perfect syndrome measurements (code-capacity noise). The two error types are detected by different checks and can be decoded separately, so focus on XX errors and the ZZ-type checks.

DerivationMinimum weight = minimum-weight perfect matching
  1. Pr⁡(E) ∝ (p1−p)∣E∣\Pr(E)\ \propto\ \Big(\frac{p}{1-p}\Big)^{\abs{E}}

    For i.i.d. noise the most likely error is the smallest edge set with ∂E=s\partial E=s.

  2. A minimal such EE 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.

  3. w(u,v)=dist⁡(u,v),w(u,u′)=dist⁡(u,boundary)w(u,v) = \operatorname{dist}(u,v),\qquad w(u,u') = \operatorname{dist}(u,\text{boundary})

    Build a complete graph on the defects with shortest-path weights. Give each defect uu a boundary twin u′u', and join all twins to each other at zero cost, so that any number of defects can be matched to the boundary.

  4. 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 d→∞d\to\infty? The cleanest proof is a Peierls-type counting argument in the spirit of Dennis, Kitaev, Landahl and Preskill (2002).

DerivationProof (Peierls argument)
  1. Failure needs a long chain. If the decoder fails, E⊕CE\oplus C (as edge sets) has no syndrome and contains a path γ\gamma joining the top and bottom boundaries. Such a path has length ℓ≥d\ell\ge d.

  2. ∣E∩γ∣ ≥ ℓ2\abs{E\cap\gamma}\ \ge\ \tfrac{\ell}{2}

    At least half of γ\gamma is error. Each edge of γ\gamma lies in exactly one of EE and CC. If ∣E∩γ∣<ℓ/2\abs{E\cap\gamma}<\ell/2, then C′=C⊕γC'=C\oplus\gamma has the same syndrome and weight ∣C∣−∣C∩γ∣+∣E∩γ∣<∣C∣\abs{C}-\abs{C\cap\gamma}+\abs{E\cap\gamma}<\abs{C}, contradicting minimality.

  3. Pr⁡[∣E∩γ∣≥ℓ2] ≤ 2ℓ pℓ/2=(2p)ℓ\Pr\big[\abs{E\cap\gamma}\ge\tfrac{\ell}{2}\big]\ \le\ 2^{\ell}\,p^{\ell/2} = (2\sqrt{p})^{\ell}

    A fixed path is unlikely. Union bound over the at most 2ℓ2^{\ell} subsets of γ\gamma of size ⌈ℓ/2⌉\lceil\ell/2\rceil, each entirely erroneous with probability p⌈ℓ/2⌉≤pℓ/2p^{\lceil\ell/2\rceil}\le p^{\ell/2}.

  4. #{γ: ∣γ∣=ℓ} ≤ O(d)⋅4⋅3ℓ−1\#\{\gamma:\ \abs{\gamma}=\ell\}\ \le\ \order{d}\cdot 4\cdot3^{\ell-1}

    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 O(d)\order{d} starting edges along the top boundary.

  5. Pfail ≤ ∑ℓ≥dO(d) (6p)ℓ=O(d) (6p)d1−6pP_{\mathrm{fail}}\ \le\ \sum_{\ell\ge d}\order{d}\,(6\sqrt{p})^{\ell} = \order{d}\,\frac{(6\sqrt{p})^{d}}{1-6\sqrt{p}}

    Sum the geometric series, which converges for 6p<16\sqrt{p}<1. Counting self-avoiding walks with the connective constant μ≈2.64\mu\approx2.64 of the square lattice instead of 3 improves the bound to p<1/(4μ2)≈3.6%p<1/(4\mu^2)\approx3.6\%. □\square

The bound is crude: the true threshold of matching is about 10.3%10.3\%. 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.

DerivationFrom error classes to the random-bond Ising model
  1. Equivalent XX errors differ by XX-type stabilizers. Put an Ising spin σv=±1\sigma_v=\pm1 on each XX-type check vv, with σv=−1\sigma_v=-1 meaning "multiply by this check". A data qubit ee in checks uu and vv is flipped by the product exactly when σuσv=−1\sigma_u\sigma_v=-1 (a boundary qubit couples to one fixed boundary spin).

  2. Pr⁡(E⋅Sσ) ∝ ∏e=⟨uv⟩(p1−p)1−ηeσuσv2,ηe={−1e∈E+1e∉E\Pr(E\cdot S_\sigma)\ \propto\ \prod_{e=\langle uv\rangle}\Big(\frac{p}{1-p}\Big)^{\frac{1-\eta_e\sigma_u\sigma_v}{2}},\qquad \eta_e = \begin{cases}-1 & e\in E\\ +1 & e\notin E\end{cases}

    Qubit ee is in error in E⋅SσE\cdot S_\sigma if and only if ηeσuσv=−1\eta_e\sigma_u\sigma_v=-1.

  3. Pr⁡(class of E) ∝ Z(K,η)=∑σexp⁡(K∑⟨uv⟩ηuv σuσv),e−2K=p1−p\Pr(\text{class of }E)\ \propto\ Z(K,\eta)=\sum_{\sigma}\exp\Big(K\sum_{\langle uv\rangle}\eta_{uv}\,\sigma_u\sigma_v\Big),\qquad e^{-2K}=\frac{p}{1-p}

    Up to an η\eta-independent factor this is the partition function of the random-bond Ising model: ferromagnetic bonds, each flipped to antiferromagnetic independently with probability pp. The coupling is tied to the disorder by e−2K=p/(1−p)e^{-2K}=p/(1-p): the Nishimori line.

  4. Pr⁡(class of EXˉ)Pr⁡(class of E)=Z(K,η′)Z(K,η)=e−ΔF\frac{\Pr(\text{class of }E\bar X)}{\Pr(\text{class of }E)} = \frac{Z(K,\eta')}{Z(K,\eta)} = e^{-\Delta F}

    Multiplying by Xˉ\bar X flips the bonds along a boundary-to-boundary line: it inserts a domain wall of free-energy cost ΔF\Delta F. In the ordered (ferromagnetic) phase ΔF\Delta F grows like dd, 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, pc≈10.9%p_c\approx10.9\%.

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 10.3%10.3\%. Noisy syndrome measurements add a time dimension and map to a 3D random-plaquette Z2\mathbb{Z}_2 gauge theory (Wang, Harrington & Preskill, 2003).

Noise modelMatching thresholdOptimal threshold
Code capacity: independent XX/ZZ, perfect syndromes≈10.3%\approx10.3\%≈10.9%\approx10.9\% (Nishimori point of the 2D model)
Phenomenological: noisy qubits and noisy syndrome bits≈2.9%\approx2.9\%≈3.3%\approx3.3\% (3D random-plaquette gauge model)
Circuit level: every gate, preparation and measurement noisy≈0.5\approx0.5–1%1\%not known exactly
Approximate values for the surface code. Circuit-level numbers depend on the gate set, the CNOT schedule and the noise details.
Check your understanding

In the random-bond Ising mapping, what does the zero-temperature version of the model correspond to?

  1. Maximum-likelihood decoding
  2. Decoding with perfect knowledge of the error
  3. Minimum-weight decoding, which keeps only the most likely error and ignores the entropy of its class
  4. 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 T=0T=0 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 (≈10.9%\approx10.9\%) beats matching's (≈10.3%\approx10.3\%).

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 O(n α(n))\order{n\,\alpha(n)}, where α\alpha is the inverse Ackermann function (effectively constant), with a threshold only slightly below matching's.

With noisy measurements, repeat the syndrome round about dd 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 (YY errors, hook errors) add diagonal edges.

Check your understanding

Take Λ≈2.14\Lambda\approx2.14 and pL(d=7)≈1.4×10−3p_L(d=7)\approx1.4\times10^{-3} per cycle. If the scaling continued, roughly what distance would a memory with 10−610^{-6} error per cycle need?

  1. d≈27d\approx27
  2. d≈11d\approx11
  3. d≈15d\approx15
  4. d≈101d\approx101
Show the answer

A. d≈27d\approx27

You need a factor of about 14001400. Each step of +2+2 gives 2.142.14, and ln⁡1400/ln⁡2.14≈9.5\ln1400/\ln2.14\approx9.5, so about 10 steps: d≈7+20=27d\approx7+20=27, roughly 2⋅272≈15002\cdot27^2\approx1500 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 2.8%2.8\% for code-capacity noise; the random-bond Ising mapping gives ≈10.3%\approx10.3\% for matching (T=0T=0) and ≈10.9%\approx10.9\% for optimal decoding (Nishimori point).
  • With noisy syndromes decoding is three-dimensional; circuit-level thresholds are ≈0.5\approx0.5–1%1\%, and below threshold pL∝(p/pth)(d+1)/2p_L\propto(p/p_{\mathrm{th}})^{(d+1)/2}.
  • Experiments now report Λ≈2\Lambda\approx2 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.

Question 1

Why does minimum-weight decoding of the surface code reduce to perfect matching?

  1. Because the surface code is a classical code
  2. Because defects are the endpoints of error chains, so a lightest correction pairs defects (or sends them to a boundary) along shortest paths
  3. Because every error has weight one
  4. 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 XX 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.

Question 2

When can maximum-likelihood decoding beat minimum-weight decoding?

  1. Never: for i.i.d. noise they always agree
  2. Only when the syndrome is trivial
  3. Only for non-degenerate codes
  4. 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, ∑SPr⁡(CLˉS)\sum_S\Pr(C\bar LS). Degenerate codes such as the surface code have many equivalent errors, so class probabilities can disagree with the lightest error.

Question 3

In the Peierls argument, why must at least half of a failing chain γ\gamma consist of actual errors?

  1. Otherwise flipping the correction along γ\gamma would give a lighter correction with the same syndrome, contradicting minimality
  2. Because errors always come in pairs
  3. Because the decoder knows the error locations
  4. Because γ\gamma has length exactly dd
Show the answer

A. Otherwise flipping the correction along γ\gamma would give a lighter correction with the same syndrome, contradicting minimality

γ\gamma has no syndrome, so C⊕γC\oplus\gamma is also a valid correction, with weight ∣C∣−∣C∩γ∣+∣E∩γ∣\abs{C}-\abs{C\cap\gamma}+\abs{E\cap\gamma}. Minimality of CC forces ∣E∩γ∣≥∣C∩γ∣\abs{E\cap\gamma}\ge\abs{C\cap\gamma}, i.e. at least ℓ/2\ell/2.

Question 4

A memory has Λ=2\Lambda=2. By what factor does pLp_L drop from d=7d=7 to d=15d=15?

  1. 22
  2. 88
  3. 1616
  4. 256256
Show the answer

C. 1616

7→157\to15 is four steps of +2+2, each dividing pLp_L by Λ=2\Lambda=2: 24=162^4=16.

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).