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

International Conference on Computing, Communication, Perception and Quantum Technology (CCPQT)

A Graph Isomorphism Algorithm based on Continuous-Time Quantum Walks

Zhan Li, Yang Wang, Xiaogang Qiang

Published Aug 4, 2023• 2 citations
Publisher

Abstract

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.

DOI
10.1109/ccpqt60491.2023.00010

Related papers

Alternated two-particle discrete-time quantum walk on arbitrary graphs and its application on graph isomorphism testing

Panlong Li, Dan Li, Yuqian Zhou +2 more

Abstract This paper introduces a novel alternated two-particle discrete-time quantum walk model on arbitrary graphs, overcoming the limitation that conventional shared coin schemes are confined to regular graphs. By employing a fixed-dimension coin operator and encoding the graph structural information into the shift operator, the new model becomes applicable to arbitrary graphs. Further, by adding interaction between the two particles, an extension is presented, which can enhance the model’s dynamic properties and facilitate more intricate quantum interference phenomena. Based on the new model, a kind of quantum graph isomorphism algorithm framework is proposed. It just need O(N 0.5*∣E∣) steps of quantum walk and O(N 2) dimensions of Hilbert space, which offers a significant reduction in complexity compared to other quantum walk based algorithms. The graph isomorphism testing is performed in the framework using non-interacting and interacting quantum walks respectively. Experimental results illustrate that the algorithm based on interacting particles achieves a 100% success rate in discriminating all test graphs. While the algorithm with non-interacting particles performs a 100% distinction success rate on general non-regular graphs, albeit being ineffective on strongly regular graphs. Due to the effectiveness of the algorithm on arbitrary graphs, the algorithm has broad application prospects in the identification and comparison of chemical molecular structures, the analysis of social networks and so on.

Physica Scripta•Feb 7, 2025•0 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

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

A Quantum-Inspired Algorithm for Graph Isomorphism

Innes L. Maxwell, Stefan N. van den Hoven, Jelmer J. Renema

The Noisy Intermediate-Scale Quantum (NISQ) era of technology in which we currently find ourselves is defined by non-universality, susceptibility to errors and noise, and a search for useful applications. While demonstrations of practical quantum advantage remain elusive in this era, it provides space to develop and analyze the advantages and limitations of systems and their ability to solve problems. In this work, we critically assess a proposed quantum algorithm for the graph isomorphism problem, implemented on a photonic quantum device. Inspired by the nature of this quantum algorithm, we formulate a necessary condition for the isomorphism of graphs encoded in Gaussian boson samplers and a classical algorithm to test for it. Our classical algorithm makes use of efficiently computable statistical properties of a quantum sampling system to show a pair of graphs fail to meet our necessary condition and thus cannot be isomorphic. We analyze our algorithm in the context of the inspiring, sampler-based quantum algorithm of Bràdler et. al., the classical color refinement algorithm, and the state-of-the-art quasi-polynomial Babai algorithm.

quant-pharXiv:2512.24423•Jan 1, 2026•0 citations

Algorithms for finding the maximum clique based on continuous time quantum walks

Xi Li, Mingyou Wu, Hanwu Chen +1 more

In this work, the application of continuous time quantum walks (CTQW) to the Maximum Clique (MC) problem was studied. Performing CTQW on graphs can generate distinct periodic probability amplitudes for different vertices. We found that the intensities of the probability amplitudes at some frequencies imply the clique structure of special kinds of graphs. Recursive algorithms with time complexity O(N^6) in classical computers were proposed to determine the maximum clique. We have experimented on random graphs where each edge exists with different probabilities. Although counter examples were not found for random graphs, whether these algorithms are universal is beyond the scope of this work.

Quantum Information and Computation•Feb 1, 2021•2 citations

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
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.
Abstract This paper introduces a novel alternated two-particle discrete-time quantum walk model on arbitrary graphs, overcoming the limitation that conventional shared coin schemes are confined to regular graphs. By employing a fixed-dimension coin operator and encoding the graph structural information into the shift operator, the new model becomes applicable to arbitrary graphs. Further, by adding interaction between the two particles, an extension is presented, which can enhance the model’s dynamic properties and facilitate more intricate quantum interference phenomena. Based on the new model, a kind of quantum graph isomorphism algorithm framework is proposed. It just need O(N 0.5*∣E∣) steps of quantum walk and O(N 2) dimensions of Hilbert space, which offers a significant reduction in complexity compared to other quantum walk based algorithms. The graph isomorphism testing is performed in the framework using non-interacting and interacting quantum walks respectively. Experimental results illustrate that the algorithm based on interacting particles achieves a 100% success rate in discriminating all test graphs. While the algorithm with non-interacting particles performs a 100% distinction success rate on general non-regular graphs, albeit being ineffective on strongly regular graphs. Due to the effectiveness of the algorithm on arbitrary graphs, the algorithm has broad application prospects in the identification and comparison of chemical molecular structures, the analysis of social networks and so on.
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.
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 Noisy Intermediate-Scale Quantum (NISQ) era of technology in which we currently find ourselves is defined by non-universality, susceptibility to errors and noise, and a search for useful applications. While demonstrations of practical quantum advantage remain elusive in this era, it provides space to develop and analyze the advantages and limitations of systems and their ability to solve problems. In this work, we critically assess a proposed quantum algorithm for the graph isomorphism problem, implemented on a photonic quantum device. Inspired by the nature of this quantum algorithm, we formulate a necessary condition for the isomorphism of graphs encoded in Gaussian boson samplers and a classical algorithm to test for it. Our classical algorithm makes use of efficiently computable statistical properties of a quantum sampling system to show a pair of graphs fail to meet our necessary condition and thus cannot be isomorphic. We analyze our algorithm in the context of the inspiring, sampler-based quantum algorithm of Bràdler et. al., the classical color refinement algorithm, and the state-of-the-art quasi-polynomial Babai algorithm.
In this work, the application of continuous time quantum walks (CTQW) to the Maximum Clique (MC) problem was studied. Performing CTQW on graphs can generate distinct periodic probability amplitudes for different vertices. We found that the intensities of the probability amplitudes at some frequencies imply the clique structure of special kinds of graphs. Recursive algorithms with time complexity O(N^6) in classical computers were proposed to determine the maximum clique. We have experimented on random graphs where each edge exists with different probabilities. Although counter examples were not found for random graphs, whether these algorithms are universal is beyond the scope of this 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).