Minimum weight error correction in the surface code
I’ve gotten a little confused by different terminologies and complexities involved in correcting errors in the surface code so I’ve rewritten the MWPM-involving algorithm to better understand it. A good reference (with fast accompanying library) is 1.
Picture the surface code. Consider the following procedure to estimate and correct the error in a given word.
Generate the parity check matrix H for one of the operators (X-type or Z-type) over mod 2.
Generate the so-called matching graph : Vertices consist of Z-type syndromes, edges are the qubit connecting the syndromes, ie. vertices u, v are connected if and only if the qubit k involved in syndromes u and v flips. If a vertex is only associated to a single stabilizer, add a boundary node and set its weight to 0. Additionally, attribute every edge with the qubit associated with said edge (boundary) (with distance, ie. weight, equal to zero).
Multiply H with error word e mod 2, get all your syndromes.
Run all-pairs shortest paths on the matching graph, we receive the so-called path graph (boundary included).
Create a syndrome graph in the following way: For every defect generate a complete graph. The edges of this graph are the distances we receive from the path graph connecting the syndromes. To correct an error, we need to match up syndromes in a pairwise manner. The syndrome graph needs to have an even number of vertices for us to be able to find a perfect matching. Hence, if the number of non-zero syndromes is uneven, assign the boundary node from the matching graph as another another vertex here. Run any Minimum Weight Perfect Matching algorithm here2.
From the perfect matching in the syndrome graph we know which syndromes need to be connected. We can extract their respective paths from the path graph. Now we can subsequently flip all the qubit in this path and do this for all syndromes that have been matched.
Combine X-type and Z-type error correction if needed.
Note (June 28 2023) Apparently we’re solving the Chinese Postman Problem here. I’ll investigate this further.