Quantum Opt’z: Graph Coloring

How to solve graph coloring using Quantum computation

15 min readDec 29, 2022

In this article, we discuss about the application of the variational method we discussed in the previous article.

we study the Graph coloring problem by using classical computation technique and also we explore quantum solution with a 5 step process and we walk through the QUBO Matrix generation. We achieve the solution using Rigetti’s pyQuil and IBM Qiskit Libraries. We explore in depth of the problem logic using pyquil and we use IBM Qiskit inbuilt QAOA function for the problem solution.

Setup:

Consider a graph G(V, E) as shown below, where V represents the Vertex or node and E represents the Edge. Here Vertex/Node represented as numbers (0, 1, 2 , 3, 4, 5) where as the edges are the connecting lines between the two vertices.

The Graph problems can be classified as

Vertex coloring problems
Edge coloring problems

Vertex coloring problems seek to assign colors to nodes of a graph in such a way that adjacent nodes receive different colors.

Similarly, Edge coloring of a graph is an assignment of colors to the edges of the graph so that no two incident edges have the same color

The K-coloring problem attempts to find such a coloring using exactly K colors.

These problems can be modeled as satisfiability problems as follows:

Problem:

The problem statement, initially observed in the paper[1].

Let consider a variable x, where nodes represented with variable i and colors represented with variable j.

the value of x shall be 1 if node i is assigned with color j, and 0 otherwise.

Since each node must be colored, we have the constraints

where n is the number of nodes in the graph.

The above constraint imposes the rule that every node shall assign with a color.

similarly, adjacent nodes shall be assigned with different colors.

To impose this constraint, let’s consider node i and node j as adjacent and p as the color.

The above constraint imposes the rule that sum of adjacent nodes with a color p shall be less than or equal to 1. The possibility here is either zero or one.

Suppose, same color got applied to the adjacent nodes then both node i and node j related variable x shall be 1 and 1 which gives the result as 1 + 1 = 2 which fails the condition.

Classical Solution:

we follow the steps as mentioned below:

A vertex should be colored with the lowest number of colors.
Another uncolored vertex should select the second-lowest number of colors to be assigned to the vertex, other than the color selected in step 1 in case of adjacent vertices.
Repeat above two steps until all vertices are colored.

Let’s take the below graph and solve the vertex coloring using minimal number of colors.

import networkx module to display the graph.

Assign some colors to the variable colors

represent the graph as points

generate the edges connectivity of the graph with the provided edges.

assign color to the vertices following the constraints

the below function performs generate the edge connection and assign the colors. Then finally attach the data to variables and print the color assignment.

with six vertices and provided edge points the result as shown below

to represent the result in the graph model for visualization we use networkx and pass the color_map captured in the above code block.

6 node graph with the assigned colors as shown below.

Quantum Solution:

We follow the steps as mentioned below:

Analyze problem statement and prepare node graph. Let’s consider 5 node graph[1].
finding the number of colors required, is itself an NP-Hard optimization problem. so for this problem we consider the number of colors required as 3.
Then derive the constraints using number of nodes and number of colors.
Once the model is available in this form, our next step is to convert the model to QUBO form (Quadratic Unconstrained Binary Optimization) using penalties.
Then we need to perform the minimization operation on the QUBO Matrix as shown below

Where Q is the penalty imposed QUBO Matrix and x is the variable representing the nodes position.

Solving this model yields the feasible coloring.

Problem:

step 1:

Number of nodes(n): 5

Node connection(edges): [(1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5)]

Let’s draw a graph using networkx module

call the above function with the given data

the function draws the below node graph

step 2:

Number of colors be 3, let’s consider the constant P as 4 (as discussed in the article).

step 3:

Deriving the constraints.

Here we can apply two constraints,

Every node shall be assigned with a color.
Adjacent nodes shall not be assigned with same color.

The first constraint with number of colors as 3 shall be

Let’s expand the constraint with all possibilities,

which states, a node shall be assigned with any color but shall be assigned with only one color.

we have 15 variables and 5 different constraints.

The second constraint, refers to the adjacent vertices or nodes, where i and j are the adjacent vertices or nodes and k is the number of colors which is 3 in the current problem.

