aristaeus commented 2 years ago

Abstract

There is a purely classical procedural generation algorithm called "wave function collapse". Despite the name, this is a classical algorithm that only has a (very loose) analogy to quantum mechanics. Let's make a properly quantum procedural generation algorithm!

Description

Procedural generation is a technique where computers randomly generate content, usually for art, computer games, or screensavers. Wave function collapse (WFC) is a classical algorithm which creates an initial "superposition" state, and then uses classical constraint satisfaction algorithms to "collapse" the superposition to a single concrete state, satisfying the rules set by the programmer (see a gif here).

Some prior work has been done on the use of quantum computers in procedural generation. These range from simply using it as a source of randomness, (1, 2) to more complicated algorithms using entanglement and interference.

Our goal is to more directly realise the promise of the analogy in the WFC algorithm. The state of our system can be represented on qubits, and prepared into a genuine quantum superposition. By encoding the rules of the procedural generation into a Hamiltonian, an algorithm like QAOA or VQE (or Grover's?) may be used to suppress "invalid" states in the superposition. The resulting superposition may be measured, and will be in a random, but valid, procedurally generated state.