The Minimum Weight Perfect Matching (MWPM) decoder seems to be the most popular choice for decoding error syndromes in Surface Code quantum error correction. Can anyone give an intuitive idea of how it works, with an example?
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
I recommend reading the sparse blossom paper.
Strings
In the surface code, errors produce pairs of detection events. Chains of errors can cancel out the detection events along the chain, leaving only the detection events at the end. In other words, errors form strings and you can see the endpoints of the strings. The goal of a matching decoder is to infer the shortest possible strings, given the endpoints (the excitations; the detection events).
Certificates
Matching works by producing a certificate-of-optimality. The certificate works by placing a circle of some radius around each excitation, where if two excitations are matched their circles must touch:
In the above picture, how do we know that there's no way to match up the points at the centers of the circles that uses less total line length? Well, if you focus on one detection event, any solution must have a part-of-line that crosses out of its circle. So all solutions must have a cost at least as high as the sum of the radii of these circles. But this solution has exactly that cost. Therefore it is optimal.
By not overlapping, and touching if linked, the circles certify that this specific set of lines is optimal.
A complication that can show up is sometimes you can't find a way to draw these circles without nesting some of them into a combined shape with a constant-crossing-distance perimeter called a blossom:
(Exercise: the above picture doesn't technically require the blossom. You can find a set of normal circles that certifies the solution. Find one.)
The same idea as before applies. ANY solution to the problem MUST have cost of at least leave(A)+leave(B)+leave(C)+leave(D)+leave(E)+cross(1)+cross(2). Otherwise it can't possibly connect up everything. But this specific solution has exactly that cost, therefore it's optimal.
Growth
So the goal is to produce this certificate of optimality that looks like nested circles. How do we do that? All you have to do is to start in a state where every excitation has a radius-0 circle around it, and start growing the circles. Never stop growing a circle until it finds a partner.
- When a pair of circles touches each other, they form a matched pair of partners, and their circles can stop growing.
- When a circle hits a matched pair, it hasn't found a partner (it's the odd one out). So it must keep growing. To avoid the circles overlapping, and to avoid losing the existing pairing, one of the circles in the pair must start shrinking and the other must start growing. This process can repeat, forming a whole tree of shrinking and growing circles.
- When a tree hits a different tree, the collision point forms a match which then allows the trees to internally fall apart into matches.
- When a tree hits itself, a blossom forms to remove the cycle. The circles within the blossom stop growing, and instead a radius starts growing around the blossom as a whole. The blossom is treated as if it is one object, capable of partnering to a circle to stop it growing.
- In some situations a blossom will start shrinking. If it shrinks too much, it can actually shatter back into the original circles.
Call a circle "energetic" if it has never paused its growth due to finding a partner. You can show that, for these rules, there will always be one circle that's energetic until the end. Or, in other words, if no circles are energetic then all detection events are paired. Assuming all circles grow and shrink at a shared consistent rate, the algorithm cannot run longer than the maximum distance from one detection event to another or to the boundary, because by that point all the circles will have merged into one big thing and that thing would contain an even number of excitations (or touch the boundary) which causes circles to stop being energetic.
Incidentally, although I've been saying "circle" this whole time, the idea generalizes to any distance metric. I should technically have been saying "shape of constant radius". This generality is what allows the algorithm to work on graphs, where the shape of constant radius is formed by all points that can be reached by traveling along the edges of the graph according to their weighs.
Here's an animation of the process. It doesn't use the same color scheme as the other pictures, and it doesn't show the edges within the blossoms, but it should give you an idea of how the algorithm progresses:
$\begingroup$
$\endgroup$
The idea of how it works is very simple. Errors on the surface code form strings: when you measure the stabilizers, you detect the ends of the strings. The goal of error correction is, having identified where the ends of the strings are, you want to find a way to match them into pairs, claiming those to be the ends of a string, and then correcting them. The length of each string is the minimum number of Pauli errors required to make that string. So, under the assumption that errors are rare, a very good assignment of pairings of string ends is simply to find the way of pairing them that would have taken the smallest number of Pauli errors to create them.
Of course, the errors that we identify may not have been exactly what happened, but we're hoping the the topological nature of the system means that even if we don't undo the exact set of errors that happened, it's close enough that everything just forms small closed loops, and hence cancels.
Example: Consider a 1D line of squares. I'll number the squares 1, 2, ..., 10. These correspond to a set of 10 stabilizers you might measure, let's say of the form $ZZZZ$ around the square (qubits are on the edges, e.g. the blobs around square 3).
If I measure these stabilizers, let's say I get -1 values for square 1, 4, 5, 9 (the $E$s in the diagram). So, there are going to be 2 strings, and we need to identify how to pair them up. The most obvious is $$ 1-4 \qquad 5-9. $$ To make these error strings would require 3 $X$ errors along the line of qubits joining boxes 1 and 4, and 4 $X$ errors along the line of qubits joiuning boxes 5 and 9. Total: 7. I claim that however you pair these up, that's the smallest you can possibly get. For comparison, I could consider the pairs $$ 4-5,\qquad 1-9. $$ This is obviously worse (total: 9), but illustrates why it's important to take the global total rather than just trying to make lots of short strings.
Of course, in practice, you're dealing with errors in 2D, and you'll have to take care of boundary conditions. Both periodic and open boundary conditions have their subtleties.
