5 - The story so far

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

In the next set of posts we will be moving on to the promised land: we will start looking at surface codes. These are a way of encoding quantum information that is especially awesome. They are the foundation of many research careers, including mine, and are the basis of the decodoku games.

Before we embark upon this pilgrimage, we must prepare ourselves. 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 1 in a billion, probably we won’t care too much. But when probability is too high, we need to do something about it.

What 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.

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 encoding, for example, 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 repetition we can just look at the majority opinion. Whichever value there is more of is our original message (most likely).

See here for more info.

Quantum Information

If our bit obeys the laws of quantum mechanics, it doesn’t always just need to be 0 or 1. It can keep its options open and be 0 and 1 at the same time: a quantum superposition. This has to stop once we look at it, and it’ll choose one or the other. Until then, we can prod it in weird quantum ways and use it to do new quantum kinds of computation, communication and cryptography. This kind of bit, a quantum bit, is called a qubit.

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.

See here and here for more info.

Decoding without looking

As our first step towards fully quantum error correction, let's consider some almost quantum error correction. This will find and correct bit flips without causing any dephasing. Let’s try to do this with the repetition encoding from before, which will use a bunch of qubits. If we want our quantum message to be 0, we set them all to 0. For 1 we set them all to 1. Any superposition of 0 and 1 will be the superposition of them all being 0, and all being 1. In every case, every qubit should agree with every other. Any disagreement is a sign that a bit flip has happened.

To decode, we just look for disagreement. One way to do that is to sit our qubits on a line. We then go along and ask every pair of next-door-neighbours whether they agree or disagree with each other. This tells us nothing about whether they are 0 or 1, so it doesn’t affect the superposition. Instead it tells us everything we need to decode without causing any dephasing. By looking at which qubits agree with each other we can see which ones are in the majority. We can then flip the minority back to their (hopefully) original values so that all agree again. All bit flips are found and unflipped. The errors are corrected.

See here for more info.


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!


* 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.

** In a previous version I used 'decoherence' here. That was a bit misleading, since bit flip noise is also a kind of decoherence. Using 'dephasing' is not entirely without problems either, but it's better.