Here the adjacent nodes/vertices are (1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (3 , 4) and (4, 5)

for the vertices i = 1, j = 2 and k = 1, 2, 3

for the vertices i = 1, j = 5 and k = 1, 2, 3

for the vertices i = 2, j = 3 and k = 1, 2, 3

for the vertices i = 2, j = 4 and k = 1, 2, 3

for the vertices i = 2, j = 5 and k = 1, 2, 3

for the vertices i = 3, j = 4 and k = 1, 2, 3

for the vertices i = 4, j = 5 and k = 1, 2, 3

The above constraints impose the condition that the adjacent nodes shall have a unique color assigned to it.

we have 15 variables and 21 different constraints.

collectively, from the condition 1 and condition 2 … there are 15 variables and 26 constraints.

step 4:

The model has 15 variables and 26 constraints. To recast this problem into the QUBO form, we use quadratic penalties.

For ease of notation, we will first re-number the variables using a single subscript, from 1 to 15, as follows:

The vertex/node assignment equations and the penalties using slack variables, we get as shown below

Applying to the first set of equations

Similarly, for remaining set of equations with the first condition

Combining the all 5 set of equations forms the Hamiltonian Q encoding our objective function as

Taking P to equal 4 and updating these penalties in the “developing” Q matrix gives the partially completed Q matrix along with an additive constant of 5P(since 5P is a constant not displayed in the Q matrix).

The diagonal elements shall be updated with the “-4” whereas off diagonal elements shall be split equally between row by column and column by row because these elements are twice the value representing the forward and reverse actions.

To complete our Q matrix, it is a simple matter of inserting the remaining penalties representing the adjacency constraints into the above matrix.

For these, we use each adjacent pair of nodes and each of the three allowed colors. We have 7 adjacent pairs of nodes and three colors, yielding a total of 21 adjacency constraints. Allowing for symmetry, we shall insert 42 penalties into the matrix, augmenting the penalties already in place.

For example, for the constraint ensuring that nodes 1 and 2 cannot both have color #1, the penalty is

implying that(P = 4) we insert the penalty value “2” in row 1 and column 4 of our matrix and also in column 1 and row 4. Including the penalties for the other adjacency constraints completes the Q matrix as shown below

step 5:

The above matrix incorporates all of the constraints of our coloring problem, yielding the equivalent QUBO model.

Where first part represents the first set of penalties and the second part represents the second set of penalties. Right side represents the equivalent penalties we have applied.

Combining both the penalties and representing in to a single matrix can be shown as below

Here our objective is to identify the solution of the graph by applying constraints to form the colored graph.

Solve the problem using IBM Qiskit:

draw the node graph using draw_graph function which uses the networkx python module

invoke the function with the number of nodes and edges connection list as shown below

Let’s define number of colors and the P value: num_color = 3
P = 4

prepare an initial Q matrix and introduce the first set of constraints as shown below

the above code block yields the output as shown below

let’s introduce the second set of constraints with the below code block

the above code block returns the complete Q matrix as shown below

convert the problem to the linear format using cplex. Which converts our Matrix problem to an equation

import the following modules

then create an instance for the Model class. generate binary variables then apply x’ Q x which returns the objective function. Then apply the minimize condition to the objective function. Now our model is completed, but it is in the cplex format. Convert the docplex to Quadratic Program, which is the required format to solve using IBM Quantum.

let’s see, how the model looks like

Since the Q Matrix is formed by applying all the constraints, we have not used the Qiskit's constraints functionality. Which is why it is showing subject to “No constraints”.

We solve our Model Quantum Program using the QAOA algorithm with the Qasm Simulator with the below code block

qaoa_result holds the output as shown below

<MinimumEigenOptimizationResult: 
fval=-20.0, 
x0=0.0, 
x1=0.0, 
x2=1.0, 
x3=0.0, 
x4=1.0, 
x5=0.0, 
x6=1.0, 
x7=0.0, 
x8=0.0, 
x9=0.0, 
x10=0.0, 
x11=1.0, 
x12=1.0, 
x13=0.0, 
x14=0.0, 
status=SUCCESS>

Solving this model using QAOA yields the feasible coloring:

x2 = x4= x6 = x11 = x12 = 1 with all other variables equal to zero.

with this result let’s assign colors to the nodes:

the below function accepts the qaoa_result which is generated by the model and also number of colors we would like to assign which is 3 in our case.

Below is the result captured by the above function

with the above result we draw a graph as shown below

the function accepts number of nodes, edge connection list and the result of the assign_color function.

Switching back to our original variables, this solution means that nodes 3 and 5 get color #1(Blue), node 2 get color #2(Green), node 1 and 4 gets color #3(Red).

Solve the problem using Rigetti’s pyQuil:

Import the required dependencies as shown below.

draw the node graph using draw_graph function which uses the networkx python module

call the function with the number of nodes and edges connection list as shown below

Let’s define number of colors and the P value: num_color = 3
P = 4

prepare an initial Q matrix and introduce the first set of constraints as shown below

let’s introduce the second set of constraints with the below code block

convert the matrix to a linear algebraic form/x variable form using below code

split the data according to the regex and remove the empty parts

further we convert the expression similar to Ising model

the converted expression looks as shown below

We are ready with the Model.

In the following solution we introduce two classes.

Params classes to generate the required initial set of parameters and also update the params over the classical computing to prepare the next quantum circuit accordingly.
QAOA class initialize the execution with Ansatz circuit and receives the updated parameters from the SciPy minimize function which runs by the Cobyla optimizer.

Params Class:

The below function captures the qubit singles and pairs from the above generated Hamiltonian.

Params class accepts the Hyperparameters and Parameters. Where Hyperparameters shall not change once defined. Whereas parameters shall vary according to the Hybrid computation. We also define the X, Z and ZZ matrices using the property annotation.

the below function accepts the Hyperparameters as inputs and generates the initial beta and gamma parameters as shown below.

We are ready with the initial set of parameters. Let’s discuss about the Ansatz circuit formation.

bring the qubits to superposition state.
convert the incoming classical optimizer data as quantum rotation angles to perform the search over the complete space.
prepare the Cost Hamiltonian and Mixer Hamiltonian functions.

the below function brings the program or circuit to superposition using H gate.

the below function declares the quil variable and returns the memory reference.

The below function assign the memory references to the memory map.

prepare the two qubit Cost Hamiltonian as shown below.

prepare the single qubit Cost Hamiltonian as shown below.

prepare the Mixer Hamiltonian as shown below.

with the above prepared functions, let’s create the Ansatz fucntion as shown below.

We have prepared an Ansatz function or initial circuit as a starting point in the large space to perform search operation.

Now we define the Expectation values related functions.

the below function captures the eigen values from the wave function.

Here we take squared value and normal values with the below function and generated the wave function expectation.

with ansatz, params, wave function expectation. We create a QAOA class as shown below and we use Wave Function Simulator from the Rigetti computing.

we define the circuit depth as p. Also, p mentioned here is different from the P we defined while prepare the Hamiltonian Matrix.

We pass Hamiltonian, p to params class.

Generated params shall be passed as an input to the QAOA class along with the Hamiltonian.

By using the SciPy's Minimize function, we continue the hybrid loop and generates the optimized result.

from the generated result we pass the data to Wave Function Simulator to capture the probabilities for the corresponding result.

from the set of probabilities, we capture the maximum value related data.

we reverse the bit string to generate the node graph.

the below function accepts the result which is generated by the model and also number of colors we would like to assign which is 3 in our case.

the below code block generates the color map assignment as shown below.

prepare a function which draw color map according to the output generated by the classical optimizer.

draw the graph using above function.

Switching back to our original variables, this solution means that node2 get color #1(Blue), nodes 3 and 5 get color #2(Green), node 1 and 4 gets color #3(Red).

Conclusion:

I hope this article gave you lot of fun.

Following are some of the use cases of the Graph coloring problem can solve.

taxi schedule,
sports schedule,
seating plan,
Register allocation,
Airport gate scheduling,
Frequency allocation and so on…

If your are further interested in solving optimization problems like me, i would suggest you to solve the set of problems mentioned in the reference[1]. Feel free to comment if you need any support.

updated (Jan 11, 2023): Added conclusion part.

References:

qiskit textbook, pyquil docs, IITM course by (@Prabha M, Anil Prabhakar), Qubit by Qubit(The Coding School) course, IBM Quantum Challenge (2021, 2022), Wikipedia, stack exchange and open source materials.

Quantum Opt’z: Graph Coloring

How to solve graph coloring using Quantum computation

References:

Written by Anonymousket