Schroedingers nyan cat
For me, one of the best things about games like Minecraft or Civ is the ability to explore randomly generated landscapes (and occasionally blow stuff up). This is all done through the magic of procedural generation.
One algorithm that recently caught my eye is called Wave Function Collapse, because it is inspired by ideas from quantum mechanics. From now on, we’ll just call it WFC.
Since my job is to write software for quantum computers, I instantly saw an opportunity. I would upgrade WFC from being just quantum-inspired, to truly being quantum.
To understand how I did this, we first need to understand the algorithm and its quantum inspiration. The WFC algorithm owes its name to the fact that each random choice is an event rather like a measurement of a quantum object. These objects can, in some sense, be doing multiple mutually exclusive things at once. This is called a quantum superposition.
For example, suppose you had a bunch of cats which obeyed the laws of quantum mechanics, and then shot at them with a quantum bullet. This bullet, while flying towards the cats, could be in a superposition of every possible trajectory at once. Then, once it hits, the superposition is spread to the cats too. Each will be simultaneously alive and dead, depending on which path the bullet took. But since there was only one bullet, only one cat will be dead. So the cats aren’t each in an independent superposition. Instead their fates are entangled together in a superposition of all possible victims.
Once a big, lumbering, non-quantum object such as ourselves comes along, the superposition will disappear. When we look at a cat, it has to decide whether it is alive or dead. This process of randomly dropping out of a superposition is the collapse of the wave function.
This all gives us a nice method for generating a collection of cats, where one of them is dead.
- Take some quantum cats
- Shoot them with a quantum bullet
- Observe them one-by-one to whether each is dead or alive
- …
- Profit!
The WFC algorithm takes this quantum inspiration and turns it into a powerful and useful method for procedural generation. Rather than just creating piles of abused cats, its actual function is to take bitmaps, and randomly riff on them to create larger images. The wave function collapse event is simulated by standard pseudorandom number generators. Nothing actually quantum ever happens.
To port it to run on a quantum computer, and hence make use of real collapses of wave functions, we need to make some choices. First, do we want a fancy algorithm that will run on the large, fault-tolerant device of the future, or do we want something that we can run today. Though the former is a very interesting possibility, I choose the latter.
For this, we just need to change one little thing. We need to find the point at which WFC makes its random choice, and replace it with a quantum random number generator. This will do exactly the same job, but it will do it using the genuine randomness that comes from collapsing wave functions in a quantum computer.
So that’s what I did. The quantum computer I targeted IBM’s 5 qubit prototype device, provided to the public over the cloud. The software I used was Qiskit, IBM’s Python package for creating and running jobs on quantum computers.
The method was exactly the same as explained in this tutorial on performing random number generation with Qiskit. Specifically, I wrote a simple Python class which, when initialized, asks IBM’s quantum device to set up a superposition of the two bit values 0 and 1, observe it, and then repeat the process thousands of times. The result is a list of thousands of bits, each the result of a wave function collapse. This list is then used for the random numbers required in WFC.
To test it out, it seemed fitting to get it to riff on the image of a cat. Here is the result. I’m not sure whether they are alive or dead.
