Minimum-Weight Perfect Matching¶
Surface Codes ended with a real problem: several different error chains can produce the exact same detection information, and we may not be able to reconstruct exactly what happened.
Two separate errors landed on this patch. The syndrome tells us that something happened at four locations — but on its own, it doesn't tell us how to pair them up into a sensible explanation.
If several error patterns are compatible with what we observed, how should the decoder choose a recovery?
Minimum-Weight Perfect Matching (MWPM) is one systematic answer to that question.
Turn the Syndrome Into a Graph¶
To reason about this systematically, we step away from the lattice picture and build a decoding graph — a representation built from the syndrome, not the physical hardware itself:
- Node — a detection event (one of the checks that fired).
- Edge — a possible connection or error explanation between two detection events.
- Weight — the cost the decoder assigns to that possible connection.
Here are the same four detection events from above, now as a graph — same positions, new meaning:
This graph is a decoding representation, not the quantum hardware — it's a tool the decoder builds from the syndrome to reason about explanations.
What Does a Weight Mean?¶
A lower-weight edge represents an explanation the decoder considers less costly, or more plausible, under its model. For a beginner-friendly starting point, we'll use geometric distance on the lattice as a proxy:
If errors are assumed to be similarly likely across the lattice, A↔B (weight 2) is the simpler explanation than A↔C (weight 4) — it requires fewer qubits to have gone wrong.
Warning
MWPM does not always choose the physically shortest path. Geometric distance is just this section's starting intuition. Real decoder weights reflect assumptions about error probabilities — they don't have to represent geometric distance at all. MWPM minimizes whatever weights the decoder's error model assigns, and we'll see those weights change later in this page.
Main Interactive — Match the Detection Events¶
Pair up all four detection events yourself. Click one node, then click another to pair them; click a paired node again to unpair it.
Click any two nodes to pair them.
Try a few different complete matchings and compare their total weights. Which one comes out lowest?
Why "Perfect Matching"?¶
Now that you've built a few matchings by hand, here's the vocabulary:
- Matching — a set of selected edges that pairs nodes, without using any node more than once.
- Perfect matching — a matching in which every node that needs to be matched is paired.
- Minimum-weight perfect matching — among all valid perfect matchings, the one with the smallest total edge weight.
where \(M\) is the selected matching, \(w_{ij}\) is the weight of each selected edge, and \(W(M)\) is the total matching weight. You don't need the equation to understand MWPM — it just says "add up the weights of whatever you picked."
For the graph above, the minimum-weight perfect matching pairs A↔B and C↔D for a total weight of 4 — pairing each error's own two detection events together, rather than crossing between the two separate errors.
From Matching to Recovery¶
The matching isn't the end goal — it's a means to a recovery. Selected edges get translated back onto the physical lattice as a suggested correction:
The green lines show the recovery paths implied by pairing A↔B and C↔D — connecting each pair's detection events back on the physical lattice.
The matching tells the decoder how detection events should be paired under its model. Those pairings are then used to construct a recovery — not left as an abstract graph exercise.
The Decoder Can Be "Wrong" and Still Succeed¶
Here's a verified example. Suppose the true physical error was three qubits — not the one qubit MWPM will infer:
A decoder does not necessarily need to reconstruct the exact microscopic error history. Its goal is to choose a recovery that returns the system to the correct logical state — not to guess the literal qubits that flipped.
When a Matching Causes Logical Failure¶
Now the contrasting case — verified the same way, with a different true error:
A decoder makes an inference from incomplete information. It cannot guarantee that its selected explanation matches the actual physical error — decoder success and decoder logical failure are both real possibilities, even when the decoder does exactly what it's designed to do.
Weights Depend on the Error Model¶
Back to the 4-node graph. Same detection events, same candidate connections — but watch what happens when the assumed error model changes.
Same syndrome, same candidate connections — but a different set of assumptions about how errors occur changed which matching MWPM prefers. Decoding depends on both the syndrome and the decoder's assumptions about the error process — exactly the lesson from Decoding, now playing out on a graph. (We're not modeling real hardware calibration here — that's Hardware-Aware QEC.)
Optional Exploration — Can You Beat the Decoder?¶
One more graph, arranged as a perfect square so two different matchings tie for the minimum. Build your own matching, then compare it against MWPM's answer.
Click two nodes to pair them, then try Run MWPM.
Takeaway¶
Minimum-Weight Perfect Matching is a decoding method that uses weighted relationships between detection events to choose a low-cost recovery consistent with the observed syndrome and the decoder's error model. MWPM does not need to determine exactly what physically happened — it needs to choose a recovery that protects the logical information, and as you saw above, it doesn't always succeed.
We can now protect a logical qubit with a surface code and decode its errors. But how do we perform operations between logical qubits while keeping them protected?