Graph coloring with Grover search

Graph coloring is one of the most fundamental problems in graph theory and computer science, and has a myriad of applications in the real world.
Not only is the coloring problem hard to solve in general even for 3 colors, the best known classical algorithms for 3-coloring require exponential time.
Our goal in this series of blog posts is to design and implement an algorithm for a $k$ -coloring of any arbitrary graph $G$ .

Basic Definitions

A graph $G=(V,E)$ consists of a vertex set and edge set $E$ whose elements are distinct pairs $\{x,y\}$ from $V$ .
For $k\ge 2$ , a $k$ -coloring of a graph $G$ is an assignment of colors to vertices $f:V\to \{c_1,\ldots,c_k\}$ such that edges that are adjacent receive distinct colors! For example, the graph drawn below is $3$ -colorable via $f(0)=f(2)=f(4)=c_1$ , $f(1)=f(3)=f(5)=c_2$ , $f(6)=c_3$ .

import networkx as nx
def create_cycle(length: int):
    # Returns a nx.Graph() object representing a cycle of prescribed length
    graph = nx.Graph()
    graph.add_nodes_from(range(length))
    graph.add_edges_from([(i,(i+1)%num_vertex) for i in range(length)])
    return graph
nx.draw(create_cycle(7), with_labels=True, font_weight='bold')

<Figure size 432x288 with 1 Axes>

The usual way to solve the $k$ -coloring problem is to transform it into a QUBO problem, which can be then solved using QAOA, and a tutorial on how to solve this problem using Blueqat-SDK is available here: EN/JP.

We shall take a different route and solve the problem using a quantum circuit from scratch.

Grover's Algorithm and Amplitude Amplification

Recall that the standard Grover's algorithm works in the following three rough steps:

Initialization: Create a uniform superposition of all possible quantum states.
Oracle: Apply an oracle that marks a specific state and changes its sign to negative.
Diffusion: Rotate the state towards the marked state.

Below is a basic circuit that implements Grover's Algorithm to mark the state $\mid 11\rangle$ .
The state evolves as follows:

\mid 000\rangle \stackrel{H^{\otimes 3}}\longrightarrow \mid +++\rangle \stackrel{I^{\otimes 2}\times Z}\longrightarrow \mid ++\rangle \mid -\rangle \stackrel{CCX}\longrightarrow \left(\frac{\mid 00\rangle + \mid 01\rangle + \mid 10\rangle - \mid 11\rangle}{\sqrt2}\right)\mid -\rangle\stackrel{\text{Diffusion}}\longrightarrow \mid11\rangle\mid -\rangle.

Refer to this page for an exposition on Grover's Algorithm.

Organization of this series of posts

We shall break down and tackle the problem of $k$ -coloring a graph in the following parts:

Part 1: Describe a circuit solving the 3-coloring problem for the triangle graph ( $K_3$ ).
Part 2: Implement the circuit for 3-coloring $K_3$ .
Part 3.1: Generalize the above circuit for general graphs.
Part 3.2: Generalize the circuit to a construction for $k$ colors.

So our goal in this blog post is to describe a quantum circuit that can solve the 3-coloring problem using Grover search.

Part 1: Solving the 3-coloring problem

Below is an illustration of $K_3$ :

num_vertex = 3
graph = create_cycle(num_vertex)
num_edges = len(graph.edges())
nx.draw(graph, with_labels=True, font_weight='bold')

<Figure size 432x288 with 1 Axes>

Circuit Construction

1.1: Design

