Friday 4 March 2016

6 - The Toric Code (part 1)

This is part of a project to get people involved with quantum error correction. See here for more info.

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 noisy 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 its 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 0 or 1 by 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.

This grid has lots of squares. Qubits live in the little ones, so we'll just refer to these as 'qubits'. The big white ones we will just call 'white squares'. The smaller blue ones will be 'blue squares'.

The edges of this grid are a bit odd: 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.

What patterns of bit values have all even squares? 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.

The example labelled (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. The one labelled (b) has a string of 1’s passing through some of the squares. When this string 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 two to the sum. Since two is even, the squares stay even. The only way for the string to leave every square that it enters is for it’s ends to join up, making a loop.

If you had (a) and wanted (b), all you’d need to do is flip the bits around the loop. Flipping bits around a loop always adds or removes a 1 when it enters a square, and does the same when it leaves. It doesn't matter what the original bit values are: loops of bit flips never change whether the squares are even or odd.

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.

No comments:

Post a Comment