Minimum-Weight Perfect Matching
The standard surface-code decoder pairs syndrome defects with the lowest-total-weight set of error chains using graph matching.
Syndromes as a matching problem
In the surface code, a chain of like errors flips stabilizers only at its two endpoints, so each isolated error string shows up as a pair of syndrome defects. Decoding X errors and Z errors separately, the task becomes: given a set of defects, find the collection of error chains that produced them. Because defects come in pairs, this is a perfect matching problem on the graph of defects, where the edge weight between two defects is the length of the shortest error chain connecting them.
Minimum weight equals most likely
Under an independent Pauli error model, the probability of an error pattern decreases with its total weight, so the most likely explanation of the syndrome is the pairing that minimizes the sum of connecting chain lengths. That is exactly a minimum-weight perfect matching. Edmonds's blossom algorithm solves it in polynomial time, and boundary defects are handled by adding virtual nodes on the lattice edges so that chains can terminate at a boundary.
- Defects come in pairs at the ends of error chains.
- Build a graph: nodes are defects, edge weights are shortest-chain distances.
- Minimum-weight matching = most probable error under independent noise.
- Boundaries modeled by virtual nodes; blossom algorithm finds the matching.
Space-time and performance
Because measurements are noisy, matching is done over a three-dimensional space-time graph, with the extra dimension being repeated syndrome cycles; a measurement error creates a vertical defect pair in time, as discussed in measurement errors and repeated measurement. Matching gives the surface code a threshold near 1 percent. Its cost, however, grows with the number of defects, which motivates faster approximations such as the union-find decoder and highly optimized implementations that run in real time on classical hardware alongside the quantum chip.
Matching does not directly generalize to codes whose syndromes are not simple endpoints, such as color codes and general LDPC codes, which need other decoders.