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 K3. 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 K3. Recall that the circuit we designed last time is the following:
We quickly create the K3 graph and import our required modules before looking at the implementation.
Copy
# 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 ∣0⟩:
We can check the statevectors to convince ourselves that this construction works out:
∣abcd⟩∣0⟩↦∣abcd⟩∣ab⟩↦∣abc⟩∣d⊕abc⟩∣ab⟩↦∣abc⟩∣d⊕abc⟩∣0⟩.
It's possible to reuse this ancilla in other parts of the circuit as it turns out clean.
Copy
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 ∣00⟩ to 31(∣01⟩+∣10⟩+∣11⟩, and we called it E3. We implement it below.
Copy
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 E3†⊗3 followed by a multiple anti-controlled X gate on a ∣−⟩ qubit to achieve phase kickback, followed by E3⊗3. This conjugate transformation negates the phases of all the 27 basis states {∣01⟩,∣10⟩,∣11⟩}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 ccx-gate, as illustrated in the animated gif below.
Of course, the ccx-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 .
Copy
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!
Copy
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!
We implemented our coloring algorithm from Part 1 and successfully found a proper coloring of K3!
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(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.