← 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 is a node. An error chain flips the stabilizers at its two ends, so the syndrome appears as a sparse set of defects sitting at the endpoints of invisible chains. The decoder's job is to guess a chain set with the same endpoints: it builds a weighted graph on the defects (weight = lattice distance), then finds the minimum-weight perfect matching, the pairing of least total length. Because a chain may also terminate on a boundary, every defect additionally gets the option of matching to the nearest boundary. Watch every distance, every candidate pairing and every correction path get drawn, step by step.

Matching graph  G  · circles = stabilizers, lines = data qubits, bars = boundaries
red = error chain · yellow = correction · teal arc = matched pair
error $E$ correction $C$ $E \oplus C$ cancelled defect $s_v=1$ quiet stabilizer
0 / 0
Sample an error to begin.

1 · Build the instance

5
0.06

2 · Run the decoder

Syndrome defects $\partial E$

A stabilizer fires when an odd number of its incident qubits carry an error, so a chain is invisible except at its two endpoints. The syndrome is exactly the boundary $\partial E$ of the error chain.

Matching graph weights $w(u,v)$

Complete graph on the defects. $w(u,v)$ is the lattice distance (shortest chain joining them), 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 of the code instead of pairing up.

Step log