The Science Behind the Games

Quantum computers suffer from errors, as do we all. But for quantum computers we have quantum error correction to help fix them. As complicated as this sounds, it's just about solving puzzles. We get clues about the errors, and have to figure out how to get rid of them.

To find the best methods, we need you! We are packaging the puzzles up in two puzzle games: Decodoku and Decodoku:Puzzles. Now you can have a go, and help build a quantum computer just by getting a high score.

This article is an extended version of the tutorial here. If you just want to know how to play, that would be the place to go. But here we will take an approach that is closer to the science.

You can do science!

Our games aren't just an attempt to teach you about the science and maths behind quantum stuff (that's what this blog is for). You are not just generating data to help someone else do their research. Instead it lets you do the research yourself. It doesn't matter who you are or what qualifications you have. You can make discoveries in the field of quantum error correction.

The science in the game is not only being researched in universities, but companies like Microsoft, IBM and Google are throwing money at it too. If you want to keep your results secret and try to sell them to those guys, that's fine by us. It's your research, after all. But we'd rather you tell us about them using our survey, or by email at decodoku@gmail.com, @decodoku on Twitter or the /r/decodoku subreddit, and we can pass it on to your fellow player/researchers. For science!

This blog and the app were developed by me, Dr James Wootton. I'm a scientist at the University of Basel, where I do research on quantum error correction. The project is supported by the NCCR QSIT, which supports research on quantum technologies in Switzerland.

We give you everything you need to tackle a problem from quantum error correction by just playing the game. If you find a way to get great scores almost all the time, then you'll know more about how to do this kind of quantum error correction than we do.

Maybe you won't be able to explain exactly what your method is. Maybe you'll just have a few tips and tricks you've found do some good. That's great! Even the smallest thing could help us, or your fellow players/researchers.  

You don't need to write a big complicated research paper with graphs and figures to help us out. Tradition dictates that us normal scientists and mathematicians need to write papers and send them to journals, but that's not what science and maths are all about. It's about discovering things, solving problems and then telling people what you've done. You are free from the bounds of tradition, and can use whatever means you want to tell people about your results, from a long technical PDF to a Let's Play or gif. Just remember to stay safe on the internet.

One scientific tradition that you should uphold is to cite your sources: If you've been inspired by someone else's work, give them a bit of credit for it. If us normal scientists use your results in our work, we'll make sure to acknowledge it too.

Both Decodoku and Decodoku:Puzzles have two versions called ℤ10 and Φ-Λ. They are two different ways of doing error correction that we need your help for. You don't need to read this blog to do the science. There are much smpler tutorials in the links above. But if you want to know more about the games and the science behind them, read on.

The following is all based around Decodoku, though Decodoku:Puzzles is based on the same science.

The Game ℤ10

The game is based on the grid shown below.

The little white squares here represent qudits. These are the basic building blocks of quantum computers. They are like the bits that we use in normal computers, but we can do cool quantum things with them. The simplest kind of qudit is called a qubit. We are already pretty good at solving the puzzles required for qubit error correction. But error correction for other qudits is a lot harder, and that's why why need your help.

No qudit is ever perfect. They are always noisy, and so errors will happen. We need a way to find these errors and remove them so that our quantum computation doesn't get messed up. That is what quantum error correction is all about.

There's a whole bunch of ways that we can do this. They are called codes. Our games use particular kinds of codes called surface codes. This is where the grid comes in.

The grid is made up of big white squares with qudits in the corners. Each qudit is shared between a couple of neighbouring squares.

For each big white square we set a rule that the qudits must follow. These rules don't tell each individual qudit what to do. Instead they tell the qudits around each square how they should play together. We can then set the grid up so that all the rules are being obeyed.

Then, like some sort of quantum police, we go around the grid checking up on all the squares. We look at whether or not the rules on each square are being obeyed. If we find some that aren't, we know that something has gone wrong. We know that at least one of the qudits has made an error.

There's more than one way that the rules can be broken. In fact, there are nine. We label these with the numbers from 1 to 9. When we find a square that's not doing what it should, we can then look at which of these nine types of crime has been committed.

Here's a couple of examples of qudits that have gone bad. One is blue and the other is dark red. All squares that now violate the rules have a red border.

The blue qudit leads to broken rules for the two squares that it is a part of. When we look at the numbers, we find that error made by the qudit is one that causes a type 6 violation on one square and type 4 on the other. We would have found different numbers if the qudit had made a different type of error.

The dark red qudit also messes up its two neighbouring squares. Here one has a 9 and the other has a 1.

In both of these examples, the numbers add up to 10. This is not a coincidence. Whenever a qudit goes bad it will break the rules on its two neighbouring squares, and the numbers for these broken rules will add up to 10.

