Decoding and Matching

Measuring the stabilizers yields a syndrome — the set of checks that read $-1$ . The decoder must turn that syndrome into a recovery operation that returns the system to the code space without applying a logical error. For surface codes the canonical algorithm is minimum-weight perfect matching (MWPM), which exploits the fact that errors create anyons in pairs. This lesson explains how decoding becomes a graph-matching problem and why minimizing weight maximizes the success probability.

Syndromes are pairs of anyons

A connected $Z$ -error string lights up the two star checks at its endpoints; an $X$ -error string lights up the two plaquette checks at its endpoints. So a syndrome is a set of excited checks — a set of anyons — and (away from boundaries) they always come in even number, because every error string has two ends. The decoder's job is to guess error strings whose endpoints reproduce exactly the observed excited checks.

Crucially, the two anyon species decouple: $X$ -errors (flux $m$ ) and $Z$ -errors (charge $e$ ) are decoded on two independent graphs, each handling one Pauli type.

The matching graph

Build a graph for one species:

Nodes = the excited checks of that type (the detected anyons), plus virtual boundary nodes on a planar patch where a string may terminate.
Edges connect every pair of nodes, weighted by the length of the shortest error chain that would connect them on the lattice (the lattice distance between the two checks).

Any error consistent with the syndrome corresponds to pairing up the excited checks into strings — a perfect matching of the graph. The total weight of a matching is the total length of the error chains, i.e. the number of single-qubit errors invoked.

Why minimum weight

Assume independent depolarizing-like noise where each qubit errs with small probability $p$ . An error configuration of weight $w$ has probability proportional to

P(\text{config}) \;\propto\; p^{\,w}(1-p)^{\,n-w} \;=\; (1-p)^n \left(\frac{p}{1-p}\right)^{w}.

For $p < 1/2$ the factor $p/(1-p) < 1$ , so probability decreases monotonically with weight. Among all error patterns producing the observed syndrome, the lowest-weight one is the most likely. Finding it is precisely minimum-weight perfect matching — solvable exactly in polynomial time by Edmonds' blossom algorithm.

Success, failure, and homology

A decoder succeeds when the recovery string, combined with the true error, forms a contractible loop — a product of stabilizers — returning the state to its original logical value. It fails when the combined string is noncontractible: then a logical operator has been silently applied. This is why failure requires the actual error plus the guessed correction to span the system, an event needing roughly $d/2$ errors. The decoder is the bridge between the geometric distance and the operational error suppression quantified by the threshold, which is next.

The decoding loop in practice

Measure all stabilizers, repeatedly in time to handle measurement errors (a 3D matching graph).
Separate $X$ -type and $Z$ -type excited checks.
Build each matching graph with shortest-path edge weights.
Run MWPM to pair anyons.
Apply the implied recovery (or, more commonly, just track it in software via a Pauli frame).

Fast, local syndrome extraction plus efficient matching is what makes the surface code a practical fault-tolerant memory rather than a theoretical curiosity.