Graph isomorphism and adiabatic quantum computing

In the graph isomorphism (GI) problem two $N$-vertex graphs $G$ and $G^{\prime }$ are given and the task is to determine whether there exists a permutation of the vertices of $G$ that preserves adjacency and transforms $G\to G^{\prime }$. If yes, then $G$ and $G^{\prime }$ are said to be isomorphic; otherwise they are nonisomorphic. The GI problem is an important problem in computer science and is thought to be of comparable difficulty to integer factorization. In this paper we present a quantum algorithm that solves arbitrary instances of GI and which also provides an approach to determining all automorphisms of a given graph. We show how the GI problem can be converted to a combinatorial optimization problem that can be solved using adiabatic quantum evolution. We numerically simulate the algorithm's quantum dynamics and show that it correctly (i) distinguishes nonisomorphic graphs; (ii) recognizes isomorphic graphs and determines the permutation(s) that connect them; and (iii) finds the automorphism group of a given graph $G$. We then discuss the GI quantum algorithm's experimental implementation, and close by showing how it can be leveraged to give a quantum algorithm that solves arbitrary instances of the NP-complete subgraph isomorphism problem. The computational complexity of an adiabatic quantum algorithm is largely determined by the minimum energy gap $\Delta \left(N\right)$ separating the ground and first-excited states in the limit of large problem size $N\gg 1$. Calculating $\Delta \left(N\right)$ in this limit is a fundamental open problem in adiabatic quantum computing, and so it is not possible to determine the computational complexity of adiabatic quantum algorithms in general, nor consequently, of the specific adiabatic quantum algorithms presented here. Adiabatic quantum computing has been shown to be equivalent to the circuit model of quantum computing, and so development of adiabatic quantum algorithms continues to be of great interest.

Figure 1

Two nonisomorphic four-vertex graphs $G$ and $G^{\prime }$.

Figure 2

Two isomorphic four-vertex graphs $G$ and $G^{\prime }$.

Figure 3

Transformation of $G$ produced by the permutation ${\pi }_1$.

Figure 4

Two nonisomorphic five-vertex isospectral graphs $G$ and $G^{\prime }$.

Figure 5

Two nonisomorphic six-vertex isospectral graphs $G$ and $G^{\prime }$.

Figure 6

Two four-vertex nonisomorphic strongly regular graphs $G$ and $G^{\prime }$.

Figure 7

Two five-vertex nonisomorphic strongly regular graphs $G$ and $G^{\prime }$.

Figure 8

Two 6-vertex non-isomorphic strongly regular graphs $G$ and $G^{\prime }$.

Figure 9

Cycle graph $C_4$.

Figure 10

Transformation of $C_4$ produced by the permutation ${\pi }_{*}$.

Figure 11

Transformation of $C_4$ produced by the automorphism $\alpha$.

Figure 12

Transformation of $C_4$ produced by the automorphism $\beta$.

Figure 13

Cycle graph $C_5$.

Figure 14

Cycle graph $C_6$.

Figure 15

Cycle graph $C_7$.

Figure 16

Grid graph $G_{2,3}$.

Figure 17

Wheel graph $W_7$.

Figure 18

Layout of qubits and couplers for a D-Wave One processor. The processor architecture is a $4\times 4$ array of unit cells, with each unit cell containing eight qubits. Within a unit cell, each of the four qubits in the left-hand partition (LHP) connects to all four qubits in the right-hand partition (RHP), and vice versa. A qubit in the LHP (RHP) of a unit cell also connects to the corresponding qubit in the LHP (RHP) in the unit cells above and below (to the left and right of) it. Most qubits couple to six neighbors. Qubits are labeled from 1 to 128, and edges between qubits indicate couplers which may take programmable values. Gray qubits indicate usable qubits, while white qubits indicate qubits which, due to fabrication defects, could not be calibrated to operating tolerances and were not used.