Decoder for the Triangular Color Code by Matching on a Möbius Strip

The color code is remarkable for its ability to perform fault-tolerant logic gates. This motivates the design of practical decoders that minimize the resource cost of color-code quantum computation. Here we propose a decoder for the planar color code with a triangular boundary where we match syndrome defects on a nontrivial manifold that has the topology of a Möbius strip. A basic implementation of our decoder used on the color code with hexagonal lattice geometry demonstrates a logical failure rate that is competitive with the optimal performance of the surface code. The logical failure rate scales approximately like $p^{\alpha \sqrt{n}}$, with $\alpha \approx 6/7\sqrt{3}\approx 0.5$, error rate $p$, and $n$ the code length. Furthermore, by exhaustively testing over five billion error configurations, we find that a modification of our decoder that manually compares inequivalent recovery operators can correct all errors of weight $\le (d-1)/2$ for codes with distance $d\le 13$. Our decoder is derived using relations among the stabilizers that preserve global conservation laws at the lattice boundary. We present generalizations of our method to depolarizing noise and fault-tolerant error correction, as well as to Majorana surface codes, higher-dimensional color codes, and single-shot error correction.

Popular Summary

Quantum error-correcting codes are many-body quantum systems that protect information that is processed during a quantum computation. To design a useful, large-scale quantum computer, we need to develop practical quantum error-correcting codes that can be realized with modern technology. The color code offers a number of advantages for two-dimensional fault-tolerant quantum computation. In particular, it has very efficient ways of performing quantum logic gates. To exploit its favorable properties, we need to design better decoding algorithms to improve its tolerance to errors. These are classical algorithms that determine how to correct errors in code experiences.

Here we design a practical decoder with high performance by careful examination of the underlying physics of the color code. We can view quantum error-correcting codes as phases of matter where errors are excitations that give rise to quasiparticles. These quasiparticles respect conservation laws whereby errors create quasiparticles in pairs with respect to some symmetry of the system. From this perspective, decoding then is simply a matching problem, where we aim to pair together quasiparticles to annihilate them, and reverse the effects of the error. In this work, we take a careful look at the conservation laws at the boundaries of the color code. Surprisingly, our examination reveals that the decoding problem for the color code on a planar lattice is mapped onto a manifold with nontrivial topology, namely that of a Möbius strip. Our new decoder demonstrates a measurable improvement in error-correcting performance compared with other matching decoders for the color code.

Figure 1

The color code on the lattice with triangular boundaries. Qubits lie on the vertices of the three-colorable lattice and the red, green, and blue boundaries of the lattice are shown by brightly colored lines of their corresponding color. (a) A stabilizer generator $S_f$. (b) A stringlike logical operator terminates at each of the three distinct boundaries of the lattice and branches in the middle of the lattice. Examples of bit-flip errors and the individual defects of their syndrome are shown at (c)–(f).

Figure 2

Decomposing a symmetry of the color code. We show four errors (i)–(iv). We color the faces of the lattice that are members of ${\mathrm{\Sigma }}_{\mathbf{r}}={\mathrm{\Sigma }}_{\mathbf{r}}^A\cup {\mathrm{\Sigma }}_{\mathbf{r}}^B$ where we separate the faces of the symmetry into disjoint subsets where ${\mathrm{\Sigma }}_{\mathbf{r}}^A$(${\mathrm{\Sigma }}_{\mathbf{r}}^B$) are the faces of ${\mathrm{\Sigma }}_{\mathbf{r}}$ that lie above (below) the red line. Red faces are excluded from the symmetry. The red line that extends from the left to the right of the figure shows the qubits that support a logical operator of the color code. Errors (i), (iii), and (iv) each give rise to a single defect on either side of the red line on either blue or green faces. Error (ii) creates only red defects, and as such they do not appear on the faces of the symmetry.

Figure 3