What happens when more qudits go wrong? In the example below there is a new bad qudit, also shown in dark red. Here we've only put the red border around squares whose numbers have changed because of the new one.

This new error happens near one of the old ones. So near, in fact, that one poor square is now affected by crimes of both. We can no longer see the individual effects of each error, and so have to think of them as working together in a gang.

The dark red gang has caused three squares to break the rules, with numbers 9, 5 and 6. These numbers add up to 20, which is a multiple of 10. Again this is not a coincidence. Any team of errors, no matter how big or weird looking, will always lead to numbers that add up to a multiple of 10.

Now here's some more broken qudits. This time in green.

Again these share a square, and so form a gang. The numbers they generate are 8 and 2, which again is a multiple of 10 (10 itself, in fact). Interestingly, the square in the middle doesn't break the rules. This is a clever gang that has managed to cover its tracks a little.

If we don't do anything, this is going to continue. More qudits will turn to a life of crime and the gangs will get bigger.

What can we do? It's possible for us to make the squares follow the rules again, but this comes at a price. One of the neighbouring squares will have to break the rules instead. This means that we are basically moving the numbers around, like the green 2 below.

The other numbers being moved here end up bashing into something else. When two numbers meet, they add up. What happens if they add up to 10? There is no such thing as a type 10 violation of the rules. Only 1 to 9. It turns out that a 10 actually means that the rules are being followed. So adding numbers up to a multiple of 10 makes them disappear.

What about if they add up to more than 10? Since 10 basically acts as if it were nothing, 11 acts as if it were 1. 14 acts as if it where 4. 26, which has two lots of nothing, acts as 6. So when the numbers add up, we can ignore any multiples of 10.

As we saw earlier, all the numbers made by any particular gang of errors will add up to a multiple of 10. So pushing all these numbers together and adding them up will make them all disappear. The errors will then have been corrected, and the bad qudits will be back to being productive members of society.¹ This is the aim of the game.

There are two things that will make it difficult for us to do this. Firstly, we don't know which qudits have messed up. We don't know which ones are working together in gangs. We only know which squares suffer from their crimes and what all the numbers are. The colours in the pictures above were just to make things clear for you. You won't be able to rely on their help in the game. You'll just see something like this.

This then gives you the puzzle you need to solve. Given this set of numbers, which groups of numbers were caused by the same gangs of errors? Once you've found these groups, you move them together so they add up to 10 and disappear. The damage done by the errors will have been removed.

The second thing making your life difficult is that more errors will come over time. New errors come after every five moves you make. This means that more rules will get broken, gangs will grow and change, and everything will become more complicated. You have as much time as you want to think about each move, though.

These troubles might lead to the most feared part of all games: Game Over! When does this happen, and how can you tell whether you are doing a good job?

Most importantly, we don't want the gangs to get too big. We want to keep them small, or get rid of them all together. This means that we need to stop the numbers they create from spreading too far. You do this by moving them together, adding them up and getting rid of them. The game ends once a gang has gotten its numbers to go all the way across the grid (top to bottom or left to right). That could mean something like the red team has done in this example that follows on from the examples earlier.

Or it could be something simpler, like this.

This was a pretty clever gang of errors. They somehow managed to get all the way across without leaving any mess in the middle. How did they manage such a feat? Sometimes it wasn't their cleverness that did it, it was your mistakes! For example, look at what the red and blue gang have done here.

If you look hard enough, you'll probably work out what you should do (even without the helpful colours). But if you are lazy and just look at the numbers in the middle, you might think “Hey, an 8 and a 2. Let's make a 10 out of those!” By doing this you close the gap between the gangs. They join forces to become the purple gang, which stretches from top to bottom. And then you lose.

The aim of the game is to go as long as possible before one of these big teams of errors comes and stretches across the grid. Your score is the number of moves you managed to make before everything messed up. This is basically the time that your quantum computer survives before the errors overwhelm it. 

To be useful for quantum computation, we'll need a method that gets scores that are as high as possible, and get them as reliably as possible. It's your job to find this! Your method should get a great high score, but also have a good average score too. You can find all your statistics on the 'Results' screen in the game.

A method for doing this job is called a decoding algorithm: it takes the information about what rules have been broken and it deciphers what must be done to get rid of the errors. So if sometime tells you to stop playing games, you can tell them that you are actually developing decoding algorithms for quantum error correction

Anyons

Before I move onto the other game, I will let you in on a little insider information about what is going on here. The numbers that we get when a rule is broken can be thought of as particles. They aren't really real particles, like apples or balls. But we can still move them around as if they were real things, as we have seen. So we can pretend that they are particles. To make it more sciency, we refer to pretend particles like these as quasiparticles.

