Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1304.5773 · Physical Review A

Graph isomorphism and adiabatic quantum computing

Frank Gaitan, Lane Clark

Published Feb 28, 2014• 46 citations
arXivHTMLPDF

Abstract

In the graph isomorphism (GI) problem two $N$-vertex graphs $G$ and ${G}^{\ensuremath{'}}$ are given and the task is to determine whether there exists a permutation of the vertices of $G$ that preserves adjacency and transforms $G\ensuremath{\rightarrow}{G}^{\ensuremath{'}}$. If yes, then $G$ and ${G}^{\ensuremath{'}}$ 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 $\ensuremath{\Delta}(N)$ separating the ground and first-excited states in the limit of large problem size $N\ensuremath{\gg}1$. Calculating $\ensuremath{\Delta}(N)$ 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.

DOI
10.1103/physreva.89.022342

Related papers

The quantum algorithm for graph isomorphism problem

Xi Li, Hanwu Chen

The graph isomorphism (GI) problem is the computational problem of finding a permutation of vertices of a given graph $G_1$ that transforms $G_1$ to another given graph $G_2$ and preserves the adjacency. In this work, we propose a quantum algorithm to determine whether there exists such a permutation. To find such a permutation, we introduce isomorphic equivalent graphs of the given graphs to be tested. We proof that the GI problem of the equivalent graphs is equivalent to the GI problem of the given graphs. The idea of the algorithm is to determine whether there exists a permutation can transform the eigenvectors of the adjacency matrix of the equivalent graphs each other. The cost time of the algorithm is polynomial.

arXiv:1901.06530•Jan 19, 2019•3 citations

Computational Complexity of Graph Isomorphism with Quantum Algorithms

Jincheng Zhang

Graph isomorphism, the problem of determining whether two graphs are structurally identical despite potentially differing node labels and edge orientations, is a fundamental problem in computer science and theoretical mathematics. This paper investigates the potential for quantum algorithms, specifically leveraging Grover's algorithm, to improve the efficiency of graph isomorphism testing. We explore the theoretical complexity of this problem on a quantum computer, analyzing the impact of graph structure and algorithm parameters. The core claim is that determining graph isomorphism remains a computationally challenging problem, even with quantum acceleration. We delve into the limitations imposed by the problem's inherent complexity and the practical hurdles involved in implementing quantum algorithms for this task. The analysis focuses on the search space reduction offered by Grover's algorithm and its interaction with the graph's topology. We examine the factors that contribute to the algorithm's effectiveness, including graph size, connectivity, and the number of possible graph configurations. Ultimately, this work contributes to a deeper understanding of the computational challenges associated with graph isomorphism and provides insights into the potential and limitations of quantum computing in tackling this problem.

•Sep 2, 2026•0 citations

Physically-motivated dynamical algorithms for the graph isomorphism problem

Shiue-Yuan Shiau, Robert Joynt, S. N. Coppersmith

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.

Quantum Information and Computation•Sep 1, 2005•34 citations

Quantum Algorithms for Tree Isomorphism and State Symmetrization

David J. Rosenbaum

The graph isomorphism problem is theoretically interesting and also has many practical applications. The best known classical algorithms for graph isomorphism all run in time super-polynomial in the size of the graph in the worst case. An interesting open problem is whether quantum computers can solve the graph isomorphism problem in polynomial time. In this paper, an algorithm is shown which can decide if two rooted trees are isomorphic in polynomial time. Although this problem is easy to solve efficiently on a classical computer, the techniques developed may be useful as a basis for quantum algorithms for deciding isomorphism of more interesting types of graphs. The related problem of quantum state symmetrization is also studied. A polynomial time algorithm for the problem of symmetrizing a set of orthonormal states over an arbitrary permutation group is shown.

arXiv:1011.4138•Nov 18, 2010•2 citations

Testing graph isomorphism using simple quantum circuits

Samuel Beasley, Ashley Montanaro

The graph isomorphism problem asks whether two graphs are equivalent up to a permutation of their vertices. Its precise computational complexity remains unresolved, and it is still unknown whether a polynomial-time algorithm exists. We investigate whether simple graph-dependent Instantaneous Quantum Polynomial-time (IQP) and Quantum Approximate Optimisation Algorithm (QAOA) circuits can distinguish non-isomorphic graphs. We first show that suitable IQP and QAOA constructions allow the underlying graph to be reconstructed using a polynomial number of samples. Building on previous work using the QAOA energy, we show that Hamming weight distributions can distinguish graph pairs at circuit depths for which the numerically computed energy gap is zero. We then apply graph invariants to the matrix of ZZ correlators on the output distribution. For the specific case of the graph spectrum, at QAOA depth $p=2$, this invariant numerically distinguishes all $10{,}486$ cospectral regular graph pairs tested on up to 18 vertices. For IQP circuits, we introduce a finer invariant based on probability multiplicities within Hamming weight sectors, which distinguishes every non-isomorphic graph pair tested numerically. Finally, we derive exact graph-theoretic characterisations of the IQP output distribution at $θ=π/2$ and $θ=π/4$. These results show that simple graph-dependent quantum circuits encode substantial structural information, while leaving open whether this information can be extracted efficiently for general graph isomorphism.

quant-pharXiv:2610.19962•Oct 15, 2026•0 citations

A quantum-walk-inspired adiabatic algorithm for solving graph isomorphism problems

Dario Tamascelli, Luca Zanetti

We present a quantum algorithm for solving graph isomorphism problems that is based on an adiabatic protocol. We use a collection of continuous time quantum walks, each one generated by an XY Hamiltonian, to visit the configuration space. In this way we avoid a diffusion over all the possible configurations and significantly reduce the dimensionality of the accessible Hilbert space. Within this restricted space, the graph isomorphism problem can be translated into searching for a satisfying assignment to a 2-SAT (satisfiable) formula and mapped onto a 2-local Hamiltonian without resorting to perturbation gadgets or projective techniques. We present an analysis of the time for execution of the algorithm on small graph isomorphism problem instances and discuss the issue of an implementation of the proposed adiabatic scheme on current quantum computing hardware.

arXiv:1401.1278•Journal of Physics A Mathematical and Theoretical•Jul 24, 2014•32 citations
In the graph isomorphism (GI) problem two NNN-vertex graphs GGG and G\ensuremath′{G}^{\ensuremath{'}}G\ensuremath′ are given and the task is to determine whether there exists a permutation of the vertices of GGG that preserves adjacency and transforms G\ensuremath→G\ensuremath′G\ensuremath{\rightarrow}{G}^{\ensuremath{'}}G\ensuremath→G\ensuremath′. If yes, then GGG and G\ensuremath′{G}^{\ensuremath{'}}G\ensuremath′ 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 GGG. 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 \ensuremathΔ(N)\ensuremath{\Delta}(N)\ensuremathΔ(N) separating the ground and first-excited states in the limit of large problem size N\ensuremath≫1N\ensuremath{\gg}1N\ensuremath≫1. Calculating \ensuremathΔ(N)\ensuremath{\Delta}(N)\ensuremathΔ(N) 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.
The graph isomorphism (GI) problem is the computational problem of finding a permutation of vertices of a given graph G1G_1G1​ that transforms G1G_1G1​ to another given graph G2G_2G2​ and preserves the adjacency. In this work, we propose a quantum algorithm to determine whether there exists such a permutation. To find such a permutation, we introduce isomorphic equivalent graphs of the given graphs to be tested. We proof that the GI problem of the equivalent graphs is equivalent to the GI problem of the given graphs. The idea of the algorithm is to determine whether there exists a permutation can transform the eigenvectors of the adjacency matrix of the equivalent graphs each other. The cost time of the algorithm is polynomial.
Graph isomorphism, the problem of determining whether two graphs are structurally identical despite potentially differing node labels and edge orientations, is a fundamental problem in computer science and theoretical mathematics. This paper investigates the potential for quantum algorithms, specifically leveraging Grover's algorithm, to improve the efficiency of graph isomorphism testing. We explore the theoretical complexity of this problem on a quantum computer, analyzing the impact of graph structure and algorithm parameters. The core claim is that determining graph isomorphism remains a computationally challenging problem, even with quantum acceleration. We delve into the limitations imposed by the problem's inherent complexity and the practical hurdles involved in implementing quantum algorithms for this task. The analysis focuses on the search space reduction offered by Grover's algorithm and its interaction with the graph's topology. We examine the factors that contribute to the algorithm's effectiveness, including graph size, connectivity, and the number of possible graph configurations. Ultimately, this work contributes to a deeper understanding of the computational challenges associated with graph isomorphism and provides insights into the potential and limitations of quantum computing in tackling this problem.
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.
The graph isomorphism problem is theoretically interesting and also has many practical applications. The best known classical algorithms for graph isomorphism all run in time super-polynomial in the size of the graph in the worst case. An interesting open problem is whether quantum computers can solve the graph isomorphism problem in polynomial time. In this paper, an algorithm is shown which can decide if two rooted trees are isomorphic in polynomial time. Although this problem is easy to solve efficiently on a classical computer, the techniques developed may be useful as a basis for quantum algorithms for deciding isomorphism of more interesting types of graphs. The related problem of quantum state symmetrization is also studied. A polynomial time algorithm for the problem of symmetrizing a set of orthonormal states over an arbitrary permutation group is shown.
The graph isomorphism problem asks whether two graphs are equivalent up to a permutation of their vertices. Its precise computational complexity remains unresolved, and it is still unknown whether a polynomial-time algorithm exists. We investigate whether simple graph-dependent Instantaneous Quantum Polynomial-time (IQP) and Quantum Approximate Optimisation Algorithm (QAOA) circuits can distinguish non-isomorphic graphs. We first show that suitable IQP and QAOA constructions allow the underlying graph to be reconstructed using a polynomial number of samples. Building on previous work using the QAOA energy, we show that Hamming weight distributions can distinguish graph pairs at circuit depths for which the numerically computed energy gap is zero. We then apply graph invariants to the matrix of ZZ correlators on the output distribution. For the specific case of the graph spectrum, at QAOA depth p=2p=2p=2, this invariant numerically distinguishes all 10,48610{,}48610,486 cospectral regular graph pairs tested on up to 18 vertices. For IQP circuits, we introduce a finer invariant based on probability multiplicities within Hamming weight sectors, which distinguishes every non-isomorphic graph pair tested numerically. Finally, we derive exact graph-theoretic characterisations of the IQP output distribution at θ=π/2θ=π/2θ=π/2 and θ=π/4θ=π/4θ=π/4. These results show that simple graph-dependent quantum circuits encode substantial structural information, while leaving open whether this information can be extracted efficiently for general graph isomorphism.
We present a quantum algorithm for solving graph isomorphism problems that is based on an adiabatic protocol. We use a collection of continuous time quantum walks, each one generated by an XY Hamiltonian, to visit the configuration space. In this way we avoid a diffusion over all the possible configurations and significantly reduce the dimensionality of the accessible Hilbert space. Within this restricted space, the graph isomorphism problem can be translated into searching for a satisfying assignment to a 2-SAT (satisfiable) formula and mapped onto a 2-local Hamiltonian without resorting to perturbation gadgets or projective techniques. We present an analysis of the time for execution of the algorithm on small graph isomorphism problem instances and discuss the issue of an implementation of the proposed adiabatic scheme on current quantum computing hardware.