The $\mathbf{g}\mathbf{b}$ restricted lattice from the symmetries of the color code. We draw the color code on the dual lattice where faces are replaced by vertices and qubits are replaced by triangles. We highlight the stabilizer vertices associated to the symmetry with blue and green vertices. We overlay the dual lattice with the primal lattice in the large circle to the left of the figure. Two adjacent stabilizers are connected by an edge. Each edge has two adjacent qubits that can be flipped to create defects at the endpoints of each edge, see, e.g., $q_1$ and $q_2$ to the right of the figure. If exactly one of these two qubits are flipped then two defects on the bold vertices will be created on the restricted lattice.

Figure 4

The Möbius symmetry. An image of the error syndrome is shown three times on three different restricted lattices. The restricted lattices are connected at their boundaries to reconstruct a single unified lattice that is embedded on a Möbius strip. We number unified qubits to the left and right of the lattice, Note that the qubits are oppositely aligned on each side of the lattice, thus giving the restricted lattice Möbius topology. We show the image of the error syndrome shown to the right of the figure on the Möbius symmetry. We also show the operator $b_{\mathbf{g}}$, which is the product of all the stabilizers on the red and blue faces.

Figure 5

The error syndrome mapped onto the Möbius strip. At the top of the figure we show three single-qubit errors; one in the bulk that gives rise to three defects, one at the boundary that creates two defects, and an error at the corner where only one defect is produced. They are circled with solid, dashed, and dotted lines, respectively. Arrows point to the image of the error and its syndrome on the Möbius strip. We observe that the single-qubit error in the bulk produces three edges on the Möbius strip. A single-qubit error on the boundary produces two edges; one in the bulk of the lattice, and one that crosses the crease that represents the logical operator supported on the green boundary. An error at the corner of the color code produces a single edge on the Möbius strip.

Figure 6

A difficult error for a decoder that does not account for correlations between green and blue defects. For a sufficiently large code, with $d\gtrsim 11$, one can find errors of weight $w=O(d/3)$ such that $w\ll (d-1)/2$ where, if we neglect the position of the blue defect, the green defect is paired to the green boundary with a correction of weight $w_{\mathbf{g}}<w$. Likewise, a decoder that matches on the $\mathbf{r}\mathbf{b}$ lattice will suggest a correction where the blue defect is paired to the blue boundary with an operator of weight $w_{\mathbf{b}}<w$. These choices will lead the decoder to fail.

Figure 7

The image of the error shown in Fig. 6 on the unified lattice. The error, shown in gray, has weight approximately $2w+1$. However, the distance between the two green defects is $2w_{\mathbf{g}}$ on the Möbius strip. Likewise, the distance between the two blue defects is $2w_{\mathbf{b}}$. We therefore see that the matching decoder will only find the incorrect outcome if $2w+1\gtrsim 2(w_{\mathbf{g}}+w_{\mathbf{b}})$. Given that $w+w_{\mathbf{g}}+w_{\mathbf{b}}=d$, we find that the decoder can tolerate errors of the type shown in Fig. 6, i.e., long strings that extend from the boundary, provided $w\lesssim d/2$.

Figure 8

Here we consider a weight-4 error on a $d=7$ color-code lattice. The left of the figure shows the error on the color-code lattice, together with the correction a naïve decoder will choose. Specifically, matching on the $\mathbf{r}\mathbf{b}$-restricted lattice will pair the two blue defects correctly. However, matching on the $\mathbf{r}\mathbf{g}$-restricted lattice will incorrectly pair the green defect along the shortest path to the green corner of the lattice. On the right we show the image of the same error on the unified lattice. Given that the decoder accounts for information from all three restricted lattices, we find that the decoder will find the right correction by pairing defects along the solid lines. The incorrect matching, shown by the dashed lines, has a higher weight. As such, in this example, a decoder that matches on the unified lattice will be successful.

Figure 9

Matching found for the syndrome of small errors using the matching algorithm. (a) Typical stringlike errors with weight $w$ are paired by two edges from the matching. The sum of the weights of the edges that pair these two red defects have weight $\ell \sim 2w$. (b),(c) Small errors with weights $w=1$ and $w=3$, respectively, that are identified by the matching algorithm with three edges in the matching that have total length $\ell =3w$. (d),(e) Branching errors of weight $w=9$ whose matchings have weights $\ell =2w+3$ and $\ell =3(w+1)/2$, respectively.