They aren't just any quasiparticles. They are an exotic kind of particle that could not exist in our universe. No matter how hard they smash things together at CERN, these particles are never going to pop out. They are called Abelian anyons. Our error correcting code is like a new little universe we've made that lets us play with impossible particles.

The Game Φ-Λ

The other game is called Φ-Λ. Φ is the Greek letter Phi, and Λ is the Greek letter Lambda. We scientists and mathematicians like to use Greek letters because they make us look clever.

In ℤ10 we did error correction with some pretend particles called Abelian anyons. These are pretty fun, but not as fun as their even more exotic cousins: non-Abelian anyons. Using these we might be able to build a quantum computer that is completely different from the boring normal computer that you are using to read this blog. We would do computations by making the anyons dance around each other. This would be called a topological quantum computer.

We would still need to do error correction. Noise will create a bunch of anyons that shouldn't be there, and we need to get rid of them. But error correction for non-Abelian anyons is quite different to that for the Abelian ones in ℤ10. We can get a taste of this using a rather simple bunch of non-Abelian anyons, that are related to the Abelian ones in ℤ10.²

All we need to do is take the same grid as in ℤ10, use the same qudits and the same rules. The only difference is that we are not allowed to know as much about how the rules were broken. Before we would look exactly which of the 9 possible violations of each rule happened. Now we are only allowed to know whether it was type 5 (which we call Λ), or something else (which we call Φ).

This means that something like this from ℤ10.

Will look like this in Φ-Λ.

This is going to make our life harder. In ℤ10, when we think a bunch of numbers come from the same gang of errors, we can see whether they all add up to a multiple of 10. If they don't, we know that we were wrong and so we think again.

In Φ-Λ, if we think that a bunch of Φ's and Λ's came from the same gang of errors, it's not so easy to disprove our theory. We have to try moving them all together and see what happens. If they all disappear, maybe we were right. If not then we were wrong. In that case, we have to hope that we didn't mess everything up too much!

We are not completely helpless. We know that moving two Λ's together means moving to 5's together, and so these will always add up to 10 and disappear. Moving a Λ and a Φ together means adding a 5 to a 1, 2, 3, 4, 6, 7, 8 or 9. This will give 6, 7, 8, 9, 11, 12, 13 or 14. None of these are 10 or 5, so they won't disappear or become a Λ. It will always end up just being a Φ. Moving two Φ's together could make them disappear (if they were 2 and 8, for example). It could also make them become a 5 (if they were 1 and 4, for example). It could even make them become a single Φ (if they were 1 and 3, for example).³

For some concrete examples, take a look at the picture below that we saw before in ℤ10. If this same thing were to happen in Φ-Λ, we'd have to replace the numbers with Φ's and
Φ-Λ. Moving the blue Φ's together annihlates them: they both disappear. Moving the red
Φ into red Λ results in them combining to become a Φ. Only when we move that into the remaining red Φ will we get annihilation.

Combining non-Abelian anyons is an uncertain business: we don't always know what is going to happen. This uncertainty is one of the things that would make them so useful for quantum computation. Unfortunately, it also makes it pretty hard to do error correction for them. In fact, no-one has proven that error correction for these non-Abelian anyons can be done well enough to use them for quantum computation. You can help me prove this. Playing Φ-Λ and finding out how to consistently get high scores is just the beginning.

Go forth and science!

This is all you need to know to get on and do some science. In fact, it's more than you need to know. So check out either Decodoku or Decodoku:Puzzles to get going.

If you want to know even more, check out the rest of this blog. Here is a good place to start (everything before that post is a prequel).

Attack of the Clones

When a mobile app gets successful, it often gets cloned. That would not be a problem for us. Why aren't in it for the money. There's no charge or ads for anything we do. We are doing it for science! If someone takes something that a scientist or mathematician has produced and does something new with it, it's never anything but awesome.

Soon we will release the source code to the game. With that, you'll be able to see how I hacked it together. If you'd like to see a few new features, you can of course let us know. But you can also try to implement them yourself, and have your own personal version of the app. If you think that others would enjoy them, you could also release it to the public. It's all for the good of science, so it can only be a good thing. Just make sure to follow the normal scientific conduct by acknowledging for giving you the idea.

Footnotes

¹  This is not entirely true. If you let the gang get too big before correcting it, the effects of their crimes may remain. Check out the rest of this blog if you want to know all the details. Here is a good place to start.

² Non-Abelian anyons aren't usually so closely related to Abelian ones like this, especially the ones that can do quantum computation. But the Φ-Λ type of non-Abelian anyons are, so they let us try out doing error correction for non-Abelian anyons without straying too far from the ℤ10 problem.

³ This was the most horrible and technical paragraph in the post. Well done for not skipping it!