Checking and Coloring Graphs Through Quantum Circuits: An IBM Quantum Experience

Abstract

Checking the graph state and coloring it with possible least number of colors (or chromatic number) has many useful applications such as coloring of maps, solving Sudoku, making schedules to name a few. Though classical algorithms are used to solve this problem, it is believed that with quantum approach, the space and time complexity can be reduced. Thus, here we present quantum algorithms and design quantum circuits to check the graph states having two- and three-vertices with given edges and color them accordingly. We also propose a quantum algorithm for coloring of trees. For each of the cases, we discuss the quantum costs and complexities and compare it with the classical approach.

1 Introduction

Computers are no more limited to work in bits of 0 and 1’s. Through quantum mechanical phenomena like superposition and entanglement [1], quantum computers are designed to work with superposition state, where they encode information as quantum bits or qubits. Qubits represent quantum versions of bits and their respective control devices that work together to act as computer memory and a processor. Because a quantum computer can contain these multiple states simultaneously, it can easily crack algorithms like that of encryption [2], used today in very less time, whereas it takes billions of years by the best supercomputer available today. For example, a classical computer of n bits can have n states at a time but a quantum computer of n qubits can deal with $2^n$ states at a time. A processor that can use registers of qubits will be able to perform calculations using all the possible values of the input registers simultaneously. A quantum computer maintains a sequence of qubits, which can represent a 1, a 0, or any quantum superposition of those two qubit states. Superposition causes a phenomenon called quantum parallelism and is the motivating force behind the research being carried out in quantum computing. Graph algorithms are sure to benefit from parallelization, while on the other hand they contain a number of NP-complete problems [3] which may be liable for quantum boost or speedup.

Quantum algorithms are often probabilistic, in that they provide the correct solution only with a definite known probability. A quantum bit like electrons is with two spin states: “down” and “up” (typically written using Dirac’s bra–ket notation $|0\rangle$ and $|1\rangle$). In general, the state of a quantum bit (or qubit) is described by: $\alpha |0\rangle + \beta |1\rangle$ where $\alpha$ and $\beta$ are complex numbers, satisfying $|\alpha |^2 + |\beta |^2 = 1$. In quantum information theory, a quantum circuit is a model for quantum computation and is a sequence of quantum gates, which are reversible transformations on a quantum mechanical analog of an n-bit register. Here, various operations are performed using the following quantum gates (which are Pauli matrices), namely (i) X gate: It transforms $|0\rangle$ to $|1\rangle$ and vice-versa, (ii) Hadamard gate: It creates superposition states, (iii) CNOT gate: It performs not operation on the second qubit only if the first qubit is in $|1\rangle$ state, (iv) anti-CNOT gate: It performs not operation on the second qubit only if the first qubit is in $|0\rangle$ state.

Quantum algorithms are run on realistic model of quantum computers such as provided by IBM quantum experience platform (IBM QE) [4], D-wave quantum computers [5], trapped ion quantum computer (IonQ) [6] to name a few. IBM QE has recently gained popularity by providing the 5-qubit and 14-qubit quantum chips to the community and making easily accessible through QISKit. A number of quantum information processing tasks in the field of quantum simulation [7,8,9,10], quantum machine learning [11, 12], quantum error correction [13,14,15,16], quantum information theory [17,18,19], quantum cryptography [20], quantum optimization problems [21], designing quantum communication devices [22, 23] are tested on the real chips, and feasible results are obtained.

A graph G(V,E) consists of a set of objects called vertices V {$v_{1}$,$v_{2}$,...} and another set E {$e_{1}$,$e_{2}$, ...}, whose elements are edges such that edge $e_{k}$ or $e_{ij}$ is associated with vertices $v_{i}$ and $v_{j}$. Graph coloring is a way of assigning colors to these vertices of a graph such that no two adjacent vertices are colored using the same color. Chromatic number is the smallest number of colors needed to color a graph. In the following text, we provide quantum algorithms for checking the connection between vertices and assigning colors according to the chromatic number of the graph. In the original work of Hondt [24], algorithms were proposed of 2-coloring and 3-coloring graphs based on qubits and qutrits, respectively. In the recent Ref. [25], quantum circuits were proposed to check and color the graphs for 2- and 3-coloring for two and three vertices system.