Figure 10

Obtaining two low-weight corrections that are logically inequivalent. We perform minimum-weight perfect-matching multiple times. The first time with a single use of the minimum-weight perfect-matching algorithm that we discussed above. We show this matching in blue. In the second use of the subroutine we change the topology of the manifold to force the algorithm to find an alternative low-weight correction, shown in red. The union of the two corrections produce networks of defects. The union of the edges of exactly one of these networks will form a nontrivial cycle around the Möbius strip.

Figure 11

Plot with logarithmic axes showing the logical failure rate $P_{\mathrm{fail}}$ for the triangular color code as a function of physical error rate $p$ using the Möbius decoder. We plot the exact form of the ansatz, Eq. (14) for each code distance $d$, showing good agreement with the data. Data points are collected using between ${10}^6$ and ${10}^7$ Monte Carlo samples.

Figure 12

Threshold plot for an independent and identically distributed bit-flip noise model. The logical failure rate $P_{\mathrm{fail}}$ is plotted as a function of physical error rate $p$ for codes of different distance $d$. The threshold, indicated by the intersection of the curves, is found to be 9.0%. The error bars show the standard deviation of the mean logical failure rate where each data point is collected using approximately $5\times {10}^4$ Monte Carlo samples. The data collected is fit to the function $f=A{x}^2+Bx+C$ where $x$ is the rescaled error rate $x=(p-p_c)d^{1/v_0}$. Each dashed line indicates this fitting for a given system size.

Figure 13

We observe an error of weight $w=4$ shown by the qubits in white on the distance $d=9$ lattice. The minimum-weight matching decoder will choose the set of edges, (a), such that ${\ell }_{\mathrm{or}}=11$. However, we note that the error configuration in dark gray traced out by these edges is logically inequivalent to the least-weight solution and is of weight $w=5$. The alternate correction, (b), which forces an inequivalent path around the Möbius strip, finds a set of edges with ${\ell }_{\mathrm{alt}}=12$ that correctly traces out the true least-weight error. This phenomenon is an instance of the branches we have discussed in Fig. 9.

Figure 14

Error for the $d=11$ color code where the alternative correction gives the least-weight solution with $w=5$. We have ${\ell }_{\mathrm{or}}=12$ and ${\ell }_{\mathrm{alt}}=13$ where we show the original matching with solid lines and the alternative matching with dashed lines.

Figure 15

A weight $(d-1)/2=4$ error on a $d=9$ color code. A correction of weight 5 can introduce a logical error. As such it is important to determine that the weight of the correction associated to this matching is $w=4$. A basic implementation of a matching subroutine is equally likely to choose between the (a) and (b) output, as both have $\ell =12$. However, only the matching and choice of paths on the matching of (a) will predict a correction of weight 4 using the methods of Refs. [51, 53]. For the matching given on the left-hand side we see that the edges bound the low-weight error exactly, thereby showing that the correct weight will be obtained using the method of Ref. [51], for instance. Likewise, the set of edges (a) will give the correct weight using the methods of Ref. [53]. Both of these methods will overestimate the weight of the correction given the matching shown on the opposite lattice (b).

Figure 16

(a) We show the stabilizers of ${\mathrm{\Sigma }}_{\mathbf{r}}^A$ where we bring the logical operator $\overline{L}$ to the foreground. In the figure we have that $\prod _{A}s\sim \overline{L}$ where we take the product over $s\in {\mathrm{\Sigma }}_{\mathbf{r}}^A$. All errors (i), (iii), and (iv) anticommute with $\overline{L}$. As such, for consistency, they necessarily create an odd parity of defects on the faces of ${\mathrm{\Sigma }}_{\mathbf{r}}^A$. Error (ii) commutes with $\overline{L}$ as it has no common support with the logical operator. It therefore creates an even parity of defects on the faces of ${\mathrm{\Sigma }}_{\mathbf{r}}^A$. (b) For completeness we show the faces of ${\mathrm{\Sigma }}_{\mathbf{r}}^B$ together with the errors in the foreground. Again, errors (i), (iii), and (iv) create a single defect on the faces of ${\mathrm{\Sigma }}_{\mathbf{r}}^B$ due to their commutation relation with the logical operator $\overline{L}\sim \prod _{B}s$. Error (ii) creates no defects on the faces of ${\mathrm{\Sigma }}_{\mathbf{r}}^B$.

