4. The story so far
This is the fourth post in a series on quantum error correction. For other parts, check out the link at the bottom.
In the next set of posts we will be moving on to the promised land: we will start looking at surface codes. These were everyone’s favourite codes back when I first wrote these blogs in 2016, and they are still at the top in 2021 too. They are the foundation of many research careers, including mine, and are the basis of the ‘Decodoku’ citizen science project that gave this blog its name.
But I am getting ahead of myself. It’s easy to become a giddy fanboy when confronted with something like surface codes! So before we embark upon this pilgrimage, we must prepare ourselves with quiet contemplation. We must reflect upon all that we have done thus far, so I will tell you the story again. But this time it will be a bit more abstract, and a lot shorter.
What is error correction?
Sometimes we need to send information. Sometimes we need to save information. But errors are always hiding around the corner, waiting to mess it all up. To deal with them, we use error correction.
The information that we usually send and save is usually quite complicated, like Christmas lists and selfies. So let’s just consider the most simple of all messages, the basic unit from which all can be built, the atom of information: the bit. This is just one of two numbers, 0 and 1.
The simplest type of error that can affect a bit is called a bit flip. This is when some gremlin* comes along and replaces our 0 with a 1, and our 1 with a 0. If the chance of this is one in a billion, probably we won’t care too much. But when probability is too high, we need to do something about it.
In that case, the thing we do is encode our information. No longer do we entrust our message to a single bit. Instead we get loads of bits, and get them all to carry our message together. There are lots of ways to do this. Some are more complicated that others. The simplest is just to set them all to the same value. If we want to store a 0, we set all bits to 0. For a 1 we set them all to 1. This is called the repetition code.
Once a few bit flips happen, our encoding will get a bit messed up. It will no longer unambiguously tell us that our message is 0 or 1. With the repetition code, we might have our bits disagreeing: some will say 0 and others will say 1. We need to work out who is lying. We need to work out what the original message was. This process is called decoding. For the repetition code we can just look at the majority opinion. Whichever value there is more of is most likely to be our original message.
For more details, see part 1.
Quantum Information
Here are some fairly obvious constrains that apply to bits:
- A bit can contain no more than a single bit of information.
- When we look at its value, we will see either a
0or a1.
Given these fairly clear properties, it would seem that there is no possibility to do anything new and interesting with bits. They seem doomed to be no more than a simple 0 or 1. But this is actually not the case at all. It is possible to make objects that satisfy the two constraints above, but which allow methods of information processing that are impossible with normal bits.
To do this we need to let our bits behave in a quantum mechanical way. This means that they only need to be sure of whether they are 0 or 1 when we look at them. When we are not explicitly reading out their value, they are allowed to have a more complex inner life, known as a quantum superposition state. It is by manipulating these superpositions, and only reading out an output when it is absolutely needed, that we can achieve new quantum kinds of computation, communication and cryptography. We call these quantum bits, qubits.
Unfortunately, qubits are not immune against bit flips. In fact, they are even more prone to them! Error correction is again required.
Qubits also experience another kind of error, one that doesn’t bother bits at all. This is called dephasing, and happens when the horrible little gremlins come and look at our qubits. This causes them to become just 0 or 1 when they are supposed to be in a quantum superposition. With the quantum magic gone, our quantum computer becomes useless.
It’s not just the gremlins we need to worry about. It’s us too! If we want to store information for a long time, we need do decoding regularly to find and remove any errors as they happen. For that we need to look at our qubits. But if we end up finding out whether they are 0 or 1, we will have removed the quantum magic. We will have dephased them to the max. Our efforts to get rid of errors will then have caused them!
Because of this, we need a new kind of error correction for qubits. It needs to be able to find and correct bit flips, but without causing dephasing. It also needs to find places where dephasing has happened and sort that out too.
For more details, see part 2.
Decoding without looking
Now we have a tricky problem to solve. We need to look for errors on our qubits, but we aren’t allowed to look at our qubits.
Actually, that’s not quite true. We just need to be careful when looking at them, to make sure that don’t just collapse down to boring 0s and 1s.
As an example, let’s consider a pair of qubits. If we look at both, there are four possible outcomes:00, 01, 10 and11.
Let’s consider the case where we have a superposition of 00 and 11. If this were to suffer a single bit flip (on either qubit) we’d get a superposition of 01 and 10. How can we tell if this error has occured.
The easiest way is to simply look at both qubits. If we get 00 or 11, we know that we had the original superposition. For 01 or 10 we’ll know we had the flipped one. But this easy method had the side-effect of destroying the superposition.
A better way is to bring in a third qubit, and have it interact with our pair. This interaction is designed to leave the third qubit in the state 0 when the pair are 00 or 11, but to put it in the state 1 when the pair are 01 or 10. If this process is done carefully, it will not change the superpositions at all. However, measuring the third qubit allows us to know whether we are in the 00/11 superposition or the 01/10 one. And then we know whether the error happened or not.
For quantum error correction we’ll do exactly this kind of thing. But lots of it!
Correcting dephasing
Dephasing happens when we, or the gremlins, find our information we aren’t supposed to. It happens when our quantum message, which is supposed to be in a superposition of 0 and 1, is forced to choose whether to be one or the other.
If our quantum message is stored on a single qubit, there will be some probability that a gremlin will come and look at it, making it dephase. If it is repeated across many qubits, there is a lot more places that the gremlins can look at it. They can find out if our message is 0 or 1 by looking at any of the many copies, and so there’s a lot more ways to make it dephase. The repetition encoding, which protects against bit flip errors so well, actually makes dephasing more likely!
To solve this problem, we need better ways to encode our qubits. We need some truly quantum error correction. Let us go on to the promised land and find it!
When the next part is out, you’ll find a link in the Twitter thread below.
* There aren’t really fairy folk messing with our bits. Not that we’ve observed, anyway. Errors are caused by our bits interacting with everything around them. Air bashes into them, nearby magnets tell them which way to point and innumerable other messy things happen which might make them do things they shouldn’t. But I like to think about it as naughty gremlims that like nothing better than trying to annoy us.