The organization of the paper is as follows. In Sect. 2, we discuss the 2-coloring of graphs with circuit implementation of appropriate quantum operators. Following which, 3-coloring is explained by mapping qutrits into qubits and developing quantum circuits to generate the graph states, to check and color the graph in Sect. 3. Finally, we conclude in Sect. 6.

2 Algorithm for 2 Vertices Coloring

2.1 Algorithm and Implementation

We start by generating a superposition of all possible colorings of this graph when edges are ignored, as follows $H^{\otimes n}|0\rangle ^{\otimes n}=1/2^n\sum ^{2^n-1}_{i=0}|i\rangle$, where the i is written in binary. For example, for two vertices we would have $|00\rangle$, $|01\rangle$, $|10\rangle$ and $|11\rangle$ with normalization factor 1/2. Now for each back edge, $e_{ij}$ considers the projective measurement $M_{ij}$ with projection operators $O_{ij}$ and $I-O_{ij}$, where $O_{ij}=|01\rangle _{ij}\langle 01|+|10\rangle _{ij}\langle 10|$ and $I-O_{ij}=|00\rangle _{ij}\langle 00|+|11\rangle _{ij}\langle 11|$.

Now we have two vertices 0 and 1 in the graph, where there may be an edge connection or not. We can show in forms of two qubits that there are four possible states of connection between the two vertices, namely $|00\rangle$, $|01\rangle$, $|10\rangle$ and $|11\rangle$ states. Here we can show that the superposition of $(|00\rangle +|11\rangle )/\sqrt{2}$ are for no edge connected and that of ($|01\rangle$ + $|10\rangle )/\sqrt{2}$ for an edge connected (Fig. 1).

For the circuit in Fig. 2, we use the first two qubits for vertices (namely 0 and 1) and the edge joining these vertices are denoted by $|\psi _{01}\rangle$. For an edge connected, the user puts an X gate in the second qubit to specify the connection. The third qubit is the ancilla qubit which remains $|0\rangle$ for no edges connected and changes to $|1\rangle$ for an edge connected. The fourth and fifth qubit output the connection or graph state and show the superposition of $|00\rangle$, $|11\rangle$ or $|01\rangle$, $|10\rangle$ according to no or an edge connected. The sixth and seventh qubits denote the colors of the vertices, where $|0\rangle$ and $|1\rangle$ represent two different colors. It outputs $|00\rangle$ for no edges connected and $|01\rangle$ for an edge connected. The colors are shown hierarchically for each case (Table 1).

Fig. 1

2 vertices coloring: a No edge is connected. Thus, both the vertices are of same color, i.e., color 0 or blue. b Edge is connected. Thus, each of the vertices is of different colors, i.e., color 0 and 1 or blue and green

Fig. 2

Quantum circuit for 2 vertices coloring. The first two qubits represent the two vertices, the next is the ancilla qubit, the next two qubits show the graph state, and the last two depict the colors

Table 1 Quantum costs according to given figures

2.2 Quantum Cost

2.3 Classical Complexity

Coloring a graph with minimum number of colors is NP-complete problem. In classical computers, an adjacency matrix of space complexity O($n^{2}$) is also assigned to store information of connected vertices. However in case of a graph with just two vertices, the problem can be solved in constant time and space (Fig. 3).

3 Algorithm for 3 Vertices Coloring

3.1 Algorithm and Implementation

Here we have 3 vertices 0, 1, and 2 in a graph where there may be no edges or one to three edges are connected. In this case, we can show in forms of two qutrits that there are nine possible states of connection between any two vertices, namely $|00\rangle$, $|01\rangle$, $|02\rangle$, $|10\rangle$, $|20\rangle$, $|12\rangle$, $|21\rangle$, $|11\rangle$ and $|22\rangle$. Each qutrit represents a vertex, and again we start out by generating unrestricted coloring, $|\psi _{1}\rangle = H^{\otimes n}|0\rangle ^{\otimes n}=1/3^n\sum ^{3^n-1}_{i=0}|i\rangle$. The measurement $M_{ij}$ for each edge $e_{ij}$ is a straightforward generalization of that from the previous section: We split the Hilbert space in two sub-spaces, associated with allowed and disallowed coloring of vertices i and j, respectively, and project onto these sub-spaces. Concretely, the projection operators read as follows; $O_{ij}=|01\rangle _{ij}\langle 01|+|10\rangle _{ij}\langle 10|+|02\rangle _{ij}\langle 02|+|20\rangle _{ij}\langle 20|+|12\rangle _{ij}\langle 12|+|21\rangle _{ij}\langle 21|$ and $I-O_{ij}=|00\rangle _{ij}\langle 00|+|11\rangle _{ij}\langle 11|+|22\rangle _{ij}\langle 22|$.

