1. What is Quantum Error Correction?

5 years ago I had ran a citizen science project based on quantum computing. More specifically it was based on quantum error correction, which is how we plan to help quantum computers solve problems despite the effects of imperfections. For those who wanted to know more, I had a blog to explain it all.

Now, 5 years on, quantum computing is even more popular than ever. Cloud-based quantum computers, like those of IBM Quantum, allow anyone to use prototype devices. And programming frameworks such as Qiskit let anyone dabble with writing quantum programs.

So it seems like a good time to remaster my old blog posts. Here is the first in a series of many. An introduction to quantum error correction, without the assumption that you’ve done any physics or maths beyond high school.

What is quantum error correction. Is it as complicated as it sounds? First we will just look at error correction. Then we’ll mix the quantum in later.

Suppose we want to send a message. We can never do this perfectly. It is always possible that it will get lost, damaged or garbled. When the probability of this is too high, we need to protect the message somehow. For this we use error correction.

Let’s consider an example: you are talking on the phone with your friend. He asks you whether you’d like to come round for dinner, and you say ‘Yes’. But the connection is bad: with a probability of 1 in 100 your answer gets garbled so much that your ‘Yes’ sounds like ‘No’.

When you go to his house later, there will be no dinner. Your friend heard ‘No’, and so wasn’t expecting you. It will be a bit embarrassing, but it won’t be so bad. A probability of 1% is not too high for the risk of a bit of embarrassment between friends.

If you have nuclear weapons, however, your conversations are much more important! Suppose you ask your boss whether it is time to launch the nukes. If he says ‘No’ and you hear ‘Yes’, it would be very bad. Naturally, we need to avoid this. A chance of 1 in 100 here would be much too high. The world is in danger!

How can we solve this problem? Your boss can change the message so that it is more robust. This method is call ‘encoding’. A simple encoding is simply to repeat yourself.

Suppose that your boss doesn’t just say ‘No’, but ‘No! No! No! No! No!’. Maybe one of the words will get garbled and we’ll hear something like ‘No! No! No! Yes! No!’. There will still be many more ‘No’ than ‘Yes’, so you probably won’t launch the nukes and the world is safe. If two get garbled there are still more ‘No’ than ‘Yes’. So the message is still clear.

There will be more ‘Yes’ than ‘No’ only when three or more get garbled. In this case it seems like we should launch, which would be a big mistake!

What is the probability of such an error? We’ve already said that the probability of one word getting garbled is 1 in 100. The probability for three or more is then 1 in 100,000, which is a lot less likely!

If even this is still too high, we can repeat more than 5 times. If we used 7 repetitions, there needs to be four or more garbled words before we accidentally destroy the world. The probability of that is 1 in 3 million. The probability gets less and less when we use more repetitions.

In the above process we haven’t just been using encoding. We have also used ‘decoding’. This is when we try to find out what message our boss has sent.

For the repetition encoding, it is very easy to decode. We know that garbled messages are rare, so we trust the majority. When there are more ‘No’ than ‘Yes’, we assume that our boss said ‘No’. For more ‘Yes’ than ‘No’ we assume ‘Yes’.

Now we have all the ingredients of error correction. We have a message to send, and it is very important. So important that no error can be tolerated. To ensure that it stays secure, the sender uses an encoding method. The receiver then uses a decoding method to get the message out again, while correcting any parts that got messed up.

This is error correction in a nutshell, even when it’s quantum.

Once the next part is posted, you’ll find a link in the Twitter thread below.