Toric code

Next we'll discuss a specific CSS code known as the toric code, which was discovered by Alexei Kitaev in 1997. In fact, the toric code isn't a single code, but rather it's a family of codes, one for each positive integer starting from 2. These codes possess a few key properties:

• The stabilizer generators have low weight, and in particular they all have weight 4. In coding theory parlance, the toric code is an example of a quantum low-density parity check code, or quantum LDPC code (where low means 4 in this case). This is nice because each stabilizer generator measurement doesn't need to involve too many qubits.

• The toric code has geometric locality. This means that not only do the stabilizer generators have low weight, but it's also possible to arrange the qubits spatially so that each of the stabilizer generator measurements only involves qubits that are close together. In principle, this makes these measurements easier to implement than if they involved spatially distant qubits.

• Members of the toric code family have increasingly large distance and can tolerate a relatively high error rate.

---

Toric code description

Let $L\geq 2$ be a positive integer, and consider an $L\times L$ lattice with so-called periodic boundaries. For example, this figure depicts an $L\times L$ lattice for $L=9.$

Notice that the lines on the right and on the bottom are dotted lines. This is meant to indicate that dotted line on the right is the same line as the line all the way on the left, and similarly, the dotted line on the bottom is the same line as the one on the very top.

To realize this sort of configuration physically requires three dimensions. In particular, we could form the lattice into a cylinder by first matching up the left and right sides, and then bend the cylinder around so that the circles at the ends, which used to be the top and bottom edges of the lattice, meet. Or we could match up the top and bottom first and then the sides; it works both ways and doesn't matter which we choose for the purposes of this discussion.

