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

Journal of Physics A Mathematical and Theoretical

A graph isomorphism algorithm using signatures computed via quantum walk search model

Huiquan Wang, Junjie Wu, Xuejun Yang, Xun Yi

Published Feb 20, 2015• 13 citations
Publisher

Abstract

In this paper, we propose a new algorithm based on a quantum walk search model to distinguish strongly similar graphs. Our algorithm computes a signature for each graph via the quantum walk search model and uses signatures to distinguish non-isomorphic graphs. Our method is less complex than those of previous works. In addition, our algorithm can be extended by raising the signature levels. The higher the level adopted, the stronger the distinguishing ability and the higher the complexity of the algorithm. Our algorithm was tested with standard benchmarks from four databases. We note that the weakest signature at level 1 can distinguish all similar graphs, with a time complexity of which that outperforms the previous best work except when it comes to strongly regular graphs (SRGs). Once the signature is raised to level 3, all SRGs tested can be distinguished successfully. In this case, the time complexity is , also better than the previous best work.

DOI
10.1088/1751-8113/48/11/115302

Related papers

Multiparticle quantum walks for distinguishing hard graphs

Sachin Kasture, Shaheen Acheche, Loïc Henriet +1 more

Quantum random walks have been shown to be powerful quantum algorithms for certain tasks on graphs like database searching, quantum simulations etc. In this work we focus on its applications for the graph isomorphism problem. In particular we look at how we can compare multi-particle quantum walks and well known classical WL tests and how quantum walks can be used to distinguish hard graphs like CFI graphs which k-WL tests cannot distinguish. We provide theoretical proofs and empirical results to show that a k-QW with input superposition states distinguishes k-CFI graphs. In addition we also prove that a k-1 QW with localized input states distinguishes k-CFI graphs. We also prove some additional results about strongly regular graphs (SRGs).

arXiv:2501.03683•Jan 7, 2025•0 citations

Comparing Algorithms for Graph Isomorphism Using Discrete- and Continuous-Time Quantum Random Walks

Kenneth Rudinger, John King Gamble, Eric Bach +3 more

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.

arXiv:1207.4535•Journal of Computational and Theoretical Nanoscience•Jun 20, 2013•19 citations

Two-particle quantum walks applied to the graph isomorphism problem

John King Gamble, Mark G. Friesen, Dong Zhou +2 more

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.

arXiv:1002.3003•Physical Review A•May 13, 2010•145 citations

An enhanced classical approach to graph isomorphism using continuous-time quantum walk

Xiaogang Qiang, Xuejun Yang, Junjie Wu +1 more

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.

Journal of Physics A Mathematical and Theoretical•Jan 4, 2012•23 citations

A Graph Isomorphism Algorithm based on Continuous-Time Quantum Walks

Zhan Li, Yang Wang, Xiaogang Qiang

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.

International Conference on Computing, Communication, Perception and Quantum Technology (CCPQT)•Aug 4, 2023•2 citations

Quantum Algorithms for Approximate Graph Isomorphism Testing

Prateek P. Kulkarni

The graph isomorphism problem asks whether two graphs are identical up to vertex relabeling. While the exact problem admits quasi-polynomial-time classical algorithms, many applications in molecular comparison, noisy network analysis, and pattern recognition require a flexible notion of structural similarity. We study the quantum query complexity of approximate graph isomorphism testing, where two graphs on $n$ vertices drawn from the Erdős--Rényi distribution $\mathcal{G} (n,1/2)$ are considered approximately isomorphic if they can be made isomorphic by at most $k$ edge edits. We present a quantum algorithm based on MNRS quantum walk search over the product graph $Γ(G,H)$ of the two input graphs. When the graphs are approximately isomorphic, the quantum walk search detects vertex pairs belonging to a dense near isomorphic matching set; candidate pairings are then reconstructed via local consistency propagation and verified via a Grover-accelerated consistency check. We prove that this approach achieves query complexity $\mathcal{O}(n^{3/2} \log n/\varepsilon)$, where $\varepsilon$ parameterizes the approximation threshold. We complement this with an $Ω(n^2)$ classical lower bound for constant approximation, establishing a genuine polynomial quantum speedup in the query model. We extend the framework to spectral similarity measures based on graph Laplacian eigenvalues, as well as weighted and attributed graphs. Small-scale simulation results on quantum simulators for graphs with up to twenty vertices demonstrate compatibility with near-term quantum devices.

quant-pharXiv:2603.02656•Mar 4, 2026•0 citations
In this paper, we propose a new algorithm based on a quantum walk search model to distinguish strongly similar graphs. Our algorithm computes a signature for each graph via the quantum walk search model and uses signatures to distinguish non-isomorphic graphs. Our method is less complex than those of previous works. In addition, our algorithm can be extended by raising the signature levels. The higher the level adopted, the stronger the distinguishing ability and the higher the complexity of the algorithm. Our algorithm was tested with standard benchmarks from four databases. We note that the weakest signature at level 1 can distinguish all similar graphs, with a time complexity of which that outperforms the previous best work except when it comes to strongly regular graphs (SRGs). Once the signature is raised to level 3, all SRGs tested can be distinguished successfully. In this case, the time complexity is , also better than the previous best work.
Quantum random walks have been shown to be powerful quantum algorithms for certain tasks on graphs like database searching, quantum simulations etc. In this work we focus on its applications for the graph isomorphism problem. In particular we look at how we can compare multi-particle quantum walks and well known classical WL tests and how quantum walks can be used to distinguish hard graphs like CFI graphs which k-WL tests cannot distinguish. We provide theoretical proofs and empirical results to show that a k-QW with input superposition states distinguishes k-CFI graphs. In addition we also prove that a k-1 QW with localized input states distinguishes k-CFI graphs. We also prove some additional results about strongly regular graphs (SRGs).
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.
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.
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.
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.
The graph isomorphism problem asks whether two graphs are identical up to vertex relabeling. While the exact problem admits quasi-polynomial-time classical algorithms, many applications in molecular comparison, noisy network analysis, and pattern recognition require a flexible notion of structural similarity. We study the quantum query complexity of approximate graph isomorphism testing, where two graphs on nnn vertices drawn from the Erdős--Rényi distribution G(n,1/2)\mathcal{G} (n,1/2)G(n,1/2) are considered approximately isomorphic if they can be made isomorphic by at most kkk edge edits. We present a quantum algorithm based on MNRS quantum walk search over the product graph Γ(G,H)Γ(G,H)Γ(G,H) of the two input graphs. When the graphs are approximately isomorphic, the quantum walk search detects vertex pairs belonging to a dense near isomorphic matching set; candidate pairings are then reconstructed via local consistency propagation and verified via a Grover-accelerated consistency check. We prove that this approach achieves query complexity O(n3/2log⁡n/ε)\mathcal{O}(n^{3/2} \log n/\varepsilon)O(n3/2logn/ε), where ε\varepsilonε parameterizes the approximation threshold. We complement this with an Ω(n2)Ω(n^2)Ω(n2) classical lower bound for constant approximation, establishing a genuine polynomial quantum speedup in the query model. We extend the framework to spectral similarity measures based on graph Laplacian eigenvalues, as well as weighted and attributed graphs. Small-scale simulation results on quantum simulators for graphs with up to twenty vertices demonstrate compatibility with near-term quantum devices.