Figure 17

Evaluating the distance between two vertices on the hexagonal lattice. We use three nonorthogonal axes to find the distance between two vertices on the hexagonal lattice. We label the axes shown at (a), (b), and (c) with symbols $x_0$, $x_2$, and $x_4$, respectively. The brightly colored lines in each of these figures show all the vertices with a common value according to this coordinate system. (d) We show the distance of each of the vertices from the central vertex marked with a 0 with bold contour lines overlaying the red hexagonal lattice.

Figure 18

Finding an alternative correction using an additional matching subroutine. The initial matching is shown by blue edges. We modify the input graph to the second subroutine to find an alternative correction. We introduce a “tear” to the Möbius strip, see the zig-zag line at (a). In the second subroutine, no defects can pair using an edge that crosses the tear. We also remove all pairs of vertices from the initial matching that are paired by an edge that crosses the tear. For example, see the pair of defects connected by the dashed blue edge, (b). To find an inequivalent matching we introduce a single dummy node on either side of the tear, (c). The inclusion of these dummy nodes force the matching to find an alternative correction, shown by the red edges. The two defects that are matched by the two dummy nodes form a new edge, see the endpoints of the edge at (d),(e). Finally, we try to reduce the weight of the edge found using the dummy vertices by looking for a shorter route back over the tear using the edges that were removed when we made the tear. The defects found by the dummy nodes are subsequently paired to the green defects, connected by the dashed line, that were initially removed to obtain the alternative correction when we made the tear. The last step recovers the matching shown in Fig. 10 in the main text.

Figure 19

(a) The logarithm of the logical failure rate $P_{\mathrm{fail}}$ is plotted against $\log (p)$ for different system sizes. Each individual plot is fitted to a linear equation, discarding points for which $P_{\mathrm{fail}}$ is lower than $5\times {10}^{-4}\mathrm{\%}$. These data points sit below the horizontal black line. We then extract the gradients $G(d)$ and intercepts $A(d)$ for each linear fit. The gradients and intercepts of the linear fittings observed in (a) are plotted as a function of the system size $d$. (b) For the linear plot of $G(d)$ in blue, the slope is the value of $\alpha$ for our decoder and $\gamma$ is the intercept. The green line has a slope of 1/2, which is the gradient we expect for a decoder that can correct up to its code distance. The red line has a slope of 1/3. We read $\alpha$ and $\gamma$ from the gradient and intercept of the blue line, respectively. (c) For the function $A(d)$, the intercept is $\log \beta +\gamma \log N$ and the slope is $\alpha \log N$.

Figure 20

The color code with two green boundaries and two blue boundaries. All four corners of the lattice are red. Like the color code on the triangular lattice, we can unify the restricted lattices of this code through the boundaries and the corners of the lattice. We show a green defect and a red defect created at the boundary. We show edges that pair them between different restricted lattices via the boundary. Furthermore, we can consider a Majorana surface code where an unpaired Majorana mode ${\lambda }_v$ lies on each vertex and we have stabilizers $S_f=\prod _{v\in \mathrm{\partial }f}{\lambda }_v$. In this picture the red face operators can be regarded as a tetron. Decoding the Majorana fermion surface code is equivalent to correcting bit flips for the color code.

Figure 21

The unified lattice of the color code shown in Fig. 20 is embedded on a manifold with the topology of a torus with a single disk-shaped puncture.

Figure 22