What we obtain is a torus — or, in other words, a doughnut (although thinking about it as an inner tube of a tire is perhaps a better image to have in mind because this isn't a solid: the lattice has become just the surface of a torus). This is where the name "toric code" comes from.

The way one can "move around" on a torus like this, between adjacent points on the lattice, will likely be familiar to those that have played old-school video games, where moving off the top of the screen causes you emerge on the bottom, and likewise for the left and right edges of the screen. This is how we will view this lattice with periodic boundaries, as opposed to speaking specifically about a torus in 3-dimensional space.

Next, qubits are arranged on the edges of this lattice, as illustrated in the following figure, where qubits are indicated by solid blue circles.

Note that the qubits placed on the dotted lines aren't solid because they're already represented on the topmost and leftmost lines in the lattice. In total there are $2L^2$ qubits: $L^2$ qubits on horizontal lines and $L^2$ qubits on vertical lines.

To describe the toric code itself, it remains to describe the stabilizer generators:

• For each tile formed by the lines in the lattice there is one $Z$ stabilizer generator, obtained by tensoring $Z$ matrices on the four qubits touching that tile along with identity matrices on all other qubits.

• For each vertex formed by the lines in the lattice there is one $X$ stabilizer generator, obtained by tensoring $X$ matrices on the four qubits adjacent to that vertex along with identity matrices on all other qubits.

In both cases we obtain a weight-4 Pauli operation. Individually, these stabilizer generators may be illustrated as follows.

Here's an illustration showing some examples of stabilizer generators in the context of the lattice itself. Notice that the stabilizer generators that wrap around the periodic boundaries are included. These generators that wrap around the periodic boundaries are not special or in any way distinguished from the ones that don't.

The stabilizer generators must commute for this to be a valid stabilizer code. As usual, the $Z$ stabilizer generators all commute with one another, because $Z$ commutes with itself and the identity commutes with everything, and likewise for the $X$ stabilizer generators. The $Z$ and $X$ stabilizer generators clearly commute when they act nontrivially on disjoint sets of qubits, like for the examples shown in the previous figure. The remaining possibility is that a $Z$ stabilizer generator and an $X$ stabilizer generator overlap on the qubits upon which they act nontrivially, and whenever this happens the generators must always overlap on two qubits, like in the next figure.

Consequently, two stabilizer generators like this commute, just like $Z\otimes Z$ and $X\otimes X$ commute. The stabilizer generators therefore all commute with one another.

The second required condition on the stabilizer generators for a stabilizer code is that they form a minimal generating set. This condition is actually not satisfied by this collection: if we multiply all of the $Z$ stabilizer generators together, we obtain the identity operation, and likewise for the $X$ stabilizer generators. Thus, any one of the $Z$ stabilizer generators can be expressed as the product of all of the remaining ones, and similarly, any one of the $X$ stabilizer generators can be expressed as the product of the remaining $X$ stabilizer generators. If we remove any one of the $Z$ stabilizer generators and any one of the $X$ stabilizer generators, however, we do obtain a minimal generating set.

To be clear about this, we do in fact care equally about all of the stabilizer generators, and in a strictly operational sense there isn't any need to select one stabilizer generator of each type to remove. But, for the sake of analyzing the code — and counting the generators in particular — we can imagine that one stabilizer generator of each type has been removed, so that we get a minimal generating set, keeping in mind that we could always infer the results of these removed generators (thinking of them as observables) from the results of all of the other stabilizer generator observables of the same type.

This leaves $L^2 - 1$ stabilizer generators of each type, or $2L^2 - 2$ in total, in a (hypothetical) minimal generating set. Given that there are $2L^2$ qubits in total, this means that the toric code encodes $2L^2 - 2 (L^2 - 1) = 2$ qubits.

The final condition required of stabilizer generators is that at least one quantum state vector is fixed by all of the stabilizer generators. We will see that this is the case as we proceed with the analysis of the code, but it's also possible to reason that there's no way to generate $-1$ times the identity on all $2L^2$ qubits from the stabilizer generators.

---

Detecting errors

The toric code has a simple and elegant description, but its quantum error-correcting properties may not be at all clear from a first glance. As it turns out, it's an amazing code! To understand why and how it works, let's begin by considering different errors and the syndromes they generate.

The toric code is a CSS code, because all of our stabilizer generators are either $Z$ or $X$ stabilizer generators. This means that $X$ errors and $Z$ errors can be detected (and possibly corrected) separately. In fact, there's a simple symmetry between the $Z$ and $X$ stabilizer generators that allows us to analyze $X$ errors and $Z$ errors in essentially the same way. So, we shall focus on $X$ errors, which are possibly detected by the $Z$ stabilizer generators — but the entire discussion that follows can be translated from $X$ errors to $Z$ errors, which are analogously detected by the $X$ stabilizer generators.

The following diagram depicts the effect of an $X$ error on a single qubit. Here, the assumption is that our $2L^2$ qubits were previously in a state contained in the code space of the toric code, causing all of the stabilizer generator measurements to output $+1.$ The $Z$ stabilizer generators detect $X$ errors, and there is one such stabilizer generator for each tile in the figure, so we can indicate the measurement outcome of the corresponding stabilizer generator with the color of that tile: $+1$ outcomes are indicated by white tiles and $-1$ outcomes are indicated by gray tiles. If a bit-flip error occurs on one of the qubits, the effect is that the stabilizer generator measurements corresponding to the two tiles touching the affected qubit now output $-1.$

This is intuitive when we consider $Z$ stabilizer generators and how they behave. In essence, each $Z$ stabilizer generator measures the parity of the four qubits that touch the corresponding tile (with respect to the standard basis). So, a $+1$ outcome doesn't indicate that no $X$ errors have occurred on these four qubits, but rather it indicates that an even number of $X$ errors have occurred on these qubits, whereas a $-1$ outcome indicates that an odd number of $X$ errors have occurred. A single $X$ error therefore flips the parity of the four bits on both of the tiles it touches, causing the stabilizer generator measurements to output $-1.$

Next let's introduce multiple $X$ errors to see what happens. In particular, we'll consider a chain of adjacent $X$ errors, where two $X$ errors are adjacent if they affect qubits touching the same tile.

The two $Z$ stabilizer generators at the endpoints of the chain both give the outcome $-1$ in this case, because an odd number of $X$ errors have occurred on those two corresponding tiles. All of the other $Z$ stabilizer generators, on the other hand, give the outcome $+1,$ including the ones touching the chain but not at the endpoints, because an even number of $X$ errors have occurred on the qubits touching the corresponding tiles.

Thus, as long as we have a chain of $X$ errors that has endpoints, the toric code will detect that errors have occurred, resulting in $-1$ measurement outcomes for the $Z$ stabilizer generators corresponding to the endpoints of the chain. Note that the actual chain of errors is not revealed, only the endpoints! This is OK — in the next subsection we'll see that we don't need to know exactly which qubits were affected by $X$ errors to correct them. (The toric code is an example of a highly degenerate code, in the sense that it generally does not uniquely identify the errors it corrects.)

It is, however, possible for a chain of adjacent $X$ errors not to have endpoints, which is to say that a chain of errors could form a closed loop, like in the following figure.

In such a case, an even number of $X$ errors have occurred on every tile, so every stabilizer generator measurement results in a $+1$ outcome. Closed loops of adjacent $X$ errors are therefore not detected by the code.

This might seem disappointing, because we only need four $X$ errors to form a closed loop (and we're hoping for something a lot better than a distance 4 code). However, a closed loop of $X$ errors of the form depicted in the previous figure is not actually an error — because it's in the stabilizer! Recall that, in addition to the $Z$ stabilizer generators, we also have an $X$ stabilizer generator for each vertex in the lattice. And if we multiply adjacent $X$ stabilizer generators together, the result is that we obtain closed loops of $X$ operations. For instance, the closed loop in the previous figure can be obtained by multiplying together the $X$ stabilizer generators indicated in the following figure.

This is, however, not the only type of closed loop of $X$ errors that we can have — and it is not the case that every closed loop of $X$ errors is included in the stabilizer. In particular, the different types of loops can be characterized as follows.

1. Closed loops of $X$ errors with an even number of $X$ errors on every horizontal line and every vertical line of qubits. (The example shown above falls into this category.) Loops of this form are always contained in the stabilizer, as they can effectively be shrunk down to nothing by multiplying them by $X$ stabilizer generators.

2. Closed loops of $X$ errors with an odd number of $X$ errors on at least one horizontal line or at least one vertical line of qubits. Loops of this form are never contained in the stabilizer and therefore represent nontrivial errors that go undetected by the code.

An example of a closed loop of $X$ errors in the second category is shown in the following diagram.

Such a chain of errors is not contained in the stabilizer because every $X$ stabilizer generator places an even number of $X$ operations on every horizontal line and every vertical line of qubits. This is therefore an actual example of a nontrivial error that the code fails to detect.

The key is that the only way to form a loop of the second sort is to go around the torus, meaning either around the hole in the middle of the torus, through it, or both. Intuitively speaking, a chain of $X$ errors like this cannot be shrunk down to nothing by multiplying it by $X$ stabilizer generators because the topology of a torus prohibits it. The toric code is sometimes categorized as a topological quantum error correcting code for this reason. The shortest that such a loop can be is $L,$ and therefore this is the distance of the toric code: any closed loop of $X$ errors with length less than $L$ must fall into the first category, and is therefore contained in the stabilizer; and any chain of $X$ errors with endpoints is detected by the code.

Given that the toric code uses $2L^2$ qubits to encode $2$ qubits and has distance $L,$ it follows that it's a $[[2L^2,2,L]]$ stabilizer code.

---

Correcting errors

We've discussed error detection for the toric code, and now we'll briefly discuss how to correct errors. The toric code is a CSS code, so $X$ errors and $Z$ errors can be detected and corrected independently. Keeping our focus on $Z$ stabilizer generators, which detect $X$ errors, let us consider how a chain of $X$ errors can be corrected. ($Z$ errors are corrected in a symmetric way.)

If a syndrome different from the $(+1,\ldots,+1)$ syndrome appears when the $Z$ stabilizer generators are measured, the $-1$ outcomes reveal the endpoints of one or more chains of $X$ errors. We can attempt to correct these errors by pairing together the $-1$ outcomes and forming a chain of $X$ corrections between them. When doing this, it makes sense to choose shortest paths along which the corrections take place.

For instance, consider the following diagram, which depicts a syndrome with two $-1$ outcomes, indicated by gray tiles, caused by a chain of $X$ errors illustrated by the magenta line and circles. As we have already remarked, the chain itself is not revealed by the syndrome; only the endpoints are visible.

To attempt to correct this chain of errors, a shortest path between the $-1$ measurement outcomes is selected and $X$ gates are applied as corrections to the qubits along this path (indicated in yellow in the figure). While the corrections may not match up with the actual chain of errors, the errors and corrections together form a closed loop of $X$ operations that is contained in the stabilizer of the code. The correction is therefore successful in this situation, as the combined effect of the errors and corrections is to do nothing to an encoded state.

This strategy won't always be successful. For example, a different explanation for the same syndrome as in the previous figure is shown in the following figure.

This time, the same chain of corrections as before fails to correct for this chain of errors, because the combined effect of the errors and corrections is that we obtain a closed loop of $X$ operations that wraps around the torus, and therefore has a nontrivial effect on the code space. So, there's no guarantee that the strategy just described, of choosing a shortest path of $X$ corrections between two $-1$ syndrome measurement outcomes, will properly correct the error that caused this syndrome.

Perhaps more likely, depending on the noise model, is that a syndrome with more than two $-1$ entries is measured, like the following figure suggests.

In such a case, there are different correction strategies known. One natural strategy is to attempt to pair up the $-1$ measurement outcomes and perform corrections along shortest paths that connect the pairs, as is indicated in the figure in yellow. In particular, a minimum-weight perfect matching between the $-1$ measurement outcomes can be computed, and then the pairs are connected by shortest paths of $X$ corrections. The computation of a minimum-weight perfect matching can be done efficiently with a classical algorithm known as the blossom algorithm, which was discovered by Edmonds in the 1960s.

This approach is generally not optimal for the most typically studied noise models, but based on numerical simulations it works very well in practice below a noise rate of approximately 10%, assuming independent Pauli errors where $X,$ $Y,$ and $Z,$ are equally likely. Increasing $L$ doesn't have a significant effect on the break-even point at which the code starts to help, but does lead to a faster decrease in the probability for a logical error as the error rate decreases past the break-even point.