To help us build a quantum computer, click here.
Thursday, 3 November 2016
Friday, 23 September 2016
Doing an experiment with the Quantum Experience
This is part of a project to get people involved with quantum error correction. See here for more info.
A few months ago, IBM launched their Quantum Experience. It lets you design programs to run on a quantum computer, and then actually run them! It's only a five qubit quantum computer, so it can't do a huge amount. But it can do a lot. There's a fair few important experiments from the past few years that you can now do for yourself, in the comfort of your own home.
Earlier this week, I realized what this meant for me. A few years ago I proposed an experiment to braid anyons on a surface code. It was published In the Journal Of Physics A, though you can get it for free here too.
Anyons and surface codes are things I've talked about here and on my YouTube channel quite a lot. They are the basis of the games that form the cornerstone of the Decodoku project. So if this experiment ever got actually implemented, it is something I would be wanting to tell you all about it.
Now it has been done! By me! Using the Quantum Experience! I spent this week designing, implementing and data processing. I did an experiment, in which I made and braided anyons. Now it's time to tell you all about it.
I wrote a paper, designed to be both a proper scientific paper and something accessible to a (suitably motivated) member of the public. You can find it here. I also made a video to explain it to more normal members of the public.
I encourage you all to get over to the Quantum Experience and have fun. If I, a staunch theorist, can do an experiment, so can you!
A few months ago, IBM launched their Quantum Experience. It lets you design programs to run on a quantum computer, and then actually run them! It's only a five qubit quantum computer, so it can't do a huge amount. But it can do a lot. There's a fair few important experiments from the past few years that you can now do for yourself, in the comfort of your own home.
Earlier this week, I realized what this meant for me. A few years ago I proposed an experiment to braid anyons on a surface code. It was published In the Journal Of Physics A, though you can get it for free here too.
Anyons and surface codes are things I've talked about here and on my YouTube channel quite a lot. They are the basis of the games that form the cornerstone of the Decodoku project. So if this experiment ever got actually implemented, it is something I would be wanting to tell you all about it.
Now it has been done! By me! Using the Quantum Experience! I spent this week designing, implementing and data processing. I did an experiment, in which I made and braided anyons. Now it's time to tell you all about it.
I wrote a paper, designed to be both a proper scientific paper and something accessible to a (suitably motivated) member of the public. You can find it here. I also made a video to explain it to more normal members of the public.
I encourage you all to get over to the Quantum Experience and have fun. If I, a staunch theorist, can do an experiment, so can you!
Saturday, 23 July 2016
Quantum Computation with the simplest maths possible
This is part of a project to get people involved with quantum error correction. See here for more info.
I and a bunch of my colleagues recently did an AMA on the science part of Reddit. There we answered hundreds of questions that people posed us about quantum technology, and quantum computation in particular. This post is inspired by some of the questions we got. This is quantum computing, explained as simply as I can.
Normal Computers
Before I try to explain simply what a quantum computer does, let's start with normal computers.
Computers do maths. Whether you are browsing Facebook or jumping on Goombas, they are just doing maths.
Maths involves numbers. We, as humans, like to write numbers using a base 10 system, so they come out looking like 42 or 3.14159. For computers it's easier to write them in binary. These same two numbers would then come out as 101010 and 11.00100100011. All numbers in binary are a string of 0s and 1s. We call each digit a bit.
To do complicated maths, computers break the problem down into lots of tiny blocks of maths, which we call gates. These are basic building blocks of mathematics. The ones that computers use are typically just lots of ways of comparing two bits. For example, the AND gate takes two bits and tells you if they are both 1 or not. The XOR gate takes two bits and adds them up, then tells you if the result is even or odd.
Another example is what I call the reversible-(N)AND gate, which we will be getting a bit more intimate with later. This looks at three bits. It does a comparison of the first two, with the third one telling it which comparison to do.
To tell you what the reversible-(N)AND does we have a picture called a circuit diagram
and a table, called a truth table.
These tell the story of three bits that go through this gate. They start on the left. The top one starts off as 0 or 1. Rather than fix it to one or the other, let's just call it a for now. The other two start off and 0 or 1 too. Let's call them b and c.
They each follow their lines through the gate. When the top one comes out, it'll always be the same as it went in. The same is true for the bottom one. But the middle one does something more interesting. If c is 0, the output is only 1 if both a and b are 1. The fancy name for this is an AND gate. If the middle bit starts as 1, it'll come out the opposite. The fancy name for this is a NAND gate.
NAND gates are pretty awesome things. With enough NAND gates you can solve any problem. Some problems need more gates that others. Perhaps you remember adding and multiplying numbers at school. Adding is pretty easy, even if the numbers have lots of digits. You just go along them doing a bunch of little additions. Multiplying, however, becomes a right pain for big numbers.
Computers feel that pain too. The number of gates you need to multiply two numbers is more than you need to add them. As as the numbers get more and more digits, it gets worse and worse.
But there are problems much worse than multplication. Factoring numbers, for example. For big enough numbers, this would need as many gates as there are atoms in the universe! Even if we took a supercomputer, and reused its gates many times, it would take the age of the universe to get all the maths done! But for adding numbers just as big, even your own computer could do it while you make a cup of tea.
Because of this, we can wonder if the gates we use are actually the best ones. Maybe we could find other gates, that could be used to solve problems like factoring much more easily. If gates are the building blocks of maths, perhaps we are currently stuck using Duplo. No wonder our maths is big and bulky if we try to build intricate things frm Duplo! We need to find the Technic.
The problem is that we have to get something to do the gates for us. For the gates in a normal computer, we use transistors. These are magical rocks, that do fun things when you poke them with electricity. This makes them perfect for doing the gates.
For new gates, we need new magic rocks. Where might we find them? Well, one kind of problem that is hard for normal computers is simulating quantum particles. But quantum particles manage to sort themselves out pretty easily. So perhaps we could harness their quantumness for new gates. That is exactly what a quantum computer would do.
Qubits
A qubit is a little like a ball. Like this ball.
Ignore the eye and stuff. But don't ignore the valve near the top. The valve is an important part of our qubit.
When the valve is at the top, we say that the qubit is in state 0. When it's at the bottom, we say the qubit is in state 1. When it is somewhere else, we say that it is some superposition of 0 and 1. There are an infinite number of places it can be, and so an infinite number of different possible superpositions.
But there is a big difference between a qubit and a ball with a valve on. For the ball, we can ask "where is the valve?", and then look at it and find out exactly where it is. For a qubit, the laws of physics don't let us know that much. All we can ask is something like "is it 0, or is it 1?"
The qubit is not allowed to say "I'm a superposition, leave me alone." It has to choose either 0 or 1. If it is 0, it says 0. If it is 1, it says 1. If it is a superposition, it randomly chooses 0 or 1. If it is near the top, it is more likely to go for 0. Near the bottom will most likely go for 1. For the equator it is 50/50.
A bit is less complicated. It has no need for some wierd story about a ball. It is just 0 or 1. We can ask it which it is, and we can turn 0's into 1's and 1's into 0's if we want. But we can't do anything more.
With a qubit, we can do more. We can rotate it. We can rotate a 0 into a 1 (which we call a NOT gate). We can do the same rotation, but only half-way. Let's call that a halfNOT. And we can also do any other fancy rotation that we could ever imagine. But we won't today. We'll just stick with halfNOTs.
Controlled gates
More interesting than just rotations of single qubits, are controlled gates. These deal with two qubits, with one called the control and the other called the target. They look at whether the control is in state 0 or 1. If 0, they then do nothing. If 1, they do some rotation on the target qubit.
The most popular controlled gate is the controlled-NOT. This does a NOT gate to the target if the control state is 0 Here is our circuit diagram.
Here if the state of the control qubit, a, is 0, the bottom qubit comes out b. Just as it went in. But if a is 1, it comes out the opposite value. It has had a NOT done to it.
There's also another way we can think about this gate.
With this way of writing the story, b is replaced with whether or not a+b is odd. Both versions of the story are useful to keep in mind, and equally valid.
The examples above have the control either in state 0 or 1. So everything is nice and simple. But what if it was a superposition?
The way a controlled operation could be done is to ask the control whether it is 0 or 1. Make it decide one way or the other, and then do whatever is required to the target based on the result. But that's not very quantum.
Instead we can make the qubits interact, so that the controlled gate happens without ever making the control qubit decide. The undecidedness remains, and spreads to the target qubit. The end result is a superposition of the target in state 0 and the control without a NOT, and the target in state 1 and the control with a NOT.
Unfortunately, this is where we can no longer use balls to understand what's going on. A two qubit correlated superposition like this is an example of entanglement. Entanglement is what allows quantum computers to go beyond computers made out of balls, or even transistors.
Since we have to depart from the ball picture, we won't go to far into complicated entanglement for the rest of this post. We'll stick with entry level entanglement, but not too entry level. Rather than a controlled-NOT, let's go for a controlled-halfNOT and see what this gate lets us do.
Doing maths with a controlled-halfNOT
Using a controlled-halfNOT as our basic gate, can we do some maths? Can we find an algorithm that will solve some mathematical problem?
We'll start simple, and just try to do a reversible-(N)AND. But this is actually a pretty important thing. We can build a normal computer just from a bunch of NAND gates, which is something a reversible-(N)AND can do. So if controlled-halfNOTs can make reversible-(N)ANDs, they can do any maths.
First, let's start by taking a look at the circuit diagram for a controlled-halfNOT.
We can start off with a and b being simply 0 or 1. But after a halfNOT, the bottom qubit won't be simply 0 or 1 any more. It will be a quantum superposition. In this post we're not going to worry about the maths needed to write that down. Though you can check it our here.
Also, keep in mind that a controlled-NOT is just two controlled-halfNOTs. Because two halfNOTs are, of course, one NOT. So if we can do controlled half-NOTs, we can do controlled-NOTs too.
Now let's see how to make a reversible-(N)AND from a bunch of controlled-halfNOTs. But first we better remind ourself what it is supposed to do.
In the first part here, we do a couple of controlled-halfNOTs. The first one has the top qubit as the control and the middle one as target. The second has the bottom as control and the middle as target (that's why it's upside down).
If a and b are both 0, neither controlled-halfNOT does anything. If they are both 1, then both controlled-halfNOTs do a halfNOT on the middle qubit. That makes a full NOT. In both cases, this is exactly what we want from a reversible-halfNOT.
But it's not all good news. For the other two cases, where only a or b is 1, we want nothing to have been done to the middle qubit. Instead, one of the controlled-halfNOTs will do nothing, but the other will do a halfNOT!
To get rid of this, we need to know whether only a or b is 1, and use this knowledge to undo the unwanted halfNOT. We then need to unknow this information, because you can't going around knowing things about quantum systems without upsetting them.
Firstly, note that the cases that get it right (a and b are both 0, and a and b are both 1) are the those where a+b is even. The cases that get it wrong (a=0 and b=1 or vice-versa) are those where a+b is odd. And we know how to find out if a+b is odd or even. We do it with a controlled-NOT.
That's what the second part of the circuit does. There's a controlled not with the top qubit as control and the bottom as target, which results in the bottom one being 0 if a+b is even, and 1 if it is odd. This gate doesn't involve the middle qubit at all (even though it seems to cross it in our picture).
Now the bottom qubit knows whether the unwanted halfNOT happened. We don't ask it to tell us, because our brains have trouble unknowing things once they know them. We just use it to undo the unwanted halfNOT. This is done with three controlled-halfNOTs with the bottom qubit as control and the middle as target. This adds three more halfNOTS to the middle qubit only when that troublesome one is there already. That gives four halfNOTs in total, which is the same as two NOTs, which is the same as nothing. The unwanted halfNOT is gone!
Now the middle qubit is doing exactly what we need. But the bottom qubit isn't. It should come out as b, rather than tell us about whether a+b is odd. To make it unknow this information, we just do the controlled-NOT again. The second NOT undoes the first and returns the bottom qubit to b. Our reversible-(N)AND is now complete!
Here we have taken three qubits, that were definitely in the states 0 or 1. So they were pretty much just bits. At the end we also have three qubits that are definitely 0 or 1, and so are also basically just bits. But inbetween, their quantumness came in to play. Superpositions happened and got shunted around to do the maths we wanted to do. And that, is quantum computation.
Of course, normal computers can do reversible-(N)ANDs just fine. What we really need quantum computers for are problems that normal computers are rubbish at. The approach is the same. We start with our qubits just being bits, and we end with qubits being bits. But in between we do quantum stuff.
To get the full advantage of quantum computation, we'll need to use more than just a simple controlled-halfNOT. This is defintely part of the Lego Technic set of quantum gates, but it's one of the big and bulky ones. We need some of the more intricate gates to make really fancy computations, such all the possible rotations of a qubit. Add those in, and we can factor huge numbers while you make a cup of tea as well.
To find out more about that, a bit more maths is needed. Complex exponentials are pretty essential, but they aren't to everyone's taste. If you think you can handle it, check out my lecture notes here. You can also find someone else's explanation of things like this in a video here.
I and a bunch of my colleagues recently did an AMA on the science part of Reddit. There we answered hundreds of questions that people posed us about quantum technology, and quantum computation in particular. This post is inspired by some of the questions we got. This is quantum computing, explained as simply as I can.
Normal Computers
Before I try to explain simply what a quantum computer does, let's start with normal computers.
Computers do maths. Whether you are browsing Facebook or jumping on Goombas, they are just doing maths.
Maths involves numbers. We, as humans, like to write numbers using a base 10 system, so they come out looking like 42 or 3.14159. For computers it's easier to write them in binary. These same two numbers would then come out as 101010 and 11.00100100011. All numbers in binary are a string of 0s and 1s. We call each digit a bit.
To do complicated maths, computers break the problem down into lots of tiny blocks of maths, which we call gates. These are basic building blocks of mathematics. The ones that computers use are typically just lots of ways of comparing two bits. For example, the AND gate takes two bits and tells you if they are both 1 or not. The XOR gate takes two bits and adds them up, then tells you if the result is even or odd.
Another example is what I call the reversible-(N)AND gate, which we will be getting a bit more intimate with later. This looks at three bits. It does a comparison of the first two, with the third one telling it which comparison to do.
To tell you what the reversible-(N)AND does we have a picture called a circuit diagram
They each follow their lines through the gate. When the top one comes out, it'll always be the same as it went in. The same is true for the bottom one. But the middle one does something more interesting. If c is 0, the output is only 1 if both a and b are 1. The fancy name for this is an AND gate. If the middle bit starts as 1, it'll come out the opposite. The fancy name for this is a NAND gate.
NAND gates are pretty awesome things. With enough NAND gates you can solve any problem. Some problems need more gates that others. Perhaps you remember adding and multiplying numbers at school. Adding is pretty easy, even if the numbers have lots of digits. You just go along them doing a bunch of little additions. Multiplying, however, becomes a right pain for big numbers.
Computers feel that pain too. The number of gates you need to multiply two numbers is more than you need to add them. As as the numbers get more and more digits, it gets worse and worse.
But there are problems much worse than multplication. Factoring numbers, for example. For big enough numbers, this would need as many gates as there are atoms in the universe! Even if we took a supercomputer, and reused its gates many times, it would take the age of the universe to get all the maths done! But for adding numbers just as big, even your own computer could do it while you make a cup of tea.
Because of this, we can wonder if the gates we use are actually the best ones. Maybe we could find other gates, that could be used to solve problems like factoring much more easily. If gates are the building blocks of maths, perhaps we are currently stuck using Duplo. No wonder our maths is big and bulky if we try to build intricate things frm Duplo! We need to find the Technic.
The problem is that we have to get something to do the gates for us. For the gates in a normal computer, we use transistors. These are magical rocks, that do fun things when you poke them with electricity. This makes them perfect for doing the gates.
For new gates, we need new magic rocks. Where might we find them? Well, one kind of problem that is hard for normal computers is simulating quantum particles. But quantum particles manage to sort themselves out pretty easily. So perhaps we could harness their quantumness for new gates. That is exactly what a quantum computer would do.
Qubits
A qubit is a little like a ball. Like this ball.
Ignore the eye and stuff. But don't ignore the valve near the top. The valve is an important part of our qubit.
When the valve is at the top, we say that the qubit is in state 0. When it's at the bottom, we say the qubit is in state 1. When it is somewhere else, we say that it is some superposition of 0 and 1. There are an infinite number of places it can be, and so an infinite number of different possible superpositions.
But there is a big difference between a qubit and a ball with a valve on. For the ball, we can ask "where is the valve?", and then look at it and find out exactly where it is. For a qubit, the laws of physics don't let us know that much. All we can ask is something like "is it 0, or is it 1?"
The qubit is not allowed to say "I'm a superposition, leave me alone." It has to choose either 0 or 1. If it is 0, it says 0. If it is 1, it says 1. If it is a superposition, it randomly chooses 0 or 1. If it is near the top, it is more likely to go for 0. Near the bottom will most likely go for 1. For the equator it is 50/50.
A bit is less complicated. It has no need for some wierd story about a ball. It is just 0 or 1. We can ask it which it is, and we can turn 0's into 1's and 1's into 0's if we want. But we can't do anything more.
With a qubit, we can do more. We can rotate it. We can rotate a 0 into a 1 (which we call a NOT gate). We can do the same rotation, but only half-way. Let's call that a halfNOT. And we can also do any other fancy rotation that we could ever imagine. But we won't today. We'll just stick with halfNOTs.
Controlled gates
More interesting than just rotations of single qubits, are controlled gates. These deal with two qubits, with one called the control and the other called the target. They look at whether the control is in state 0 or 1. If 0, they then do nothing. If 1, they do some rotation on the target qubit.
The most popular controlled gate is the controlled-NOT. This does a NOT gate to the target if the control state is 0 Here is our circuit diagram.
Here if the state of the control qubit, a, is 0, the bottom qubit comes out b. Just as it went in. But if a is 1, it comes out the opposite value. It has had a NOT done to it.
There's also another way we can think about this gate.
With this way of writing the story, b is replaced with whether or not a+b is odd. Both versions of the story are useful to keep in mind, and equally valid.
The examples above have the control either in state 0 or 1. So everything is nice and simple. But what if it was a superposition?
The way a controlled operation could be done is to ask the control whether it is 0 or 1. Make it decide one way or the other, and then do whatever is required to the target based on the result. But that's not very quantum.
Instead we can make the qubits interact, so that the controlled gate happens without ever making the control qubit decide. The undecidedness remains, and spreads to the target qubit. The end result is a superposition of the target in state 0 and the control without a NOT, and the target in state 1 and the control with a NOT.
Unfortunately, this is where we can no longer use balls to understand what's going on. A two qubit correlated superposition like this is an example of entanglement. Entanglement is what allows quantum computers to go beyond computers made out of balls, or even transistors.
Since we have to depart from the ball picture, we won't go to far into complicated entanglement for the rest of this post. We'll stick with entry level entanglement, but not too entry level. Rather than a controlled-NOT, let's go for a controlled-halfNOT and see what this gate lets us do.
Doing maths with a controlled-halfNOT
Using a controlled-halfNOT as our basic gate, can we do some maths? Can we find an algorithm that will solve some mathematical problem?
We'll start simple, and just try to do a reversible-(N)AND. But this is actually a pretty important thing. We can build a normal computer just from a bunch of NAND gates, which is something a reversible-(N)AND can do. So if controlled-halfNOTs can make reversible-(N)ANDs, they can do any maths.
First, let's start by taking a look at the circuit diagram for a controlled-halfNOT.
We can start off with a and b being simply 0 or 1. But after a halfNOT, the bottom qubit won't be simply 0 or 1 any more. It will be a quantum superposition. In this post we're not going to worry about the maths needed to write that down. Though you can check it our here.
Also, keep in mind that a controlled-NOT is just two controlled-halfNOTs. Because two halfNOTs are, of course, one NOT. So if we can do controlled half-NOTs, we can do controlled-NOTs too.
Now let's see how to make a reversible-(N)AND from a bunch of controlled-halfNOTs. But first we better remind ourself what it is supposed to do.
Basically, the output is just c, unless both a and b are 1. In that case, the middle bit gets a NOT, to make it 1-c.
Here's how we do that with a bunch of controlled-halfNOTs.
In the first part here, we do a couple of controlled-halfNOTs. The first one has the top qubit as the control and the middle one as target. The second has the bottom as control and the middle as target (that's why it's upside down).
If a and b are both 0, neither controlled-halfNOT does anything. If they are both 1, then both controlled-halfNOTs do a halfNOT on the middle qubit. That makes a full NOT. In both cases, this is exactly what we want from a reversible-halfNOT.
But it's not all good news. For the other two cases, where only a or b is 1, we want nothing to have been done to the middle qubit. Instead, one of the controlled-halfNOTs will do nothing, but the other will do a halfNOT!
To get rid of this, we need to know whether only a or b is 1, and use this knowledge to undo the unwanted halfNOT. We then need to unknow this information, because you can't going around knowing things about quantum systems without upsetting them.
Firstly, note that the cases that get it right (a and b are both 0, and a and b are both 1) are the those where a+b is even. The cases that get it wrong (a=0 and b=1 or vice-versa) are those where a+b is odd. And we know how to find out if a+b is odd or even. We do it with a controlled-NOT.
That's what the second part of the circuit does. There's a controlled not with the top qubit as control and the bottom as target, which results in the bottom one being 0 if a+b is even, and 1 if it is odd. This gate doesn't involve the middle qubit at all (even though it seems to cross it in our picture).
Now the bottom qubit knows whether the unwanted halfNOT happened. We don't ask it to tell us, because our brains have trouble unknowing things once they know them. We just use it to undo the unwanted halfNOT. This is done with three controlled-halfNOTs with the bottom qubit as control and the middle as target. This adds three more halfNOTS to the middle qubit only when that troublesome one is there already. That gives four halfNOTs in total, which is the same as two NOTs, which is the same as nothing. The unwanted halfNOT is gone!
Now the middle qubit is doing exactly what we need. But the bottom qubit isn't. It should come out as b, rather than tell us about whether a+b is odd. To make it unknow this information, we just do the controlled-NOT again. The second NOT undoes the first and returns the bottom qubit to b. Our reversible-(N)AND is now complete!
Here we have taken three qubits, that were definitely in the states 0 or 1. So they were pretty much just bits. At the end we also have three qubits that are definitely 0 or 1, and so are also basically just bits. But inbetween, their quantumness came in to play. Superpositions happened and got shunted around to do the maths we wanted to do. And that, is quantum computation.
Of course, normal computers can do reversible-(N)ANDs just fine. What we really need quantum computers for are problems that normal computers are rubbish at. The approach is the same. We start with our qubits just being bits, and we end with qubits being bits. But in between we do quantum stuff.
To get the full advantage of quantum computation, we'll need to use more than just a simple controlled-halfNOT. This is defintely part of the Lego Technic set of quantum gates, but it's one of the big and bulky ones. We need some of the more intricate gates to make really fancy computations, such all the possible rotations of a qubit. Add those in, and we can factor huge numbers while you make a cup of tea as well.
To find out more about that, a bit more maths is needed. Complex exponentials are pretty essential, but they aren't to everyone's taste. If you think you can handle it, check out my lecture notes here. You can also find someone else's explanation of things like this in a video here.
Thursday, 7 July 2016
14 - Qudit Codes
Normal computers are based on bits: things that can be either 0 or 1. But why stop at 1? Why not 4? or 17? Why isn't 42 the answer?
Well, a computer needs to do a lot of basic little pieces of maths with the bits. Since each bit can only be two things, those pieces of maths can never be too hard. We found some weird rocks1 that can do it for us, and computers are basically just a big pile of them.
If we used fancier bits that go beyond 1, let's call them dits, then they would do fancier basic bits of maths. That might be nice for designing nice and efficient programmes, but it might also be too complicated to actually build. We would need even fancier rocks. So we settled for bits, in the end.
With quantum computers, we don't yet know whether it would be best to use qubits, or some sort of fancier qudits. For the rest of this post, let's think specifically about qudits that can be one of 10 possible things. So instead of just 0 and 1, as we'd have for qubits, these qudits can be 0, 1, 2, 3, 4, 5, 6, 7, 8 or 9. There's nothing special about 10, except that it's a nice number. Everyone loves 10.
Whether you use qubits or qudits, you need to do quantum error correction. For qubits, we have thought of errors in terms of bit flips and unwanted measurements. Qudits also suffer from the latter, but what is the qudit version of a bit flip? It will just be something that swaps the numbers around. You could have something cylic, like turning 0 to 1, 1 to 2, and so on until 9 turns back to 0. You could also have something pretty random, like turning 0 to 5, 1 to 7, and so on. What happens exactly will depend on how you actually build the thing. But we won't need to worry about that.
We can build a code for qudits in exactly the same way as before. We just replace all the qubits with qudits. We also have to change the rules for the squares a bit. Before, when we added up all the numbers around a square, we wanted it to be an even number: a multiple of 2. But now we are moving beyond bits and their slavish devotion to the number 2. Instead we have qudits that are obsessed with 10. So the new rule is that the numbers around each square should add up to a multiple of 10.
One example of how these rules can all be happy is for all qudits to be 0. But, just like for the qubits, we can also have loops of things that aren't 0. Here's an example on the toric code.
Here the numbers in the loop have to switch between 8 and 2 to make sure that each square has a multiple of 10. It could also be done with 9 and 1, or 7 and 3, or some other things. You know how adding works
Qudits also let us do weird things that aren't quite as simple as loops. For example.
We could think of this as a little loop of 9s and 1s and a big loop of 8s and 2s that got stuck together. Or we could think of it differently. But let's think about different things for a bit.
Rules for the blue squares
There are also rules on the blue squares, but we won't think about them too much. As for the qubit codes, the rules on the blue squares are exactly the same as those on the white ones, except for a few differences. The differences are that a bunch of superposition stuff is involved, and they detect unwanted measurements rather than bit flip type stuff.
The anyons that emerge on the blue squares act in exactly the same way as those on the white ones. But when the once on blue squares dance with ones on white squares, anyonic magic happens.
Perhaps we'll look into the maths of qudits one day, and do the blue squares in more detail. But until then, let's just stick to the white ones.
Anyons
It's actually better to split the big white squares into two families. We'll colour one of them grey. The grey squares are chosen such that every grey square only shares qudits with white squares, and every white square only shares qudits with grey ones.
Anyons live on the white and grey squares when the rules are broken. But there's more than just one way to break the rules now. The way we label the rule breakers is going to be different for the white and grey squares. Let's start with the white. For these we will look at the sum of numbers around a square, and then see how much higher it is than a multiple of 10. So if we get 1, 11, 21 or 31, that is 1 higher than a multiple of 10. This gives an anyon of type 1. For 2, 12, 22 or 32 we'd have an anyon of type 2. We also have anyons of types from 3 to 9. But there's no anyon of type 10, because 10 higher than a multiple of 10 is a multiple of 10 itself.
For grey squares, we look at how much lower the sum is than a multiple of 10. So a sum of 9, 19 or 29 would give us an anyon of type 1 here, and so on.
Though this might seem an odd way to do things, it makes the anyons behave nicer. Whenever an error pops up and creates a pair of anyons, they will always add up to a multiple of 10. The maths behind this is just adding and stuff, so I'll leave it as an exercise to the reader.
In the example above, it's fairly obvious that the 6 and 4 anyons are each others antiparticles. The same is true for any pair that adds up to 10. So only type 5 anyons are their own antiparticle in this particular anyonic universe.
The anyons in this qudit code can also do decay process: one anyon can break into two or more. For example, let's another error nearby.
Here the 4 decays into a couple of 2s. It could also have decayed into a 3 and a 1 with a different error. Or even into an 8 and a 6. As long as the end result adds up to the original 4, ignoring any multiples of 10, then it is possible.
When trying to correct errors, we use the fact that errors create little clumps of anyons that add up to a multiple of 10. That's the whole point of this project, which let's you get involved in helping us correct the errors by playing a game. To learn more, check out this post.
This series on the science behind the game is now over. But don't worry. As players contribute to science through the game, there will be plenty more to fill this blog with.
Footnotes
1. By which I mean transistors, Which are a bit more complicated than just wierd rocks.
2. An electronic computer was once built using the three posssibilities +1, 0 and -1, rather than just 0 and 1. It didn't make it very far, but it did have some nice properties. See here.
Well, a computer needs to do a lot of basic little pieces of maths with the bits. Since each bit can only be two things, those pieces of maths can never be too hard. We found some weird rocks1 that can do it for us, and computers are basically just a big pile of them.
If we used fancier bits that go beyond 1, let's call them dits, then they would do fancier basic bits of maths. That might be nice for designing nice and efficient programmes, but it might also be too complicated to actually build. We would need even fancier rocks. So we settled for bits, in the end.
With quantum computers, we don't yet know whether it would be best to use qubits, or some sort of fancier qudits. For the rest of this post, let's think specifically about qudits that can be one of 10 possible things. So instead of just 0 and 1, as we'd have for qubits, these qudits can be 0, 1, 2, 3, 4, 5, 6, 7, 8 or 9. There's nothing special about 10, except that it's a nice number. Everyone loves 10.
Whether you use qubits or qudits, you need to do quantum error correction. For qubits, we have thought of errors in terms of bit flips and unwanted measurements. Qudits also suffer from the latter, but what is the qudit version of a bit flip? It will just be something that swaps the numbers around. You could have something cylic, like turning 0 to 1, 1 to 2, and so on until 9 turns back to 0. You could also have something pretty random, like turning 0 to 5, 1 to 7, and so on. What happens exactly will depend on how you actually build the thing. But we won't need to worry about that.
We can build a code for qudits in exactly the same way as before. We just replace all the qubits with qudits. We also have to change the rules for the squares a bit. Before, when we added up all the numbers around a square, we wanted it to be an even number: a multiple of 2. But now we are moving beyond bits and their slavish devotion to the number 2. Instead we have qudits that are obsessed with 10. So the new rule is that the numbers around each square should add up to a multiple of 10.
One example of how these rules can all be happy is for all qudits to be 0. But, just like for the qubits, we can also have loops of things that aren't 0. Here's an example on the toric code.
Here the numbers in the loop have to switch between 8 and 2 to make sure that each square has a multiple of 10. It could also be done with 9 and 1, or 7 and 3, or some other things. You know how adding works
Qudits also let us do weird things that aren't quite as simple as loops. For example.
We could think of this as a little loop of 9s and 1s and a big loop of 8s and 2s that got stuck together. Or we could think of it differently. But let's think about different things for a bit.
Rules for the blue squares
There are also rules on the blue squares, but we won't think about them too much. As for the qubit codes, the rules on the blue squares are exactly the same as those on the white ones, except for a few differences. The differences are that a bunch of superposition stuff is involved, and they detect unwanted measurements rather than bit flip type stuff.
The anyons that emerge on the blue squares act in exactly the same way as those on the white ones. But when the once on blue squares dance with ones on white squares, anyonic magic happens.
Perhaps we'll look into the maths of qudits one day, and do the blue squares in more detail. But until then, let's just stick to the white ones.
Anyons
It's actually better to split the big white squares into two families. We'll colour one of them grey. The grey squares are chosen such that every grey square only shares qudits with white squares, and every white square only shares qudits with grey ones.
Anyons live on the white and grey squares when the rules are broken. But there's more than just one way to break the rules now. The way we label the rule breakers is going to be different for the white and grey squares. Let's start with the white. For these we will look at the sum of numbers around a square, and then see how much higher it is than a multiple of 10. So if we get 1, 11, 21 or 31, that is 1 higher than a multiple of 10. This gives an anyon of type 1. For 2, 12, 22 or 32 we'd have an anyon of type 2. We also have anyons of types from 3 to 9. But there's no anyon of type 10, because 10 higher than a multiple of 10 is a multiple of 10 itself.
For grey squares, we look at how much lower the sum is than a multiple of 10. So a sum of 9, 19 or 29 would give us an anyon of type 1 here, and so on.
Though this might seem an odd way to do things, it makes the anyons behave nicer. Whenever an error pops up and creates a pair of anyons, they will always add up to a multiple of 10. The maths behind this is just adding and stuff, so I'll leave it as an exercise to the reader.
In the example above, it's fairly obvious that the 6 and 4 anyons are each others antiparticles. The same is true for any pair that adds up to 10. So only type 5 anyons are their own antiparticle in this particular anyonic universe.
The anyons in this qudit code can also do decay process: one anyon can break into two or more. For example, let's another error nearby.
Here the 4 decays into a couple of 2s. It could also have decayed into a 3 and a 1 with a different error. Or even into an 8 and a 6. As long as the end result adds up to the original 4, ignoring any multiples of 10, then it is possible.
When trying to correct errors, we use the fact that errors create little clumps of anyons that add up to a multiple of 10. That's the whole point of this project, which let's you get involved in helping us correct the errors by playing a game. To learn more, check out this post.
This series on the science behind the game is now over. But don't worry. As players contribute to science through the game, there will be plenty more to fill this blog with.
Footnotes
1. By which I mean transistors, Which are a bit more complicated than just wierd rocks.
2. An electronic computer was once built using the three posssibilities +1, 0 and -1, rather than just 0 and 1. It didn't make it very far, but it did have some nice properties. See here.
Thursday, 30 June 2016
13 - The Planar Code
So far we've been looking at the toric code which, as the name suggests, needs to be wrapped around in a doughnut shape. This isn't really the most practical thing in the world. So how about something that can be done on an ordinary flat surface. Something like the following, perhaps?
As before, the little white squares are qubits. For each big white square there is a rule that all the qubits must obey. Usually they have four qubits around them, but the ones on the edges only have three and the ones at the corners have just two. The blue squares also have a rule that their qubits must follow. All of those have four qubits around them. When the rules are broken on any square, we can think of it as a particle: an anyon.
The whole point of a quantum code is to store a qubit, and to protect it from bit flips and unwanted measurements. For the toric code, this was done with big loops around the doughnut. But there are no loops like that any more. We'll have to work out a different way.
One thing we can do is to take the big white square at the top left, and stop enforcing its rule. We'll also do the same for the big white square at the bottom right. Now these squares are allowed to both have an anyon in, or both not (because these anyons always come in pairs). They could also have some superposition of the two.
These squares can now be used to store our qubit. We can have them both empty for a qubit that is 0, and both with anyons for a qubit 1. This is then nicely protected against logical bit flips, as a line of bit flips would have to stretch from top left to bottom right to do any harm.
Unfortunately, the qubit won't be protected from unwanted measurements. To see if there is an anyone on the top left square, you only need to look at two qubits. The same is true for the bottom right. So it's quite easy to measure our logical qubit.
To make it harder, let's knock down the wall between the top left square and its neighbour. We'll also do the same at the borrom left. Specifically, let's look at the code below.
This has a 'double square' at the top left, which is just two of the old squares stuck together. Otherwise it is exactly like a normal square. A rule can be set for the three qubits around it, and an anyon can live there. The same is true for the bottom left. Now the Gremlins need to measure three qubits to destroy our superpositions. So it's a bit harder than before.
To protect the qubit from unwanted measurements even more, we can just carry on knocking walls down. Now we have a big multisquare at the top and bottom. Both can hold an anyon, but they will be smeared across the whole edge, and so need lots of measurements to work out which you have. Now we have a good way of storing a logical qubit, this finally deserves the 'code' part of the name 'planar code'.
Now that's basically it. You could check out what is happening from the perspective of the other kind of anyons, the ones living on the blue squares, but I'll leave that as an exercise to the reader.
The whole point of a quantum code is to store a qubit, and to protect it from bit flips and unwanted measurements. For the toric code, this was done with big loops around the doughnut. But there are no loops like that any more. We'll have to work out a different way.
One thing we can do is to take the big white square at the top left, and stop enforcing its rule. We'll also do the same for the big white square at the bottom right. Now these squares are allowed to both have an anyon in, or both not (because these anyons always come in pairs). They could also have some superposition of the two.
These squares can now be used to store our qubit. We can have them both empty for a qubit that is 0, and both with anyons for a qubit 1. This is then nicely protected against logical bit flips, as a line of bit flips would have to stretch from top left to bottom right to do any harm.
Unfortunately, the qubit won't be protected from unwanted measurements. To see if there is an anyone on the top left square, you only need to look at two qubits. The same is true for the bottom right. So it's quite easy to measure our logical qubit.
To make it harder, let's knock down the wall between the top left square and its neighbour. We'll also do the same at the borrom left. Specifically, let's look at the code below.
To protect the qubit from unwanted measurements even more, we can just carry on knocking walls down. Now we have a big multisquare at the top and bottom. Both can hold an anyon, but they will be smeared across the whole edge, and so need lots of measurements to work out which you have. Now we have a good way of storing a logical qubit, this finally deserves the 'code' part of the name 'planar code'.
Thursday, 23 June 2016
12 - Swapping Toric Code Anyons
This is part of a project to get people involved with quantum error correction. See here for more info.
Last time we showed that broken rules in the toric code behave like particles. The white squares have one type of particle, that are created, moved around and annihilated using bit flips. The blue squares have a different type of particle, which are manipulated by phase flips instead.
Since then, we also published an article about anyons. These are strange particles that do strange things when they dance around each. Anyons are impossible in our 3D universe. But the surface code is a 2D universe of particles. Could they behave as anyons? It turns out that they do!
In the following picture, some of the qubits are given different colours. One is half blue. Doing a bit flip here creates a couple of particles on the white squares either side. These are shown in orange, so I'll call them orange particles.
Another qubit is light green. Doing a phase flip there creates the other kind of particle on the blue squares either side. These are shown in red, so I'll call them red particles.
What about the dark green qubits? Doing phase flips on these, one after the other, would move the top red particle in a loop around the rightmost orange particle.
For example, if we first do a couple of them, we move the red particle two steps to the left.
The next one, which is on the same qubit as we did a bit flip earlier, moves it up past the orange particle.
The rest then take it back to where it started.
In 3D universes, as we learned here, having a particle loop around another does absolutely nothing. But with particles living in 2D, interesting things can happen. Let's see what happens here.
Firstly, let's see what we mean by a loop that does nothing. Say you never did the bit flip, and never had any orange particles. Then all we'd have is a loop around nothing.
This is what boring looks like.
So let's compare the following two situations.
If these two orders of doing things end up the same, we know that moving one of these particles around the other does nothing. If they are different, it does something. But which is it?
Most qubits have just one thing happen to them, and don't talk to any other qubits. So they don't really even know if their phase flip is happening before or after other stuff. They won't give us much insight.
The important qubit is the one where both a bit and phase flip happen. In the first case, the bit flip happens first. In the second, it happens after the phase flip.
To see if this makes a difference, we have to remember what bit and phase flips do.
What the flipping heck is -1? It's basically 1, but with a -. If you asked the qubit whether it was 0 or 1, it would still tell you that it's 1. But if you had superpositions, the - might do some stuff with the maths. Like turning a + to a -, for example.
Now, let's suppose that this qubit was initially 0 and do the flips according to order number 1. When we first do the bit flip, we get a 1. When we then do the phase flip, we get -1. But if did order number 2, doing the phase flip first, it would do nothing. Then when we did the bit flip we'd get a 1.
So when we do bit and phase flips to the same qubit, it does matter which order we do them in! The results differ by some weird mathsy -1! The same would happen whether the qubit started as a 1, or a +, or a -, or anything.
So there is a difference between an empty loop of a red particle, and one that goes round an orange one. Their dancing does things that are impossible for particles in our universe. They are anyons!
Last time we showed that broken rules in the toric code behave like particles. The white squares have one type of particle, that are created, moved around and annihilated using bit flips. The blue squares have a different type of particle, which are manipulated by phase flips instead.
Since then, we also published an article about anyons. These are strange particles that do strange things when they dance around each. Anyons are impossible in our 3D universe. But the surface code is a 2D universe of particles. Could they behave as anyons? It turns out that they do!
In the following picture, some of the qubits are given different colours. One is half blue. Doing a bit flip here creates a couple of particles on the white squares either side. These are shown in orange, so I'll call them orange particles.
Another qubit is light green. Doing a phase flip there creates the other kind of particle on the blue squares either side. These are shown in red, so I'll call them red particles.
What about the dark green qubits? Doing phase flips on these, one after the other, would move the top red particle in a loop around the rightmost orange particle.
For example, if we first do a couple of them, we move the red particle two steps to the left.
The next one, which is on the same qubit as we did a bit flip earlier, moves it up past the orange particle.
In 3D universes, as we learned here, having a particle loop around another does absolutely nothing. But with particles living in 2D, interesting things can happen. Let's see what happens here.
Firstly, let's see what we mean by a loop that does nothing. Say you never did the bit flip, and never had any orange particles. Then all we'd have is a loop around nothing.
So let's compare the following two situations.
- First we do the blue bit flip, then the light green phase flip, then the dark green phase flips.
- First we do the light green phase flip, then the dark green phase flips, then the blue bit flip.
If these two orders of doing things end up the same, we know that moving one of these particles around the other does nothing. If they are different, it does something. But which is it?
Most qubits have just one thing happen to them, and don't talk to any other qubits. So they don't really even know if their phase flip is happening before or after other stuff. They won't give us much insight.
The important qubit is the one where both a bit and phase flip happen. In the first case, the bit flip happens first. In the second, it happens after the phase flip.
To see if this makes a difference, we have to remember what bit and phase flips do.
- Bit flips flip a 0 to a 1, and an 1 to a 0.
- Phase flips flip a + to a -, and a - to a +
What the flipping heck is -1? It's basically 1, but with a -. If you asked the qubit whether it was 0 or 1, it would still tell you that it's 1. But if you had superpositions, the - might do some stuff with the maths. Like turning a + to a -, for example.
Now, let's suppose that this qubit was initially 0 and do the flips according to order number 1. When we first do the bit flip, we get a 1. When we then do the phase flip, we get -1. But if did order number 2, doing the phase flip first, it would do nothing. Then when we did the bit flip we'd get a 1.
So when we do bit and phase flips to the same qubit, it does matter which order we do them in! The results differ by some weird mathsy -1! The same would happen whether the qubit started as a 1, or a +, or a -, or anything.
So there is a difference between an empty loop of a red particle, and one that goes round an orange one. Their dancing does things that are impossible for particles in our universe. They are anyons!