Literal Wavefunction Collapse Algorithm

Inspiration

This project is inspired by the classical Wave Function Collapse Algorithm for procedural generation

What it does

The classical algorithm generates procedural content (such as for video game levels) similarly to how one would solve a sudoku puzzle. Each node in a graph can take on one of several states probabilistically, but with limitations called adjacency rules (such as a 2D sprite for the surface of the earth not being above one for open air). It chooses randomly between the tiles with the lowest informational entropy (a.k.a. smallest number of possible states) to collapse into a state, then lets the consequences of that new state cascade to eliminate possibilities for other nodes. This is iterated multiple times until the entire graph of nodes has a determinate value.

The goal of the Literal Wave Function Collapse Algorithm is to modify this algorithm so that the consequence cascade happens automatically via entanglement of qubits between nodes, such that if a measurement is made of one node's state, that ends up cascading through the whole graph changing the possible states of the other nodes.

How I built it

While this project is incomplete, there exists a strategy to do so. First each node is assigned a qubit registry of a length equal to that of the number of possible states and then put into a W-state so that only one of the qubits in each node's registry will be |1>. Then each node is entangled with adjacent nodes such that the potential |1> state of a qubit in the first nodes ensures that the corresponding qubit in the second node takes on a |0> state if there is an existing adjacency node. Unlike the earlier step, how to implement this step eludes me for the moment, but I hope to properly implement this by Thursday.

Challenges we ran into

In addition to theoretical problems described above, there were issues trying to learn python on the fly since I am more used to the syntax of other languages (C#, Java, C++, etc.)

Accomplishments that we're proud of

I'm proud of the fact that I was able to learn so much over the past week from basically nothing to even attempt a project like this. Furthermore I have a history of giving up when things got difficult or looked like it would risk failure, and this project has really helped me overcome my pessimism.

What we learned

Over the past week I learned tons about quantum computing, python, and my own inner power to achieve great things through self discipline.

What's next for Literal Wavefunction Collapse Algorithm

This project is far from complete. I have several short and long term goals I need to accomplish in order for me to feel like this has bean completed to a satisfactory degree

Short Term Goals (hope to complete by Thursday presentation time):

• Implement known method for setting arbitrarily long W-states
• Research and implement method for entangling the qubits of adjacent nodes via adjacency rules.
• fix any bugs that could prevent a viable presentation

Long Term Goals:

• Implement as an abstract class or interface to make implementation more generalizable
• Replace current qubit register format of each qubit corresponding to 1 possible state and instead use a binary counting system so that qubit usage grows with O(log2(s)n) instead of O(sn) where n = the number of nodes, s = number of possible states.

Built With

• python
• qiskit