Graph Coloring using Grover Search: Part 2

We're back with a continuation of the series of posts on graph coloring with Grover search! This part contains circuit implementations for coloring the triangle graph K_3. Please check out Part 1 here to familiarize yourself with the 3-coloring problem and its quantum solution!

The aim of this post is to implement and run a circuit that solves the 3-coloring problem for K_3. Recall that the circuit we designed last time is the following:

We quickly create the K_3 graph and import our required modules before looking at the implementation.

# Install blueqat if not already installed!
# !pip install blueqat

# Import Libraries
from blueqat import circuit
import math

# Create the triangle graph
vertices = [0, 1, 2]
edges = [[0,1], [1,2], [0,2]]

Implementation Prerequisites

The CCCX gate

Most quantum machines do not support multi-controlled not gates, and therefore we need to implement the cccx gate used to flip the phase of the coloring solution via only toffoli gates. It is simple to do this using a new ancilla qubit. We can replace the cccx gate with the following circuit, with an ancilla initialized to \lvert 0\rangle:

We can check the statevectors to convince ourselves that this construction works out:

It's possible to reuse this ancilla in other parts of the circuit as it turns out clean.

def apply_cccx(circuit, controls, target, ancilla):
    # Applies a CCCX gate onto the circuit. Requires a clean ancilla qubit.
    assert len(controls) == 3, '3 controls were not provided: CCCX gate needs a list of controls of size 3.'
    circuit.ccx[controls[0],controls[1],ancilla]
    circuit.ccx[controls[2],ancilla,target]
    circuit.ccx[controls[0],controls[1],ancilla]

E3 and E3_dagger gates

