← Back to Tools

Minimum-Weight Perfect Matching Decoder

The original surface-code decoder, from Dennis, Kitaev, Landahl and Preskill (2002). Each data qubit is an edge of the matching graph and each stabilizer a node. An error chain flips only the stabilizers at its ends, so the syndrome is a sparse set of defects. The decoder measures the lattice distance between every pair of defects and to the nearest boundary, then finds the minimum-weight perfect matching: the pairing of least total length, which is the most likely error. Here the matching is solved exactly with Edmonds' blossom algorithm, and a greedy baseline shows what goes wrong without it. Sample a seeded error, load a worked example, or tap qubits on the lattice to build your own.

circles = stabilizers · lines = data qubits · bars = boundaries · tap a qubit to flip it
Overlay
error $E$ correction $C$ in both: cancelled defect quiet stabilizer matched pair boundary escape
0 / 0
Sample an error to begin.

1 · Build the instance

5
0.06

Worked examples load a hand-built error

2 · Run the decoder

Syndrome defects $\partial E$

A stabilizer fires when an odd number of its qubits carry an error, so a chain is invisible except at its two ends. The syndrome is the boundary $\partial E$ of the error chain. A chain that ends on a left or right boundary leaves only one defect.

Matching graph weights $w(u,v)$

Complete graph on the defects. $w(u,v)$ is the lattice distance, the length of the shortest chain joining $u$ and $v$ inside the code, found by breadth-first search. The last column $b$ is each defect's distance to its nearest boundary: the cost of letting its chain run off the edge instead of pairing up.

Logical error rate Monte Carlo at this $d$ and $p$

Samples fresh errors at the current $d$ and $p$ (no forced error), decodes each with MWPM and with greedy, and counts logical failures. Compare distances at a fixed $p$: below threshold (about $0.10$ for this noise model and decoder) a larger $d$ fails less often.

Step log

What is being decoded

One stabilizer type of the unrotated planar surface code with distance $d$: $d(d-1)$ stabilizers on a $d \times (d-1)$ grid and $d^2 + (d-1)^2$ data qubits on the edges. Each qubit is flipped independently with probability $p$ (code-capacity noise, perfect measurements). Chains may end on the left or right boundary, where a logical operator of weight $d$ runs from one side to the other. Up to $t = \lfloor (d-1)/2 \rfloor$ errors are always corrected; heavier errors may or may not be.

Why minimum weight

An error pattern of weight $\ell$ has probability $p^{\ell}(1-p)^{n-\ell}$, so the most likely error consistent with the syndrome is the lightest one. With a uniform $p$ every edge costs the same, $\log\frac{1-p}{p}$, so minimising the length is the same as minimising $\sum_e \log\frac{1-p_e}{p_e}$; non-uniform noise simply changes the edge weights. MWPM picks the most likely error, not the most likely class of errors, which is why it is slightly worse than an optimal (degeneracy-aware) decoder.

Boundaries and the blossom algorithm

With $k$ defects, add $k$ boundary copies: defect $u$ is joined to its copy at cost $b(u)$ and the copies are joined to each other at cost $0$. A minimum-weight perfect matching of these $2k$ nodes is exactly a minimum-weight matching in which any defect may instead escape to a boundary. Edmonds' blossom algorithm (1965) solves it exactly in polynomial time by a primal-dual method: grow a region around every unmatched defect, make an edge tight when two regions meet, and shrink odd cycles of tight edges into "blossoms" so that augmenting paths can be found. Modern decoders (Blossom V, PyMatching's sparse blossom, fusion blossom) use the same idea with local, sparse data structures.

References

  • E. Dennis, A. Kitaev, A. Landahl, J. Preskill, Topological quantum memory, J. Math. Phys. 43, 4452 (2002).
  • J. Edmonds, Paths, trees, and flowers, Canad. J. Math. 17, 449 (1965).
  • V. Kolmogorov, Blossom V, Math. Prog. Comp. 1, 43 (2009).
  • O. Higgott, C. Gidney, Sparse Blossom (PyMatching 2), Quantum 9, 1600 (2025).
  • Y. Wu, L. Zhong, Fusion Blossom (2023).