the initial state of an example graph + its encoding method
the complete circuit that solves the example graph I provided
the outcomes of the aforementioned circuit
the acceptable solutions to the sample graph

Inspiration

I completed this project because of a deep interest in quantum computing and quantum machine learning, and a desire to learn more about it.

What it does

My program uses Grover's Quantum Algorithm to color regions on a graph so that no two regions of the same color are touching. to do this it places all possible states into a quantum superposition and uses a matrix called an oracle to isolate the possible solutions to the problem and uses a diffusion matrix to increase the chance of the desired outcomes. repetition of the last two steps completed enough times makes the desired outcomes the only ones likely to occur.

How I built it

I initially started trying to solve this problem for any graph which consisted of 2 or more square regions each bordering between one to four other regions. I eventually discovered an encoding method and oracle algorithm which would successfully solve this problem, but needed at least 5 qubits per region to encode this. I decided that this was a prohibitively large number of resources and added more constraints to the input.

I changed my base constraints to the assumption that the square regions fit into a rectangle which was X regions across and Y regions down. this allows me to only need one qubit per region to encode the starting state, with the total number of qubits needed being equal to two times the number of regions.

the oracle uses XOR gates (consisting of two CNOT gates each) to verify that 2 regions aren't the same color in a possible solution. Each XOR gate output must be stored on a different qubit, and the minimum number of possible XOR comparisons that could prove a solution is one less than the number of regions. A multi input gate is needed to verify that all XOR gates outputted correctly for a possible solution, bringing the number of qubits needed for solutions up to be equal to the number needed to store the possible states.

the output is a binary number where each number determines the color of the corresponding region. To change the input, simply enter the number of regions across the new area is as X and the number of regions down it is as Y.

Challenges I ran into

I had difficulties conceptualizing how to minimize the number of qubits because I didn't want to constrain the possible inputs. I eventually constrained my inputs enough that each region could be represented with one bit, at which point I started making progress quickly.

What I learned/What's next

I'm proud to say that the program I created is capable of accepting variably sized input graphs. I learned about Grover's algorithm in far more detail than I ever knew before, and gained a better understanding of both Qiskit and quantum computing in general. I also learned more about myself. I started this project uncertain of myself and my abilities, and not knowing if I would be able to accomplish my goals. In the process of completing my project I proved to myself that I am more than capable of achieving difficult goals when I commit myself to my goals. My next goal with this project is to implement a way to reduce the number of qubits needed to process the oracle, which would increase the speed and scope of this project.