We already saw in Part 1 a circuit that takes the state \lvert 00\rangle to \frac 1{\sqrt3}(\lvert 01\rangle + \lvert 10\rangle +\lvert 11\rangle, and we called it E_3. We implement it below.

def apply_E3(circuit, targets):
    # Applies an E3 gate on two qubits.
    assert len(targets) == 2, 'E3 only acts on 2 qubits.'
    circuit.ry(2*math.asin(math.sqrt(2/3)))[targets[0]]
    circuit.ch[targets[0],targets[1]]
    circuit.x[targets[1]]

def apply_E3_dagger(circuit, targets):
    # Applies an E3_dagger on two qubits.
    assert len(targets) == 2, 'E3 only acts on 2 qubits.'
    circuit.x[targets[1]]
    circuit.ch[targets[0],targets[1]]
    circuit.ry(-2*math.asin(math.sqrt(2/3)))[targets[0]]

The Diffusion Operator

Recall that we used the operator {E_3^\dagger}^{\otimes 3} followed by a multiple anti-controlled X gate on a \lvert -\rangle qubit to achieve phase kickback, followed by {E_3}^{\otimes 3}. This conjugate transformation negates the phases of all the 27 basis states \{\lvert 01\rangle, \lvert 10\rangle, \lvert 11\rangle\}^3 when applied on the uniform superposition state. We see that the same effect can be achieved on these 27 states by using just a \overline{cc}x-gate, as illustrated in the animated gif below.

Of course, the \overline{cc}x-gate flips many more amplitudes other than the 27 basis states; however, these do not appear in our 3-coloring problem due to the nature of the initialization and oracle.

Our final reduced circuit can be checked on quirk.

def apply_diffusion(circuit, vertex_qubits, phase_flip_ancilla):
    assert len(vertex_qubits) == 6, 'Only implemented for 3 vertices and 6 qubits!'
    for i in range(int(len(vertex_qubits)/2)):
        apply_E3_dagger(circuit, [vertex_qubits[2*i], vertex_qubits[2*i+1]])
    
    # Put in anticontrolled toffoli
    circuit.x[vertex_qubits[0]].x[vertex_qubits[2]]
    circuit.ccx[vertex_qubits[0], vertex_qubits[2], phase_flip_ancilla]
    circuit.x[vertex_qubits[0]].x[vertex_qubits[2]]
    
    for i in range(int(len(vertex_qubits)/2)):
        apply_E3(circuit, [vertex_qubits[2*i], vertex_qubits[2*i+1]])

Color-checking component of oracle

We now implement the color checking part which checks whether two vertices of an edge get different colors. Observe that this part of the oracle is repeated and designed in such a way that the edge qubits are de-entangled from the vertex qubits!

def apply_color_check(circuit, edges, vertex_qubits, edge_qubits):
    # for each edge, apply two toffoli gates onto its corresponding qubit
    for i in range(len(edges)):
        # get the vertices u,v incident to the i'th edge
        e = edges[i]
        u = e[0]
        v = e[1]
        # apply two toffolis
        circuit.ccx[vertex_qubits[2*u], vertex_qubits[2*v+1], edge_qubits[i]]
        circuit.ccx[vertex_qubits[2*u+1], vertex_qubits[2*v], edge_qubits[i]]

The inverse operation of the color-checking component is itself, as every ccx gate applied in apply_color_check can commute. We're now ready to implement the oracle part of the circuit!

Grover Oracle

def apply_grover_oracle(circuit, edges, vertex_qubits, edge_qubits, phase_flip_ancilla, clean_ancilla):
    apply_color_check(circuit, edges, vertex_qubits, edge_qubits)
    apply_cccx(circuit, controls=edge_qubits, target=phase_flip_ancilla, ancilla=clean_ancilla)
    apply_color_check(circuit, edges, vertex_qubits, edge_qubits)

The complete circuit and its simulation!!

We're now prepared to create the circuit and simulate it using blueqat!

# Setting the circuit and registers
from blueqat import Circuit
qc = Circuit(11)
vertex_qubits = list(range(6))
edge_qubits = list(range(6,9))
phase_flip_ancilla = 9
clean_ancilla = 10

# Circuit Initialization
for v in vertices:
    apply_E3(qc, [vertex_qubits[2*v], vertex_qubits[2*v+1]])
qc.h[phase_flip_ancilla].z[phase_flip_ancilla]

num_iter = math.ceil(math.pi/4 * math.sqrt(2**6/6)) # We're cheating here since we know there are 6 solutions...
print('Using Grover Rotation {} times...'.format(num_iter))

for _ in range(num_iter):
    # Oracle
    apply_grover_oracle(qc, edges, vertex_qubits, edge_qubits, phase_flip_ancilla, clean_ancilla)

    # Diffusion
    apply_diffusion(qc, vertex_qubits, phase_flip_ancilla)

# Measure
qc.m[0:6]

# Get the most frequent result
r = qc.run(shots=1000).most_common(5)
print(r)
r = r[0][0]

print('Vertex 0: {}\nVertex 1: {}\nVertex 2: {}'.format(int(r[0:2],2),int(r[2:4],2), int(r[4:6],2)))

Using Grover Rotation 3 times...
[('10011100000', 110), ('01111000000', 107), ('01101100000', 100), ('11011000000', 84), ('10110100000', 73)]
Vertex 0: 2
Vertex 1: 1
Vertex 2: 3

Conclusion: Part 2

• We implemented our coloring algorithm from Part 1 and successfully found a proper coloring of K_3!
• Sadly, a blog post on Part 3 is put on hold for now. This is because the generalization to arbitrary graphs is pretty straightforward, whereas for k colors, the solution becomes quite mathematical.

Answers to "Food for Thought" questions

Let's go back to the questions in the last section of Part 1.

• I think I was able to answer the first question pretty well in this post.
• The general oracle for checking whether two colors are identical or not can be implemented using a lot of controlled not gates. For a detailed explanation, one can look at microsoft's Q# tutorial at [1].
• As for the final question of whether this formulation is better or worse than QUBO, I'd like to refer the reader to a seminal paper of Roland and Cerf [2]. It is known that adiabatic quantum computing is equivalent to gate-model quantum computing, and these authors demonstrate that the speedup of O(\sqrt N) obtained via Grover search on an entire solution space of size N, is exactly the speedup given by QAOA algorithms. However, in NISQ era, adiabatic algorithms have better promise since gate models require a huge number of qubits to maintain coherence for a long amount of time.