Fig. 3

3 vertices coloring: a When none of the edges are connected, all vertices will have the same color, i.e., color 0 or blue. b When any two of the vertices are connected they will have different colors, i.e., color 0 and 1 or blue and green; the third vertex will have color 0 or blue. c When all the vertices are connected by edges, the three vertices will have three different colors, i.e., color 0, 1, and 2 or blue, green, and red

Fig. 4

Quantum circuit for 3 vertices coloring: Mapping qutrit to qubit system, a when there is no edge between any vertices, the qubits will show superposition of $|0000\rangle$, $|0101\rangle$ and $|1010\rangle$ states, b when there is an edge between vertices 0 and 1, the qubits will show superposition of $|0001\rangle$ and $|0100\rangle$ states, c when there is an edge between vertices 0 and 2, the qubits will show superposition of $|0010\rangle$ and $|1000\rangle$ states, d when there is an edge between vertices 1 and 2, the qubits will show superposition of $|0110\rangle$ and $|1001\rangle$, e when there are edges between vertices 0,1 and 0,2,the qubits will show superposition of $|0001\rangle$, $|0100\rangle$, $|0010\rangle$ and $|1000\rangle$ states, f when there are edges between vertices 0,1 and 1,2, the qubits will show superposition of $|0001\rangle$, $|0100\rangle$, $|0110\rangle$ and $|1001\rangle$, g when there are edges between vertices 0,2 and 1,2, the qubits will show superposition of $|0010\rangle$, $|1000\rangle$, $|0110\rangle$ and $|1001\rangle$, h when there is an edge between every two vertices, the qubits will show superposition of $|0001\rangle$, $|0100\rangle$, $|0010\rangle$, $|1000\rangle$, $|0110\rangle$, and $|1001\rangle$

Fig. 5

Quantum circuit for 3-coloring: connection between ancilla qubits and vertices

Fig. 6

Quantum circuit for 3 vertices coloring: connection between ancilla qubits and colors. The colors are mapped as $|00\rangle$, $|01\rangle$, and $|10\rangle$ for colors 0, 1, and 2 respectively

We can show that superposition of $(|00\rangle + |11\rangle + |22\rangle )/\sqrt{3}$ are for no edges connected; superposition of $(|01\rangle + |10\rangle )/\sqrt{2}$ for 0 and 1 connected and likewise for 0,2 and 1,2; superposition of $(|01\rangle + |10\rangle + |02\rangle + |20\rangle )/\sqrt{4}$ for edges between 0,1 and 0,2 and likewise for 1,2 and 1,0 and also 1,2 and 0,2. Lastly, we have superposition of the states $(|01\rangle + |10\rangle + |02\rangle + |20\rangle + |12\rangle ) + |21\rangle )/\sqrt{6}$ for all the three edges connected between the three vertices. We now map the two-qutrit system to four-qubit system changing $|00\rangle$ to $|0000\rangle$, $|01\rangle$ to $|0001\rangle$, etc., where the first two qubits denote each of the first qutrit and second two qubits denote the each of the second qutrit. This will help us in producing outputs in terms of binary and quantum computer readable language. In Fig. 4, there are eight circuits for each case where we output the vertex combinations and thus the graph state.

