Decoding Surface Codes with Minimum-Weight Perfect Matching

Hello! Welcome back to our study of fault-tolerant quantum computing.

In our last lesson, we established the crucial connection between physical errors on the surface code and the patterns of violated stabilizers, or syndromes, they produce. We saw that any local error or error chain creates a pair of syndrome "defects" at its endpoints, which can be separated in space or time. We concluded by introducing the high-level idea that decoding this syndrome is equivalent to solving a Minimum-Weight Perfect Matching (MWPM) problem on a graph of these defects.

Today, we will formalize this idea. The goal is to delve into the precise algorithmic details of this mapping. Our learning outcome is to formulate the surface code decoding problem as a minimum-weight perfect matching instance and analyze the mapping from syndromes to graph weights. This involves constructing the exact graph and, most importantly, understanding how to assign meaningful weights to its edges based on the physics of the underlying noise.

1. The Decoding Graph: Vertices, Edges, and Boundaries

Let's begin by formalizing the components of the graph used for decoding. As we discussed, the problem isn't just a 2D snapshot; it's a 3D spacetime problem involving multiple rounds of syndrome measurement.

The following video from a Qiskit seminar by Ted Yoder provides an excellent and detailed overview of how the decoding graph is constructed from experimental data. It introduces the concept of "error-sensitive events" which become the nodes of our graph.

To summarize and build on the video's points:

• Vertices (Nodes): The vertices of our decoding graph correspond to the spacetime coordinates $(x,y,t)$ where a stabilizer measurement flips its value (from $+1\to -1$ or $-1\to +1$). These are the "detection events" or "syndrome defects".
• The Boundary: We augment the set of vertices with a single, special boundary node. This node acts as a sink for error chains that begin or end at the physical edge of the surface code lattice. An error near the boundary might only create one visible syndrome defect inside the code; the boundary node serves as its implicit partner for the matching.
• Edges: An edge is drawn between every pair of vertices in the graph (including the boundary vertex). The graph is a complete graph. Each edge $(v_i,v_j)$ represents the hypothesis that the two syndrome defects $v_i$ and $v_j$ are the endpoints of a single, underlying error chain.

The problem is now clear: given a set of active syndrome vertices, we need to choose a set of edges that pairs them all up. But which pairing is the correct one? This is where edge weights become critical.

2. From Error Probability to Edge Weights

The central principle of MWPM decoding is to find the most likely set of error chains that could have produced the observed syndrome. Since we assume errors are independent and rare, shorter error chains are exponentially more probable than longer ones. Our goal is to find the matching that corresponds to the highest overall probability.

The standard MWPM algorithm, however, is designed to find a matching with the minimum total weight. We can connect these two objectives by defining the edge weight as the negative logarithm of the error probability.

Let $P(e_{ij})$ be the probability of the most likely error chain that connects syndrome defects $i$ and $j$. We define the weight of the edge between them as:

Maximizing the total probability $\prod P(e_{ij})$ over the matching is equivalent to maximizing $\sum \log P(e_{ij})$, which in turn is equivalent to minimizing $\sum w_{ij}$.

So, how do we calculate $P(e_{ij})$? This depends on our noise model.

• For a simple model, we can assume each single-qubit Pauli error $E\in \{X,Y,Z\}$ occurs with a physical error probability $p$. An error chain of length $L$ would then have a probability proportional to $p^L$. The weight $w_{ij}$ would then be proportional to the "distance" between nodes $i$ and $j$ on the lattice. This is often taken to be the Manhattan distance: $d=|x_i-x_j|+|y_i-y_j|+c\cdot |t_i-t_j|$, where $c$ is a constant weighting the cost of time-like separation.
• For more sophisticated models, we must consider the specific probabilities of failure for each gate and measurement in the circuit.

The following resource provides a clear mathematical formulation for this weight calculation.

The key formula from the resource, $w_i=\log ((1-p_i)/p_i)$, is a specific form of the log-likelihood ratio. Summing these weights for all errors in a chain gives the total weight for the corresponding edge in the decoding graph. In practice, calculating the weight between two arbitrary syndrome defects requires finding the shortest path between them on the physical lattice and summing the weights of the elementary errors along that path. This calculation can be done using algorithms like Dijkstra's.

Ted Yoder's talk also discusses more advanced methods for determining these weights, including using experimental data to learn them, which addresses correlations and complex noise that simple analytical models might miss.

3. The Full Formulation: The Global Weight Table

We can now assemble the complete problem statement. The decoding process involves two main stages:

1. Pre-computation: Before the experiment even runs, we can compute the weights for all possible edges. For a code with $N$ possible syndrome locations (including all spatial locations over $d$ rounds of time, where $d$ is the code distance), we can construct a giant $N\times N$ matrix, often called a Global Weight Table (GWT). The entry $(i,j)$ in this table stores the weight $w_{ij}$ of the edge connecting potential syndrome defects $i$ and $j$. This weight is calculated by finding the shortest path between $i$ and $j$ on the physical lattice and summing the log-likelihoods of the elemental errors along it. The diagonal elements $w_{ii}$ store the weight of connecting defect $i$ to the boundary.

2. Real-time Decoding:

   • During the experiment, we observe a syndrome, which is a small list of active defect locations $\{s_1,s_2,\dots ,s_k\}$.
   • We construct a small, complete graph using only these $k$ vertices (plus the boundary, if $k$ is odd).
   • We look up the required weights $w_{s_i{s}_j}$ from the pre-computed GWT.
   • We run an efficient classical MWPM algorithm (like the Blossom algorithm) on this small graph to find the minimum-weight pairing.
   • The resulting pairs tell us the endpoints of the most likely error chains. We then apply corrections (e.g., Pauli-X gates) along the physical paths on the lattice corresponding to these matched edges.

The following paper, which introduces a decoder named 'Astrea', provides a very clear and practical description of this exact process.

This formulation neatly separates the computationally heavy task of calculating all possible error path probabilities (done once, offline) from the fast, real-time task of matching the small number of syndromes that actually appear in any given cycle.

Conclusion

In this lesson, we have moved from a conceptual picture of decoding to a precise, algorithmic formulation. We have transformed the physical problem of inferring errors from syndromes into the well-understood computer science problem of Minimum-Weight Perfect Matching.

Key Takeaways:

• The surface code decoding problem is formulated as finding a Minimum-Weight Perfect Matching on a complete graph.
• The vertices of this graph are the observed syndrome defects in spacetime, plus a special boundary node.
• The weight of an edge connecting two defects is the negative logarithm of the probability of the most likely error chain causing them. This maps the goal of finding the most probable error configuration to finding the minimum weight matching.
• Edge weights can be calculated from an analytical noise model or learned from experimental data.
• In practice, all possible edge weights can be pre-computed and stored in a Global Weight Table (GWT), allowing for fast look-up and real-time decoding of observed syndromes.

Preview of the next module:
We have now completed our deep dive into the surface code, one of the most promising candidates for building a fault-tolerant quantum computer. In the next module, we will broaden our perspective and begin exploring other important families of quantum codes, starting with Low-Density Parity-Check (LDPC) codes, which hold the potential for even better performance than surface codes.