Our goal is to create a circuit where the output will encode information about the colors given to a vertex. Since 3 colors are used, each vertex would require 2 qubits. Let us use the states $\mid 01\rangle, \mid 10\rangle, \mid 11\rangle$ for denoting the three colors corresponding to a given vertex.
The oracle would require checking that each edge receives a different color. This implementation would require 3 more qubits corresponding to the number of edges, plus a phase-flip ancilla.
The diffusion operator needs to reflect and rotate around the subspace spanned by $\{\mid 01\rangle, \mid 10\rangle, \mid 11\rangle$ instead of the full space. This requires redesigning the diffusion operator more carefully than using $H$ and multi-anticontrol ( $\overline C \cdots \overline CX$ ) gates.

In short, we need $2\cdot \text{num_vertices} + \text{num_edges} + 1 = 10$ qubits.

1.2: Initialization

We need to figure out a way to send the state $\mid 00\rangle$ to the state $\frac 1{\sqrt3} (\mid01\rangle + \mid 10\rangle + \mid11\rangle)$ . In advanced libraries such as qiskit, this can be achieved by built-in functions. However, these gates are not available on real systems, so we shall quickly figure out how to achieve this construction. Let $E_3$ denote the circuit below:

E3-circuit

A simple computation shows us that $E_3\mid 00\rangle$ is a uniform superposition of the states $\mid01\rangle, \mid10\rangle$ and $\mid11\rangle$ :

\begin{aligned}\mid 00\rangle \stackrel{R_y(\sin^{-1}\left(\frac{\sqrt2}{\sqrt3}\right))\otimes I}{\longrightarrow} \frac 1{\sqrt3}\mid 00\rangle + \frac{\sqrt 2}{\sqrt 3}\mid 10\rangle&\stackrel{CH}{\longrightarrow} \frac 1{\sqrt3}\mid00\rangle + \frac{\sqrt2}{\sqrt3}\cdot \frac1{\sqrt2}(\mid 10\rangle + \mid 11\rangle)\\& \stackrel{X}{\longrightarrow} \frac 1{\sqrt 3}\mid01\rangle + \frac 1{\sqrt3}\mid 11\rangle + \frac 1{\sqrt3} \mid 10\rangle.\end{aligned}

Hence, for each vertex, we initialize its corresponding qubit pair using $E_3$ .

1.3: Oracle

The point of the oracle is to imitate the condition for 3-coloring: For every edge $\{u,v\}\in E(K_3)$ , the states that we need to flip the signs of are $\mid 01\rangle\mid10\rangle, \mid01\rangle\mid11\rangle, \mid10\rangle\mid01\rangle, \mid10\rangle\mid11\rangle,\mid11\rangle\mid01\rangle$ and $\mid11\rangle\mid10\rangle$ .
We can do this for a single edge using the following circuit:

oracle-flip

The main idea is to use the phase kickback from the $\mid-\rangle$ state in the last qubit to switch the signs of the six states mentioned above.
It can be checked that the state of the system evolves as (here $i,j\in\{01, 10, 11\}$ ):

coloring-eq

As we need to make sure that all valid colorings have their amplitudes flipped, we would need to use a single phase flip qubit to flip all the edges, as seen in the circuit diagram below.

circuit-initialization-and-oracle

1.4: Diffusion

The original role of the diffusion operator in the usual Grover's algorithm is to produce a reflection around the initial state $\mid 0\rangle^{\otimes n}$ . However, since we are restricting ourselves to the state $\mid u \rangle := \frac 1{\sqrt3} (\mid 01\rangle + \mid 10\rangle + \mid 11\rangle)$ , we have to implement a reflection around $\mid u\rangle^{\otimes n}$ .

This requires us to implement the operator $D = 2\mid u^n\rangle\langle u^n\mid - I$ . Observe that,

{E_3^\dagger}^{\otimes n}DE_3^{\otimes n} = 2{E_3^\dagger}^{\otimes n}\mid u^n\rangle\langle u^n\mid E_3^{\otimes n}- I = 2\mid 00^n\rangle \langle 00^n\mid - I,

Which is exactly the phase flip oracle that flips the phase of $\mid 0\rangle^{\otimes 2n}$ ! So, we need to use the same diffuser as Grover's algorithm, but instead of hadamard gates we use $E_3$ and $E_3^\dagger$ gates.

The complete circuit therefore, is in this Quirk Link (for a single iteration).

Conclusion: Part 1

We have finished designing a circuit that would give a $3$ -coloring of the triangle graph $K_3$ .
In the next part, we'll implement this algorithm and run it on both a simulator and a quantum computer.
Of course, due to the sheer number of controlled operations happening in this algorithm, we're pretty much doomed to get terrible results on a real computer, but nevertheless it'd be an interesting experiment to try.

Food for thought

The following issues are yet to be addressed, and the reader is encouraged to think about these issues and play around with the quirk circuit above before reading the next post! :)

How do we even implement the multi-controlled X gate in the diffusion operator? Most quantum computers and libraries support only upto Toffoli gates. Is it really required, or can we optimize it for our special case of 3-coloring the triangle?
What about an oracle in general? We claim that our algorithm generalizes to multiple colors, but the construction of the oracle is still an unanswered question.
How does the requirements of this algorithm scale with the number of qubits? Is its performance worse or better than the QUBO formulation?

Coloring graphs using Grover search: Part 1

Sayan Mukherjee