Introducing: Procedural Generation Using Quantum Computation
This is the transcript of a talk given at the PCG workshop at the FDG 2020 conference. You can find the paper it’s based on here. It’s all about procedural generation, which is basically making content (like terrain, levels, puzzles, etc) for things that need content (like games).
I’m James Wootton from IBM Quantum, where we work on quantum computation. This is a new technology, so you’ve probably not heard it being applied to procedural generation before. I’ve been looking into how it might be done, and that’s what I’m here to tell you about!
First, I’ll need to convey some idea of what quantum computers are and how helpful we can expect them to be. I’ll spare you from all the details about how they work. Suffice it to say that they represent a completely different model of computation than both conventional digital computers and analogue computers. They don’t just speed up normal software through some quantum magic. Instead they require a completely different approach to software, as well as different hardware to run it on.
It turns out that quantum computation could one day perform some tasks far more efficiently than normal computation. This will enable us to solve problems that are currently intractable. After decades of research we now know many examples of quantum algorithms that will provide these “Quantum Advantages’. They relate to a range of possible applications, including some that could be relevant for procedural generation. These include solving optimization problems, constraint satisfiability problems, doing graph-theoretic analysis and more.
The hardware required for quantum computation has also been in development over the last few decades, but building it is a tricky business. Imperfections are inherent, and our favorite methods to work around them require huge overheads in software.
To be specific, one important parameter in describing a quantum device is the number of qubits. These are basically bits, but implemented in a quantum way. To run these flagship algorithms we need many thousands of qubits, which is not something we will have for a good few years.
There are a bunch of other important considerations which mean that we really shouldn’t compare devices with qubit number alone.
But since we won’t be drilling down into those details, let’s just continue to use qubit number as our main metric of comparison.
We don’t currently have many thousands of qubits, or even just one thousand. We don’t even have 100. The largest device that can be used at the moment has 65 qubits. Though not enough to run the flagship quantum algorithms we know and love, they do have the potential to offer results that conventional computers cannot. This is demonstrated by the hardness of emulating these devices, which would require you to book the world’s largest supercomputer for a couple of days to even make an attempt.
So, we live in interesting times! The hardware can offer unique answers, but our decades of research have not prepared us to ask the right questions. A major focus of current research is therefore to try and figure out how to do something useful with these machines as soon as we can.
As well as the biggest and best of current devices, there are also many at the more modest level of around 20 qubits. And there are also a whole bunch with up to 15 qubits that have been made available to the public for free by us at IBM.
Also, we have been building some great emulation software to use to aid in design and testing. Though it is a massive computational task to emulate more than 50 qubits, even your laptop wouldn’t have much trouble doing it for up to around 20 qubits.
This all combines to make ~20 qubits an important landmark. Whether we use real quantum hardware or emulation, it is really easy to run quantum software targeted at this level.
So, what does this all mean for procedural generation? Well, that depends on which of these three eras you are looking at: today, the upcoming era where devices have hundreds of qubits, or the future where devices have over a thousand qubits.
Once we get quantum hardware that can run standard quantum algorithms, we’ll get new tools to use for procedural generation. So, we think that quantum computers of that time will be able to achieve unique things that are useful for this field.
At the other extreme, quantum software targeted at the 20-qubit level cannot do anything unique. The very fact that we can run it on an emulator means that you don’t even need the quantum hardware. But can the quantum software nevertheless do something useful? Can we write a 20-qubit quantum program that will give results that a real-life end user can use in a real-life situation?
If we can achieve usefulness with 20 qubits, then we can aim to keep on expanding that usefulness as we target ever larger quantum hardware. The middle era becomes one of exploring ever more sophisticated ways for quantum computation to offer useful things for procedural generation. We’ll begin by making tools that we probably wouldn’t have thought of if we weren’t thinking in terms of quantum software. Then at some point we’ll move on to things that we can’t do without using quantum hardware.
Reaching such a point is known as ‘Quantum Advantage’, and is a big deal in the quantum computing community. Actual users, however, will care more about whether it is actually useful to run any given piece of quantum software. They won’t care about the digital vs. quantum hardware wars going on in the background. They just want the results at the end. So, it’s achieving usefulness with quantum software that I prefer to focus on.
But let’s not get ahead of ourselves. The first step towards this era of expanding usefulness is to prove that even quantum software for up to 20 qubits can be useful. So let’s do that!
Now’s the time to get specific. Procedural generation means that I need to generate something. But what? Terrain generation is a classic, so let’s start with that!
Perlin noise is a ubiquitous tool for procedural terrain generation. It would be great to be able to make something equally useful with quantum software. So I started with the aim of making something for terrain generation.
There is also another, much less sophisticated method for terrain generation: create a bunch of random points, concentrated where you want high ground, and then apply a blur effect. Implementing something like this seemed like a more attainable goal for a first step, so that’s what I did.
For this I started by developing a way to encode height maps as quantum circuits (which are the fundamental elements of quantum software). These have some similarities to those of the Boolean circuit model of digital computation. The qubits are the bits, and they pass through various operations as the computation proceeds.
Once we can encode height maps as circuits, we can manipulate them. The encoding I used focuses on squeezing as many points into as few qubits as possible. This doesn’t leave a lot of flexibility to offer much high-level control. However, pretty much any change you make to the circuit will induce some kind of interference effect.
Mostly I work with operations than can be thought of as partial forms of the Boolean NOT gate. When applied to normal bits, the NOT flips the value between 0 and 1. With quantum gates we can parameterize this to perform a manipulation that can do half a NOT, or a quarter, or any fraction you want.
If we apply this operation to all our qubits, then we can look at how the height map changes as we increase the fraction. We start off seeing something like a blur effect. Interference effects then begin to take over, creating patterns that we wouldn’t get from a simple blur.
In this example shown here, we start off with two seemingly arbitrary points in (a). They start to blur, but then the interference effects kick in. This results in a pattern emerging: in this case the chessboard pattern of (f). This particular result is explicitly due to the two pixels I started off with. If you use a different seed, you’ll see a different journey.
As well as generating these patterns, I have also used them. My main use is as a substitute for high-frequency Perlin noise in terrain generation. So, you make the main profile of, for example, an island through some other method. Like the one in (c) here. Then you make a seed set of pixels, as in (a), and quantum blur it to generate a pattern like the one in (b). Then you splat the pattern all over the profile to create your final terrain.
Here you can see a 2D example, as well as a 3D rendering that was used in our education game QiskitBlocks. Details such as information about grass type and tree placement in the 3D rendering was also made using the quantum process.
Since RGB images are basically just three height maps stuck together, we can also manipulate images. This could be be to just make weird looking images using the interference effects. A more sophisticated use is to encode a pair of images and induce a teleportation-like effect between them. Quantum Teleportation is an actual thing for quantum systems where information is transferred between qubits, so it is something that we can actually write a program for. Of course, it’s not the same as teleportation in Star Trek, but we can use it to make transition animations.
The idea behind the encoding can also be used for other forms of data. I’ve tried music
and a Mario level:
Evidently I can use it to make content for some nice tweets. But is the method actually useful? For this I need external validation.
There are two major examples of external use. One is the a game studio that I’ve been working with, who are using the method for elements of procedural generation in an upcoming game. The game has a sci-fi setting, with the quantum method here injecting a genuine flavor of science into their fiction.
The other is that the artist Libby Heaney used some of these ideas as the starting point for some of her own art.
The fact that the results emerge from quantum software is something that is highlighted in both these use cases. There is some form of what I call ‘algorithmic provenance’ going on here: It is important to the user that these results originate from the quantum region of algorithm space, and aren’t just sparkling linear algebra.
This is not a sustainable feature. There won’t always be people wanting to use quantum software just because it is quantum. But it is a start, so I’ll take it. These use cases show that the quantum blur method is useful to external parties, at least to some degree.
In conclusion, the era of using quantum software to create actually useful methods for procedural generation starts now!
With this method described here, it is better to use emulation than real quantum hardware, but that will start to change soon. In fact, I’ve already used one of our biggest devices in a completely different method for PCG.
So expect to see me again in the future, still banging the drum of quantum computing.
Until then, you can try out using the quantum blur effect yourself. It’s native to Python, but we have a Unity plugin too. Hopefully these can help provide even more ways to be useful!
