5. The Toric Code (part 1)
This is the fifth post in a series on quantum error correction. For other parts, check out the link at the bottom.
We want to build a quantum computer. For that we need quantum bits or qubits. The ones we can build will always be too noisy to be used directly. We need a method to build relatively noiseless qubits out of many noisy ones. This is quantum error correction.
In this post we will start looking at one particular way to do this: the toric code. This is part of a family of codes call the surface codes, introduced over a decade ago by Alexei Kitaev. When quantum computers actually get built, it seems most likely that it will be some variant of a surface code that is doing the error correction.
Pros and Cons of the Repetition Code
Before we look at the toric code, let’s again think about the repetition code that can be used for error correction with bits (if you are new, see the last post for a summary).
In the repetition code we take many bits that are a too imperfect to be useful. Let’s call these physical bits. We want to use them to build one bit that is not very noisy at all, we’ll call this a logical bit. We can then use logical bits to store important information, like MP3s of songs by The Wurzels.
If we want our logical bit to have value 0, we set all the physical bits to 0. If we want it to be 1, we set them all to 1. So if we use seven physical bits, we’d have
0 0 0 0 0 0 0 or 1 1 1 1 1 1 1
If noise causes some of the noisy physical bits to flip value, we end up with something like
0 0 1 1 0 0 0 or 1 1 0 0 1 1 1
To find traces of these errors we look at each pair of neighbouring physical bits, and see if their value is the same or different. It should always be the same, but strings of bit flips will have a pair that are different at each end. By finding these and pairing them up we find the errors.
We could also interpret these measurements a little differently. We can imagine that we add the two neighbouring bit values. Then we only look at whether the result is odd or even. When they are the same, the result is always even (0+0=0 and 1+1=2). When they are different, the result is always odd (0+1=1+0=1). This interpretation will help us when we make a more complicated code later in this post.
Suppose we want to flip the value stored in our logical bit. We want to flip it from 0 to 1 or vice-versa. To do this, we just flip every one of the physical bits.
0 0 0 0 0 0 0 → 1 1 1 1 1 1 1 or 1 1 1 1 1 1 1 → 0 0 0 0 0 0 0
All the bit values remain the same, so doing this leaves no trace. This is good, because it wasn’t an error that did this. It was us.
Unfortunately, it is possible for errors to do this too. The probability of a bit flip error on every physical bit is very small, but it is possible. If this happens, it looks exactly like something that we might do on purpose. There is no way we could ever detect these errors. If they happen, we fail.
Obviously, we don’t want to fail very often. We want the probability to be very small. This is true for the repetition code, because flipping the logical bit is not easy: It needs us to flip every physical bit. If it is hard for us, it is hard for the gremlins that cause errors too. If it’s hard for them, it won’t happen often.
We could also use this code for qubits, using it to build a logical qubit from many noisy physical ones. It will make it rare for the logical qubit to get flipped, just as it does for logical bits.
Unfortunately, qubits suffer from another kind of noise: unwanted measurement. They are not restricted to just being 0 or 1, they can be a quantum superposition of both at the same time. If we or some gremlin look at whether our logical qubit is 0 or 1, it destroys the superpositions that we need for quantum computation. With the repetition code you can measure whether it is 0 or 1 by looking at any of the physical qubits. This makes it very likely that something will interact with them and learn the forbidden information.
So how do we protect a qubit from both types of error. We need the following two things.
- Flipping our logical bit can only be done by flipping lots of physical bits.
- It shouldn’t be possible to find out if the logical qubit is
0or1by just looking at one physical qubit. Instead, finding out about the logical bit can only be done by looking at lots of physical bits.
Now let’s look at a code that does this.
The Toric Code
For the toric code we don’t put our qubits in a line, we put them in a grid pattern. Here’s the grid pattern we used in the game ‘Decodoku’, which this blog was originally written to accompany back in 2016. It’s a nice pattern of interlocking squares.
The different elements of this pattern are used to represent different things.
- The qubits live at the points where the squares intersect.
- Around each square is a collection of four qubits. We’ll refer to these as white squares.
- The blue squares are another collection of four qubits.
Another thing to note are the periodic boundary conditions. This just means that the top is connected to the bttom, and the left side to the right side. So if you move off the top you appear at the bottom, and if you move off the right you appear at the left. The half squares on the top and bottom are actually different halves of the same square. This means that the grid is wrapped around a torus, which is a doughnut shape. It is also possible to make similar quantum codes on different surfaces. These are the surface codes.
In the repetition code we looked at whether neighbouring bits had the same or different value (or whether their sum was even or odd). We do something similar in the toric code, but not for pairs of qubits. Instead we will do it for the four qubits around each of the white squares. We add up the four bit values for each of these squares, and see whether the result is even or odd.
These results are what we’ll use to look for signs of errors. We’ll try to keep every such that all these squares are always even. If one is ever odd, we’ll know that an error happened.
So what patterns of bit values keep all the white squares even? Some examples are below.
You may be wondering about the half numbers on the edges. The halves on the left will join up with the ones on the right when we wrap this around a torus. The same is true for the top and bottom.
Example (a) is the easiest of all: everything is 0, so everything adds up to zero. Zero is even (don’t let anyone tell you otherwise), so all the squares are even. Example (b) has some 1s around a loop. Thinking of it as a loop helps to understand its effects: when the loop enters a square, we add 1 to that square’s sum. When it leaves we add another 1. As long as it leaves every square it enters, we will add 2 to the sum. Since 2 is even, the squares stay even. The only way for the string to leave every square that it enters is for its ends to join up, making a loop. So if we have loops of 1s, then the white squares will always be even.
The two other examples have a string that stretches from left to right. This is also a loop, because the left and right edges are the same. The half squares that it passes through on left and right are just halves of the same square. In (c) we have the same bit values as (a), but with the bit values flipped on one particular line from left to right. Similarly, (d) is exactly the same as (b), except for flips on the exact same line.
The two most important things to get from all this are:
- When all squares are even, the bit values look like loops of 1’s on a background of
0’s; - Doing bit flips around a loop doesn’t change whether any square is even or odd.
Now we can start thinking about how to store information in this thing. But that’ll have to wait until next time.
When the next part is out, you’ll find a link in the Twitter thread below.
