Wednesday 10 February 2016

4 - Decoding Without Looking

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

We have some information. We want to store it for a long time without it getting messed up. As we saw here, that’s no problem. We can just write it down many times, and keep checking on the copies. The majority will usually have the correct information. If any disagree, we assume that they got messed up and replace them with something that agrees with the majority.

This is all well and good if our information is the kind of normal information that we deal with in day-to-day life. But what if it’s quantum information? This can have hold multiple different messages at the same time in a weird quantum way. If we try to correct errors in the way described above, we have to look at all the copies to see what message they have. As soon as we do that, it has to choose just one of the multiple messages and the quantumness is lost. Any fancy quantum effects that we were relying on are gone.

To solve this problem we somehow have to find out which of the copies agree with each other, without ever finding out exactly what they say. Then we can poke the ones that disagree until they agree again. This will correct the errors and the majority will win, all while maintaining the quantumness.

How do we measure how different the copies are without getting any information we don’t want? We’ll need to be clever in choosing exactly how we are going to store our information. Writing it down on a piece of paper isn’t going to be our best option. Instead we need something that’ll let us use some fancy physics. Something like magnets!

Let’s say the information that we want to store is something simple: just a ‘yes’ or ‘no’. Rather than writing this down many times, let’s use a bunch of magnets. If we want to store the information ‘yes’, we place all the magnets with their north pole facing north. For ‘no’ we place them with the north pole facing south. We use plain magnets that don’t have anything written on them telling us which way is north or south. We can only find that out if we use a compass. So we won’t be able to easily tell if they say ‘yes’ or ‘no’.

When it’s time for our weekly check up, we can go around all the safe places that we keep our magnets. Let’s suppose we numbered our magnets 1, 2, 3, and so on. We can get the first one and the second and put them side-by-side. If they agree, they will stick together. It doesn’t matter if they are both facing north or south, they will stick just the same. Then you’ll know that they agree, without knowing what information they are storing. Similarly, if they repel each other you’ll immediately know that one says ‘yes’ while the other says ‘no’. You know they are different, but you have no idea which is which. We can then compare the second and the third in the same way, and then the third and the fourth and so on. This will give us all the information we need to decode.

Let’s suppose we used nine magnets. The results we get after a weekly check up might then be something like this

1 - a - 2 - a - 3 - a - 4 - d - 5 - d - 6 - a - 7 - a - 8 - a - 9

Here I’ve put an ‘a’ between magnets that agree, and a ‘d’ when they disagree. In this example, the fifth magnet is found to disagree with both neighbours. Since there are only two options, this means that the fourth and sixth magnets must agree with each other. For example, if the fourth is ‘yes’, the disagreeing fifth must be ‘no’. Since the fifth also disagrees with the sixth, this must be ‘yes’ too.

It is clear to see which magnets are in the majority. 1, 2, 3, 4, 6, 7, 8 and 9 all agree. Only 5 disagrees. The fifth is therefore most likely an error. We rotate it so that it agrees with all the others, and our error is corrected.

A more complicated example would be something like

1 - a - 2 - d - 3 - a - 4 - d - 5 - a - 6 - a -7 - d - 8 - d - 9

Here we can see that 1 and 2 agree with each other, and 3 and 4 agree with each other. But 1 and 2 disagree with 3 and 4. But who is in the majority? Looking at the other results we find that 5, 6, 7 and 9 are on the side of 1 and 2, but only 8 joins the side of 3 and 4. So it seems that 3, 4 and 8 are the ones with errors. They are the ones we should rotate.

Whatever happens, these measurements will always give us enough information to find out who is in the majority. It tells us where the errors are and how to correct them without ever telling us what the majority says. This decoding method is therefore perfectly compatible with the needs of quantum information.

Of course, things aren’t quite so easy. We can’t actually use big lumbering things like magnets to store quantum information. These will interact with nearby magnets, like the Earth’s magnetic field or any compasses in the area, and tell them which way they are pointing. So even if we don’t look at the information they are storing, the nearby magnets will. The quantumness will get ruined anyway.

To solve this we need to do two things. Firstly, use something instead of a magnet that isn’t going to gossip the information so readily. One thing that we often think about is the spin of an electron. Really this is actually a magnet. But it’s a tiny magnet. A really tiny magnet. It doesn’t give up its secrets as easily as the big ones that we stick on fridges. Again we can use physics to get the information we need, about whether neighbouring spins store the same information or not. The process will be a bit different to big magnets, but principle of harnessing their interactions is the same.

The other thing we need to do is build some extra fanciness into our error correction. At the moment, we are just looking at how to correct the kinds of errors that turn ‘yes’ to ‘no’ and vice-versa. It’s an important kind of error to correct, but so is the leakage of information to things that aren’t supposed to know it. We need our error correction to stop that too. We’ll get on to how to do that soon enough. Nexttime, however, it'll be time to meditate on all that we've done so far.

No comments:

Post a Comment