We investigate classical and quantum physics-based algorithms for solving the graph isomorphism problem. Our work integrates and extends previous work by Gudkov et al. (cond-mat/0209112) and by Rudolph (quant-ph/0206068). Gudkov et al. propose an algorithm intended to solve the graph isomorphism problem in polynomial time by mimicking a classical dynamical many-particle process. We show that this algorithm fails to distinguish pairs of non-isomorphic strongly regular graphs, thus providing an infinite class of counterexamples. We also show that the simplest quantum generalization of the algorithm also fails. However, by combining Gudkov et al.'s algorithm with a construction proposed by Rudoph in which one examines a graph describing the dynamics of two particles on the original graph, we find an algorithm that successfully distinguishes all pairs of non-isomorphic strongly regular graphs that we tested (with up to 29 vertices).
We investigate classical and quantum physics-based algorithms for solving the graph isomorphism problem. Our work integrates and extends previous work by Gudkov et al. (cond-mat/0209112) and by Rudolph (quant-ph/0206068). Gudkov et al. propose an algorithm intended to solve the graph isomorphism problem in polynomial time by mimicking a classical dynamical many-particle process. We show that this algorithm fails to distinguish pairs of non-isomorphic strongly regular graphs, thus providing an infinite class of counterexamples. We also show that the simplest quantum generalization of the algorithm also fails. However, by combining Gudkov et al.'s algorithm with a construction proposed by Rudoph in which one examines a graph describing the dynamics of two particles on the original graph, we find an algorithm that successfully distinguishes all pairs of non-isomorphic strongly regular graphs that we tested (with up to 29 vertices).
The graph isomorphism problem (GI) plays a central role in the theory of computational complexity and has importance in physics and chemistry as well \cite{kobler93,fortin96}. No polynomial-time algorithm for solving GI is known. We investigate classical and quantum physics-based polynomial-time algorithms for solving the graph isomorphism problem in which the graph structure is reflected in the behavior of a dynamical system. We show that a classical dynamical algorithm proposed by Gudkov and Nussinov \cite{gudkov02} as well as its simplest quantum generalization fail to distinguish pairs of non-isomorphic strongly regular graphs. However, by combining the algorithm of Gudkov and Nussinov with a construction proposed by Rudolph \cite{rudolph02} in which one examines a graph describing the dynamics of two particles on the original graph, we find an algorithm that successfully distinguishes all pairs of non-isomorphic strongly regular graphs that we tested with up to 29 vertices.
We show that the quantum dynamics of interacting and noninteracting quantum particles are fundamentally different in the context of solving a particular computational problem. Specifically, we consider the graph isomorphism problem, in which one wishes to determine whether two graphs are isomorphic (related to each other by a relabeling of the graph vertices), and focus on a class of graphs with particularly high symmetry called strongly regular graphs (SRGs). We study the Green's functions that characterize the dynamical evolution single-particle and two-particle quantum walks on pairs of nonisomorphic SRGs and show that interacting particles can distinguish nonisomorphic graphs that noninteracting particles cannot. We obtain the following specific results. (1) We prove that quantum walks of two noninteracting particles, fermions or bosons, cannot distinguish certain pairs of nonisomorphic SRGs. (2) We demonstrate numerically that two interacting bosons are more powerful than single particles and two noninteracting particles, in that quantum walks of interacting bosons distinguish all nonisomorphic pairs of SRGs that we examined. By utilizing high-throughput computing to perform over 500 million direct comparisons between evolution operators, we checked all tabulated pairs of nonisomorphic SRGs, including graphs with up to 64 vertices. (3) By performing a short-time expansion of the evolution operator, we derive distinguishing operators that provide analytic insight into the power of the interacting two-particle quantum walk.
Berry and Wang [Phys. Rev. A {\bf 83}, 042317 (2011)] show numerically that a discrete-time quantum random walk of two noninteracting particles is able to distinguish some non-isomorphic strongly regular graphs from the same family. Here we analytically demonstrate how it is possible for these walks to distinguish such graphs, while continuous-time quantum walks of two noninteracting particles cannot. We show analytically and numerically that even single-particle discrete-time quantum random walks can distinguish some strongly regular graphs, though not as many as two-particle noninteracting discrete-time walks. Additionally, we demonstrate how, given the same quantum random walk, subtle differences in the graph certificate construction algorithm can nontrivially impact the walk's distinguishing power. We also show that no continuous-time walk of a fixed number of particles can distinguish all strongly regular graphs when used in conjunction with any of the graph certificates we consider. We extend this constraint to discrete-time walks of fixed numbers of noninteracting particles for one kind of graph certificate; it remains an open question as to whether or not this constraint applies to the other graph certificates we consider.
Graph isomorphism is an essential problem in graph theory and widely used in a variety of applications. With graph size increasing, graph isomorphism become difficult for classical computation since there is no polynomial algorithm for general graphs yet. Considering the advantages of quantum computation over classical computation in various tasks, quantum graph isomorphism algorithms have been studied to explore the potentials of quantum computation in graph isomorphism. In this work, we propose a graph isomorphism algorithm based on continuous-time quantum walks, where we construct the graph certificates from the output probabilities of continuous-time quantum walks on the tested graphs with added self-loops to graph vertices, and distinguish graphs by comparing the graph certificates. Numerous tests on diverse graph classes demonstrate the effectiveness of the proposed GI algorithm, which is not limited to a specific topological structure graph. Moreover, we test the proposed algorithm on classes of strongly regular graphs, and the results show that the distinguishing ability of the algorithm can be improved with the increasement of the added self-loops to distinct vertices.
We investigate the quantum dynamics of particles on graphs (``quantum random walks''), with the aim of developing quantum algorithms for determining if two graphs are isomorphic (related to each other by a relabeling of vertices). We focus on quantum random walks of multiple noninteracting particles on strongly regular graphs (SRGs), a class of graphs with high symmetry that is known to have pairs of graphs that are hard to distinguish. Previous work has already demonstrated analytically that two-particle noninteracting quantum walks cannot distinguish nonisomorphic SRGs of the same family. Here, we demonstrate numerically that three-particle noninteracting quantum walks have significant, but not universal, distinguishing power for pairs of SRGs, proving a fundamental difference between the distinguishing power of two-particle and three-particle noninteracting walks. We show analytically why this distinguishing power is possible, whereas it is forbidden for two-particle noninteracting walks. Based on sampling of SRGs with up to 64 vertices, we find no difference in the distinguishing power of bosonic and fermionic walks. In addition, we find that the four-fermion noninteracting walk has greater distinguishing power than the three-particle walk on SRGs, showing that increasing the particle number increases the distinguishing power. However, we also show analytically that no noninteracting walk with a fixed number of particles can distinguish all SRGs, thus demonstrating a potential fundamental difference in the distinguishing power of interacting versus noninteracting walks.
Studies on graph isomorphism play an important role in graph research, and graph isomorphism algorithms have a wide range of applications in image matching, pattern recognition, computer vision, biochemistry and other fields. Previous research demonstrated that involving discrete-time quantum walk in the graph isomorphism algorithm could achieve complexity O ( N 7 ) for general graphs, since quantum walk could be utilized as a new toolbox for solving graph problems. We develop an enhanced classical approach to graph isomorphism using continuous-time quantum walk, which has lower complexity O ( N 5 ) and can effectively distinguish the graphs that are generally considered difficult. In addition, we define a graph similarity measure based on the proposed algorithm, which can be used for graph isomorphism and graph clustering. In the experiment, we test a wide variety of classes of graphs; the results show that the algorithm has a wide range of applications rather than being limited to a specific type of graph.