common.title

Overview
Service overview
Terms of service

Privacy policy

Contact

Sign in
Sign up
common.title

Coloring graphs using Grover search: Part 2

Sayan Mukherjee

2021/06/24 14:37
#algorithm #graph theory #grover #coloring #amplitude amplification

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 K3K_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 K3K_3. Recall that the circuit we designed last time is the following:

3-coloring-K3-circuit

We quickly create the K3K_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 0\lvert 0\rangle:

cccx-reduction

We can check the statevectors to convince ourselves that this construction works out: abcd0abcdababcdabcababcdabc0.\lvert abcd\rangle\lvert 0\rangle \mapsto \lvert abcd\rangle \lvert ab\rangle\mapsto \lvert abc\rangle\lvert d\oplus abc\rangle\lvert ab\rangle\mapsto \lvert abc\rangle \lvert d\oplus abc\rangle\lvert 0\rangle.

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 00\lvert 00\rangle to 13(01+10+11\frac 1{\sqrt3}(\lvert 01\rangle + \lvert 10\rangle +\lvert 11\rangle, and we called it E3E_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 E33{E_3^\dagger}^{\otimes 3} followed by a multiple anti-controlled X gate on a \lvert -\rangle qubit to achieve phase kickback, followed by E33{E_3}^{\otimes 3}. This conjugate transformation negates the phases of all the 2727 basis states {01,10,11}3\{\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 2727 states by using just a ccx\overline{cc}x-gate, as illustrated in the animated gif below.

diffusion-reduction-animated

Of course, the ccx\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 .

final-reduced-circuit

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 K3K_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 kk 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)O(\sqrt N) obtained via Grover search on an entire solution space of size NN, 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.

© 2024, blueqat Inc. All rights reserved