Wednesday, 20 January 2016

1 - What is Error Correction?

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

What is Quantum Error Correction

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. He 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, this is very easy. 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'.

In this example the message is easy to understand, even after encoding. That will not always be so. For more complicated encoding it can seem like nonsense if we don't recognize the encoding. The sender must therefore first explain the encoding method used. The receiver can then develop a decoding method. This will let them extract the original message from what they have received, even when it has gotten a little garbled.

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.

No comments:

Post a comment