Using a simple puzzle game to benchmark quantum computers
Since last year, we’ve seen a lot of big announcements about prototype quantum computers. From big companies like IBM, Google and Intel, to smaller startups like Rigetti and IonQ,. It seems that quantum computing is really starting to become a reality.
But how do we go about comparing these devices? How important is the number of quantum bits (known as qubits)? How does the connectivity of the qubits effect the programs we can run. What about noise and imperfections?
I wanted to make something that would allow the interested layman to answer these questions for themselves. No need to rely on press releases or hype. Instead, a bit of hands-on experience could be used to compare prototype quantum computers.
So I made a game. It’s called Quantum Awesomeness.
What are the rules of the game?
Quantum Awesomeness is a game of simple puzzles. Each puzzle is made up of a grid of coloured dots with numbers in. Each dot should have a similar colour and number as one of their neighbours. The player’s job is to look for these similarities, and use them to pair up all the dots.
For example, look at the puzzle below.
These split into pretty clear pairs. For example, the two dots to the far left are the same reddish colour, and both have the number 70. So it is clear that pair H is part of our solution. Then there is pair I that with the two 0s, and so on. Continuing in this way, we find that the pairs labeled H, I, J, K, L, M G, and V are the correct solution to this puzzle.
After a couple of rounds, things get trickier.
The numbers have started to drift away from each other. They are no longer as close in value as they once were. This effect, that we call ‘fuzziness’, leads to an increased difficulty in finding the solution.
Ideally, Quantum Awesomeness should be played directly on a quantum computer. In this case, any mistakes made in finding the pairing of one puzzle will have consequences in all that follow. Specifically, all dots involved in the mistakes will experience a lot more fuzziness in later rounds. So the less mistakes you make, the easier the rest of the game will be.
This is the goal for the player. There will be a Game Over condition when the puzzles become too hard. So the player must try to make it through as many rounds as possible before that happens.
Well, that will be the goal for the player. But for the time being, it is the quantum computers that need to prove themselves. They need to show that they are actually capable of running the game. And of running it well.
Why will we need a quantum computer?
The basic gameplay described above could easily be implemented on a normal computer. Some procedure could easily be devised to cause the fuzziness.
But to live up to the quantum part of the name, we don’t just want any old fuzziness. We want to use the slow and steady built up of multipartite entanglement across a quantum processor. Then, once we are a sufficient number of rounds through a sufficiently large puzzle, our ‘simple’ game becomes something that even a supercomputer couldn’t run within its lifetime.
This is related to the notion of so-called ‘quantum computational supremacy’, the point at which we prove that quantum computers can outperform normal ones (for some tasks, at least). In fact, the game is based on Google’s proposal for how to achieve this milestone, known as random circuit sampling (or RCS).
Put simply, what they want to do is run a fairly long quantum program on a fairly large device. The end result will be a fancy random number generator, where each of the possible outputs have almost the same probability. The almost here is very important, because it is the exact form of the slight differences in probabilities that will be hard to simulate with normal (or even super) computers. So by implementing this random number generator, it can be shown that a quantum processor can do something that non-quantum devices cannot.
In Quantum Awesomeness, the puzzle for each round is created by a small slice of random quantum program. By providing a solution, the player is unknowingly creating another snippet of quantum program. If the player’s solution is correct, this will undo the part that came before. But for each mistake that is made, a piece of the random program will remain. Once there have been enough mistakes, and the game becomes truly unplayable, the underlying quantum program will be just the kind that could use for RCS.
One major difference between the RCS approach and Quantum Awesomeness is the length of the program. Proposals for how to achieve ‘supremacy’ usually want to get it done as quickly and easily as possible. The quantum program at the heart of Quantum Awesomeness, however, is quite different. If the player gives good solutions to each puzzle, the effect is for one part of the program to undo what just came before. This means that it spends most of its runtime just faffing around.
The only way to avoid this is to have a completely incompetent player. Then things don’t get undone. In fact, the player’s solutions will be an extra contribution to building up the random circuit.
So the RCS proposal is equivalent to playing Quantum Awesomeness until Game Over, and then verifying that the Game Over was truly due to the expected quantum effects. But to do so as quickly as possible, the game can be played by only the most incompetent players.
This interpretation of what’s going on in the RCS proposal hopefully helps to provide a bit of perspective. Achieving ‘supremacy’, by this or any other means, is just one step along the long road to fully working quantum computers. It will be an important milestone to pass, but it won’t be the end of the journey. For that, we’ll at least need to let a moderately competent player manage to reach a fully quantum Game Over.
How well to current quantum devices perform?
The need to use the shortest possible quantum program is not due to impatience. It is as a protection against noise: the spurious effects that can contaminate our results. The faster a quantum program can be run, the less noise it will have to deal with.
Noise brings a new source of fuzziness to the numbers in the game. This means another source of difficulty, and one that has no respect for gentle learning curves.
Given the strength of noise we find in current devices, the difficulty level ramps up far more quickly than we’d like. The point of unplayability will come within a few rounds, regardless of whether the player is good or bad.
So in the near term, a player won’t really be playing the game to show off their own skills. Instead, they’ll be using the game to compare different quantum processors, and see which device provides the best gameplay.
Quantum processors as playgrounds
Playing the game can let you experience more than just the noise level. The design of the puzzles depends explicitly on the device used to run them. Each dot represents a qubit. The possible pairings of dots represent the connectivity of the device. So if you are getting sophisticated puzzles, it means that the device allows easy implementation of sophisticated programs. Just by playing the game you can get a sense of how complex it is in comparison to the competition.
For some examples of this, check out the images on this page. There are examples from three different IBM devices, as well as one from Rigetti.
So let’s play!
You don’t need your own quantum computer to try the game. You don’t even need to get yourself access to one. I am getting data on every device I can, which you can use to run games offline. Of course, this means that your mistakes can’t come back to haunt you, as they really should. But it does allow you to see how different devices manage to implement the game. A version you can play in your browser can be found here (note: it may take a few attempts to get it running).
And let’s do science!
This project is also designed so that interested programmers can contribute. For example, you could design better bots that can play the game. Or find improved post-processing of the data to make it more playable. These could then give us insight into exactly what the noise is doing, and help the development of quantum computing. Head on over to the GitHub repo and dive in.