A proposal for a unified symmetry for the color code on a toric lattice. (a) We show an element of the stabilizer group depicted by the product of shaded face operators. It consists of the restricted lattice ${\mathrm{\Sigma }}_{\mathbf{b}}$ to the left of the lattice and ${\mathrm{\Sigma }}_{\mathbf{g}}$ to the right of the lattice. The product of these operators is a one-dimensional line of Pauli-$Z$ operators that runs vertically through the middle of the lattice. (b) We obtain the same stabilizer term shown in the top figure by taking the product of the green and blue face operators of the restricted lattice ${\mathrm{\Sigma }}_{\mathbf{r}}$. Together, the set of stabilizers shown in the top figure, and those shown in the middle figure give a symmetry. The union of these two subsets of stabilizers form a seam. (c) We can combine seams around a periodic lattice to find a global symmetry. We propose one suitable configuration by representing the two-dimensional lattices by one-dimensional lines that cut the lattices. We show how these bold lines align with the two-dimensional restricted lattices by the bold lines shown at the bottom of the lattices shown at the top and middle of the figure.

Figure 23

The product of Pauli-$X$ stabilizers, Pauli-$Y$ stabilizers, and Pauli-$Z$ stabilizers on, respectively, red, green, and blue faces gives rise to a symmetry.

Figure 24

The syndrome of stabilizers measured in spacetime. In all figures time runs in the upward direction. (a) The Pauli-$X$ stabilizer and the Pauli-$Z$ stabilizer of a common plaquette are measured over time in an alternating pattern. If no errors occur, we expect $S_f^Z(T)=+1$ for all measurements $T=t-1,t,t+1$. A measurement error on the central face occurs, we therefore create a pair of $r_X$ defects detected by checks $S_f^Z(t)S_f^Z(t-1)=-1$ and $S_f^Z(t+1)S_f^Z(t)=-1$. (b) We measure a periodic sequence of Pauli-$X$, Pauli-$Y$, and Pauli-$Z$ stabilizers and define a check as the product of three time-adjacent measurements. A single measurement error creates three defects. (c) A single physical Pauli-$X$ error violates three adjacent checks of different colors. A single blue check is shown. (d) A Pauli-$X$ error occurring between the measurement of Pauli-$Y$ stabilizer and Pauli-$Z$ stabilizer measurements creates six defects. (e) A pair of measurement errors creates two defects of the same type with temporal separation.

Figure 25

Decoding point defects for the color code in higher dimensions. (a) An error of weight approximately $d/4$ on the three-dimensional tetrahedral color code that may lead a matching decoder on a restricted lattice to a logical failure. The stringlike error stretches up from the red boundary to the center of the lattice such that the three defects can be paired to the boundary of their corresponding color with $\lesssim d/(D+1)$ errors. (b) An error on a single qubit and its syndrome on the restricted lattice of blue and green cells. A single error on any of the six qubits of the face separating the two cells, shaded in pink, will give rise to the same syndrome with respect to the restricted lattice.

Figure 26

Four boundary operators obtained by taking the product of all the cell operators of two of the four color subsets of stabilizers. The left most tetrahedron shows the product of the blue and the green cell operators. The nontrivial support of the boundary operator lies on the blue and green boundaries, with the exception of the qubits that lie on both the blue and green boundaries. The figure also shows the boundary operator for the red-blue restricted lattice, the yellow-red restricted lattice, and the green-yellow restricted lattice. The restricted lattices can be combined by their shared boundaries via the displayed arrows to produce a unified lattice to decode the point excitations of the three-dimensional color code.

Figure 27

Single-shot error correction with the gauge color code. (a) A blue gauge check. The check is the product of all the face operators about a red cell that include a blue color element. The value of the gauge check is independent of the value of the syndrome of the color-code stabilizers. It depends only on measurement errors of its faces. (b) Two blue gauge checks are violated on the red and green cell. The blue gauge check of the central yellow cell is not violated. We can consistently pair the blue gauge defects as we necessarily have an even number of them due to their bulk symmetry. (c) A collection of gauge defects that can be locally corrected. The edges show the results from matching for each of the color charge symmetries. (d) Matching subroutines for different charge colors are performed in unison. The two constituent charges for a single $\mathbf{y}\mathbf{b}$ gauge defect are paired via the green boundary.