Solving the general planar graph colouring problem using Grover's Algorithm. The backtracking algorithm takes O(k^n) for k colours and n vertices while Grover's reduces this complexity to O(sqrt(k^n)) providing a quadratic speedup.
Given 4 nodes to be coloured using 4 colours, we represent each colour using 2 binary bits and build the quantum circuit to apply the Grover search algorithm for proper colouring.
We visualize the results in the histogram and look for the most likely outcomes which will give us the proper colouring of the graph:
Finally, we convert the binary strings to the corresponding coloring.