In Fig. 5, we show the connection between the vertices and the ancilla qubits. For the circuit, we use each of the first two qubits of the six for vertices (namely 0,1 and 0,2 and 1,2) edges joining these vertices are denoted by $|\psi _{01}\rangle$ and $|\psi _{02}\rangle$ and $|\psi _{12}\rangle$. For an edge connected, the user puts an X gate in the second qubit of the edges to specify the connection. The next three qubits are the ancilla qubits which remains $|0\rangle$ for no edges connected and changes to $|1\rangle$ for an edge connected. They denote the connection between given two vertices. The connection between the ancilla qubits and the vertex coloring is shown in Fig. 6. According to the given connection, we color the vertices 0, 1 and 2: each representing a different color. We again map 0, 1 and 2 to two-qubit system to show the colors of each vertex hierarchically.

For d number of vertices and for all the vertices connected, the maximum number of colors used is d. Thus, we need a qudit system which when mapped to a corresponding qubit system can give all the possible color combination for all the cases if the circuits are built for each case based on that showed for 3-coloring.

3.2 Quantum Cost

According to the input, circuit in Fig. 5 connects with one of the circuits from Fig. 4 showing the graph state. The circuit of Fig. 5 also connects with the circuit of Fig. 6 to show the respective coloring of the vertices. For example, for no edges connected, Fig. 5 is combined with Figs. 4a and 6; (Table 2).

Table 2 Quantum costs according to given figures

3.3 Classical Complexity

The adjacency matrix with space complexity O($n^{2}$) is required to denote connections between vertices. Actions like finding an edge between two given vertices or an edge removal can be done in constant time. The greedy algorithm requires O($V^{2}+E$) time complexity in the worst case.

4 Trees

In the previous sections, we denoted graph states as superposition of vertices and showed corresponding graph state’s vertices’ coloring. We now extend our coloring algorithms to trees as 2 colorable bipartite graphs. In graph theory, trees have only one connection between any two vertices. Each vertex can have zero to many children vertices. We use this property of one connection between parent and child vertices as a logical qubit. The connection is changed to $|{1}\rangle$ via an X gate if a connection is present. The circuit is developed with the vertices initially and then their corresponding connections. The vertices output their colors. Since only 2 colors are applicable, we either have $|{0}\rangle$ or $|{1}\rangle$ as outputs. For our paper, we assume a given tree in Fig. 7 and show its corresponding quantum circuit in Fig. 10. This circuit can be used as a reference for a tree with n vertices with given connections (Fig. 8).

Fig. 7

Representation of a tree: a given tree

Fig. 8

Quantum circuit for the given tree: Vertices and connections are shown. The vertices output their colors

4.1 Quantum Cost

Counting each connection between each parent and child, let us assume we have c connections for a tree of n vertices. We can calculate the quantum cost as $18c+c+1= 19c+1$. Also, we can calculate the cost as $18(n-1)+1+c= 18n+c-17$. For fig, our cost is 96.

4.2 Classical Complexity

We determine a bipartite graph and color it with 2 colors by computing breadth first traversal (BFT) or depth first traversal (DFT). This is done in linear time complexity.

5 Binary Trees

Binary trees are a special form of trees where every parent vertex has exactly two children vertices. We now present a circuit specifically for binary trees. Here we do not denote connections as starting from the root vertex, every parent–children connection is previously known. In our paper, we assume a given binary tree shown in Fig. 9 and show its quantum circuit for outputting colors in Fig. 10. This reference circuit can be extended to n vertices.

Fig. 9

Representation of a binary tree: a given binary tree

Fig. 10

Quantum circuit for the given binary tree: Vertices output their corresponding colors

5.1 Quantum Cost

For a binary tree of n vertices, the quantum cost corresponding to Fig. 10 can be calculated as $3n+1$. For our circuit in Fig. 9 with 7 vertices, the quantum cost is 19.

5.2 Classical Complexity

Binary trees take O(n) to color its vertices.

6 Conclusion

To conclude, we have designed quantum circuits for the graph states through superposition for each of 2 vertices and 3 vertices. We have also shown the possible colors of the vertices according to the chromatic number. W have also shown circuits for coloring trees. We have also specified a circuit specially for binary trees. We have mentioned the quantum cost of our circuits and mentioned the space–time complexity for the corresponding classical algorithms. Our algorithm proposes a pattern for d-coloring using a qudit system, where the qudit system can be mapped into a qubit system and appropriate quantum circuits can be designed, and thus, graph coloring can be achieved. The approach used here can be used in applications such as solving Sudoku [26, 27], setting time table [28], and coloring of maps.