Making games with quantum computers
Quantum computers are a new technology! Games are great! Let’s put them together! This is what I’ve been looking into for the past few years, and many others have now heard the call and joined the fun.
Nevertheless, you might be wondering why anyone would bother, and how they’d go about doing it. To answer this, I think it’s best to go back to the dawn of all computer games: the 1950s.
The 1950s: What can games do for computers?
Games have been around for as long as humanity. Computers are a more recent phenomenon. It was the 1950s when they really began to coalesce.
The first example was Bertie the Brain, exhibited at a trade show in 1950.
It used vacuum tubes and light bulbs and played Tic-tac-toe. Not because it offered a better play experience than using pen and paper, but because it helped to show off the vacuum tubes. The fact that I’m writing about it now, 70 years later, shows that it certainly had some impact. It showed us the first possible reason for making games with computers: to showcase new technology.
Then there was Nimrod in 1951. Again vacuum tubes and light bulbs, but this time the game was Nim. It was shown at the Festival of Britain with a stated aim, among other things, to
…illustrate the algorithm and programming principles involved.
This gave us a second reason to make games with computers: for education. Programming would have seemed a strange and arcane art in those days. How better to make it relatable than to show it playing a game?
Next was a research project in 1952 at Cambridge University.
The idea was to study human-computer interaction, done using another implementation of Tic-tac-toe (or Noughts and crosses, as it is known in Cambridge). It again used vacuum tubes, but this time had cathode ray displays: the first graphical upgrade of the games industry! Nevertheless, the driving principle was research, giving us another reason to make games with computers.
Another project to note was that done at IBM Research in the 1950s: making an AI to play Checkers and beat a human opponent.
This would be something that IBM would repeat decades later, using Deep Blue to beat Gary Kasparov at chess, and then Watson to beat champions at Jeopardy! DeepMind has also been prominent in this area, using AlphaGo to beat a champion at Go. All of which are more examples of using games to showcase technology.
There were more games in the 1950s, but the ones here show what the decade was all about. Whether it was to showcase the technology, to educate about the technology or to research the technology, games were used to help computers rather than the other way around.
The exception was 1958’s Tennis for Two, a game made for fun and a sign of what was coming.
The 1960s: What can computers do for games?
In 1962, a team at MIT decided to put their new PDP-1 to good use. They embarked on a project that would:
- Test out the new device (and later, new installations);
- Showcase its capabilities;
- Be fun!
They created a game. But it wasn’t just an existing game, with a computer-based implementation tacked on as a gimmick. It was something new: space battles without the need to build your own space ship. It was called Spacewar!
This was the first clear example of computers doing something for games. They were used to make something new, and something fun. Functions made for trigonometric calculations were repurposed to let the player experience flying around a star.
It wasn’t the only game this decade to be set in space. There was also the original Lunar Lander, as well as the unimaginatively named Space Travel. More down to Earth was an economics simulator — The Sumerian Game — which was an early ancestor of games like SimCity.
In each case, the computer was used to do exactly what computers were made for: crunching numbers and performing simulations. But rather than being used for payroll calculations or planning a real trip to the moon, the computers were used to provide unique play experiences.
The 1970s: Commercial Success
Not many people know about Spacewar! or Space Travel. Any familiarity with Lunar Lander is usually due to one of its later incarnations, rather than the 1960s text-based original. This wasn’t due to any secrecy on the part of the developers: they usually freely shared the source code. It was more because few had the room for a room-sized computer, never mind the money.
The 1970s is when it became possible to bring the hardware to the masses. The first arcade game was Computer Space, conceived of as a coin-operated Spacewar!, that ran on hardware dedicated only to the game. The first generation of home consoles soon followed, including the Magnavox Odyssey, Atari Home Pong and more.
With these breakthroughs, computer games became something you could sell to the masses, either in an arcade or at home. The games industry had truly begun. You probably know the rest.
What are computers anyway?
So far, I’ve assumed you know what computers are. Probably a good assumption, since most of us now use them every day. However, we probably don’t spend much time thinking about how they work at the most fundamental level.
For example, what is the simplest thing a computer can be programmed to do? Most might think of something like adding two numbers together. But even that has its complexities: What kind of numbers are they? How are they encoded? What does the addition look like when it actually runs through the microchips?
For the truly simplest elements of computation, we need to think in terms of bits. All information is encoded using bits, and all information is processed using many simple manipulations of bits known as logic gates.
For example, the so-called NAND gate is a simple comparison of two bit values. It outputs 1 if they are both 0, and 0 otherwise. Amazingly, every possible program can be compiled down into many applications of the NAND gate. If you don’t believe me, there is a course that takes you all the way from NANDs to Tetris!
For every problem that computers can solve, the so-called ‘computational complexity’ is a measure of the resources we need to crack it. Essentially, it is like asking how many NAND gates we would need. Some problems take more than others. For example, adding two n-digit numbers has a complexity that rises linearly with n: doubling the length of the numbers doubles the effort. Multiplying numbers (at least in the way taught in primary school) takes quadratic complexity, so doubling the number of digits would quadruple the complexity. There are some problems for which the computational complexity increases much faster this this. For these, we can easily run into seemingly straightforward problems that cannot not be solved within the lifetime of a human, even with a planet sized supercomputer!
Simulating molecules is one such example. Just writing down the quantum states of atoms is something that you need exponentially many bits for. Processing them isn’t any more efficient. Even quite common molecules in our everyday life, such as caffeine, are beyond our ability to fully study with computers.
The difficulty of simulating molecules within a human lifetime is a rather extreme example, but the limitations of computers arise in many other cases too. Whatever you are doing with computers, you will run into issues with computational complexity sonner later.
Game design is field that can be particularly sensitive to computational complexity, since we need to be very careful with how long things take. Even calculating the inverse square root of a number, a relatively easy task, can take too long when we need to do a lot of them. This motivated the use of some almost magical methods in Quake III Arena, to get it done fast enough to render the graphics.
Whether in game design or some other application of computing, software developers have become adept at finding workarounds like this. Sometimes it comes in the form of new hardware, such as graphics cards, dedicated to solving certain types of problems.
This is exactly how we hope to solve the problem of molecular simulation. We want to find a new form of hardware that is perfectly suited to storing and processing information about quantum states. For this, all we need to do is take something that works in a quantum way anyway, and harness it as a computer. These proposed devices started to be seriously studied in the 1980s, and were given the name ‘quantum computers’. It was soon discovered that they are useful for more than just quantum-related work, but could speed up our computations in all sorts of different areas.
Like normal computers, quantum computers are based on the idea of bits that are manipulated by simple logic gates. All quantum programs are just great big piles of these basic operations.
The difference is that the evolution of the states is described by quantum physics. This gives us a few extra kinds of basic operation, with which we can find completely new paths from input to output. The number of quantum logic gates we need to solve certain problems can be dramatically fewer than when using the logic gates of normal computers. Because of this, programs that would take impractically long to run can be made practical.
To run this quantum software, we need quantum hardware. It’s taken a few decades, but we’ve finally gotten to the point of making prototype versions of this hardware. The quantum bits, also known as qubits, can be made using tiny superconducting circuits that have been cooled down to near absolute zero.
Since 2016, these are available on the cloud for anyone to play with at the IBM Quantum Experience. Since 2017, it is been possible to interface with them programmatically using a Python API.
This marked this beginning of a new era. We can start making games with quantum computers!
The 2010s: What can games do for quantum computers?
In 2017 I started making games that use quantum computers. Why? Because I could!
The first one worthy of note — which I have now retconned as the first ever — was a simple version of Battleships.
The display was just ASCII in a terminal. The gameplay was no better than you could do with pen and paper. Rather than being made to be played, it was made to be the basis of a blog post.
The idea was to give an example of quantum programming that wasn’t a complex algorithm, but instead something more tangible. The states of a qubit were used to encode whether a ship had been sunk or not. Quantum gates were used to implement attacks. Without realizing at the time, I had repeated the history of Nimrod. Just as normal programming seemed like an arcane art then, so quantum computing can seem so now, so I made a game to “illustrate the algorithm and programming principles involved.” It was a quantum game made for the purpose of education.
My next major game was Quantum Awesomeness. This was based on the fact that there are many aspects of a quantum processor that determine how useful it is: number of qubits, which pairs of qubits we are allowed to apply a two-qubit gate to, and what imperfections are present. To help people get an idea of how different devices compare, I made a puzzle game.
The game was designed so that the puzzles were based on the specifications of the device used to run it. The more qubits you had, and the more complex the layout of possible two-qubit gates, the better the puzzles would be. The more imperfections there were, the less it would seem to make any sense. So to compare devices and see which was best, one only needed to see which was the most fun. It’s not as informative as looking at benchmarking data, but it is a lot more accessible to the public.
The easiest way to see it in action is to read one of my blog-based play-throughs.
This game was designed so that the player didn’t need to have direct access to the devices. Instead I would use my own access to generate a bunch of puzzles. I also made a some of graphs and wrote a paper. So this was an example of making quantum games for the purpose of research. Again, repeating the history of the 1950s.
The next game to use a real quantum device was made in 2019, by a team at a quantum game jam in Helsinki. It was a card game in which each player has a qubit and each card represents a quantum gate. The quantum computer was used at the very end to judge who played their gates best.
It’s a fun game to play, but it also helps to teach people about quantum gates. Instead getting them to sit through a lecture or read through a textbook, playing the game helps us explain the basics of quantum computing in a more friendly atmosphere. Another quantum game made for education.
The motivation behind these games was exactly the same as in the 1950s: education and research. They also served the other big purpose of 1950s games, to showcase the new technology, since their very existence helped to get the word out in the form of blog posts, tweets and more.
The 2020s: What can quantum computers do for games?
Now it’s time to get serious. What can quantum computers actually do for games?
Like everything, they bring some benefits but also some design constraints. For one thing, the need to cool the hardware to near absolute zero means that you’ll never get one inside your Switch. They’ll live on the cloud, and so probably aren’t something that you wanting to send jobs to every frame. For any game that might use a quantum computer, the vast majority of it will still run on a normal computer. We just need to find a small corner that quantum computers can excel at.
As with any attempt to find applications for quantum computers, we also need to think about the different eras that the technology will go through. Our main aim is a future era, where all imperfections are removed by error correction, where you’ll have more qubits than you’ll ever need, and where you’ll be able to do any two-qubit gates you want. This is the era of fault-tolerant, scalable quantum computing. Don’t expect to see it during the next decade!
What we’ve had since 2016 is what has been called the ‘quantum ready’ era. Prototype devices have been made and put on the cloud for everyone to use. But most can’t do anything that you couldn’t emulate on your phone while reading this article.
Between these two eras is something a bit more mysterious. We’ll have quantum devices that are too complex to simulated, but which do not have the capability to run the standard textbook algorithms developed over the last few decades. This is the so-called ‘NISQ era’. We’ll need some hindsight to determine whether it has already begun, is beginning now, or will begin in a few years. Nevertheless, finding potential applications of quantum computers for this era is currently a big area of research: by universities, large companies and even start-ups.
In my opinion, an ideal type of application to look at is one where experimentation can be started in the quantum ready era, made even more sophisticated in the NISQ era, and then become fully awesome in the fault-tolerant era. I also like to encourage people outside the field to get involved, so something with a gentle learning curve would also be very useful.
I am very much of the opinion that procedural generation is the answer: Starting off simply and branching out in complexity; providing tools for hobbyists to play around with; absorbing any wait time for quantum results in a loading screen; and making nice content to tweet about.
I could go on about this endlessly, but instead I’ll direct you to where I go on about this endlessly.
For current and near-term applications, the most important factor is that we need to be easy on the quantum processors. We can’t get them to do highly abstract things that require huge amounts of gates. The small imperfections in each will just pile up to give us nonsense at the end. Instead, we need to let the quantum computers be their natural quantum selves, and find applications for that.
My first idea was to take one of the most natural processes for quantum systems: making interference patterns. By devising a method for encoding images in quantum states, these interference effects could be used for simple image manipulation.
For example, here’s the process turning a couple of pixels into a chessboard, and finding some interesting patterns along the way.
One possible use of these patterns is to create interesting textures for procedurally generated terrain. So that’s what I did.
Is this a revolution in terrain generation? I don’t think so. Are AAA studios offering me huge wads of cash to put this in their games? Not that I’ve noticed. It is the first step towards figuring out where quantum computers could be useful in games, but there is still a long way to go.
Before taking the next step along this road, there are a few more things we can do with this quantum image encoding. For example, in quantum computers we often use teleportation-like effects. These are not just sci-fi, but something you can do with a simple quantum program. Applying them to an encoded image can give an interesting transition effect.
The method is not limited to images. It can be adapted to encode and perturb many different forms of information. I’ve dabbled with music
and even Mario levels.
This didn’t give the most beautiful symphony, or the best possible Mario level. But they were fun to do!
My current project is something a bit more sophisticated: I’m trying to get a quantum computer to play a Civilization-like game.
The hope is that this might be the Spacewar! of quantum games: The first example of the new technology contributing something truly unique. Though perhaps it is more likely to be the quantum equivalent of the 1950s checkers AI: something done by some guy at IBM to show off. Either way, it’s a step in the right direction: into (or towards) the 1960s.
The quantum tool behind this project will be open-source and freely available for everyone to play with. It could be used as part of procedural generation projects or function as a rudimentary AI. As in the 1960s, the spirit of the next decade should be one of experimentation and collaboration. Near-term quantum computers are for game jams rather than AAA studios.
There will also be papers and graphs. They are seldom sexy, but they keep us rigorous. Here’s a sneak preview.
Quantum games without quantum computers
If the history of computer games began in the 1950s, then the 1940s was its prehistory. One relic of this era was Turochamp, a chess AI developed by Alan Turing and David Champernowne. It had one big problem: it was too complex for the computer hardware of the time. It was run in 1948, but with a human manually simulating the process.
This too has a parallel in recent experiments with quantum games. It is easier to simulate simple quantum programs on a normal computer than to run them on real quantum hardware. This allows us greater flexibility to explore what qubits can do, within the familiar and fun context of hacking together simple games.
Many games have been made in this way. Such as QPong (a quantum version of Pong), Qiskit:Blocks (building quantum programs in a Minecraft-like world), and many more. Most of the procedural generation techniques I talked about before also ran on simulators rather than real devices.
So if you want to have experiment with the brave new world of quantum computing, why not try making a simple game yourself? I introduce some of the tools you might use in the following Twitter thread.
