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

Physica Scripta

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

Panlong Li, Dan Li, Yuqian Zhou, Bojia Duan, Yu‐Guang Yang

Published Feb 7, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.1088/1402-4896/adaf7e

Related papers

Two-particle quantum walks: Entanglement and graph isomorphism testing

Scott M. Berry, Jingbo B. Wang

We study discrete-time quantum walks on the line and on general undirected graphs with two interacting or noninteracting particles. We introduce two simple interaction schemes and show that they both lead to a diverse range of probability distributions that depend on the correlations and relative phases between the initial coin states of the two particles. We investigate the characteristics of these quantum walks and the time evolution of the entanglement between the two particles from both separable and entangled initial states. We also test the capability of two-particle discrete-time quantum walks to distinguish nonisomorphic graphs. For strongly regular graphs, we show that noninteracting discrete-time quantum walks can distinguish some but not all nonisomorphic graphs with the same family parameters. By incorporating an interaction between the two particles, all nonisomorphic strongly regular graphs tested are successfully distinguished.

Physical Review A•Apr 14, 2011•155 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

MapEff: An Effective Graph Isomorphism Agorithm Based on the Discrete-Time Quantum Walk

Kai Liu, Yi Zhang, Kai Lü +3 more

Graph isomorphism is to determine whether two graphs have the same topological structure. It plays a significant role in areas of image matching, biochemistry, and information retrieval. Quantum walk, as a novel quantum computation model, has been employed to isomorphic mapping detection to optimize the time complexity compared with a classical computation model. However, these quantum-inspired algorithms do not perform well-and even cease to work-for graphs with inherent symmetry, such as regular graphs. By analyzing the impacts of graphs symmetry on isomorphism detection, we proposed an effective graph isomorphism algorithm (MapEff) based on the discrete-time quantum walk (DTQW) to improve the accuracy of isomorphic mapping detection, especially for regular graphs. With the help of auxiliary edges, this algorithm can distinguish the symmetric nodes efficiently and, thus, deduct the qualified isomorphic mapping by rounds of selections. The experiments tested on 1585 pairs of graphs demonstrated that our algorithm has a better performance compared with other state-of-the-art algorithms.

Entropy•Jun 5, 2019•6 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•28 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•24 citations

A hybrid quantum walk model unifying discrete and continuous quantum walks

Tianen Chen, Yun Shang

Quantum walks, both discrete and continuous, serve as fundamental tools in quantum information processing with diverse applications. This work introduces a hybrid quantum walk model that integrates the coin mechanism of discrete walks with the Hamiltonian-driven time evolution of continuous walks. Through systematic analysis of probability distributions, standard deviations, and entanglement entropy on fundamental graph structures, we reveal distinctive dynamical characteristics that differentiate our model from conventional quantum walk paradigms. The proposed framework demonstrates unifying capabilities by naturally encompassing existing quantum walk models as special cases. Two significant applications emerge from this hybrid architecture: (1) We develop a novel protocol for perfect state transfer(PST) in general connected graphs, overcoming the limitations of previous graph-specific approaches. A PST on a tree graph has been implemented on a quantum superconducting processor. (2) We devise a quantum algorithm for multiplying K adjacency matrices of n -vertex regular graphs with time complexity O ( n 2 d 1 ⋯ d K ), outperforming classical matrix multiplication ( O ( n 2.371552 )) when vertex degrees d i are bounded. The algorithm’s efficacy for triangle counting is experimentally validated through the quantum simulation on PennyLane. These results establish the hybrid quantum walk as a versatile framework bridging discrete and continuous paradigms while enabling practical quantum advantage in graph computation tasks.

arXiv:2509.09221•npj Quantum Information•Dec 30, 2025•3 citations
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.
We study discrete-time quantum walks on the line and on general undirected graphs with two interacting or noninteracting particles. We introduce two simple interaction schemes and show that they both lead to a diverse range of probability distributions that depend on the correlations and relative phases between the initial coin states of the two particles. We investigate the characteristics of these quantum walks and the time evolution of the entanglement between the two particles from both separable and entangled initial states. We also test the capability of two-particle discrete-time quantum walks to distinguish nonisomorphic graphs. For strongly regular graphs, we show that noninteracting discrete-time quantum walks can distinguish some but not all nonisomorphic graphs with the same family parameters. By incorporating an interaction between the two particles, all nonisomorphic strongly regular graphs tested are successfully distinguished.
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.
Graph isomorphism is to determine whether two graphs have the same topological structure. It plays a significant role in areas of image matching, biochemistry, and information retrieval. Quantum walk, as a novel quantum computation model, has been employed to isomorphic mapping detection to optimize the time complexity compared with a classical computation model. However, these quantum-inspired algorithms do not perform well-and even cease to work-for graphs with inherent symmetry, such as regular graphs. By analyzing the impacts of graphs symmetry on isomorphism detection, we proposed an effective graph isomorphism algorithm (MapEff) based on the discrete-time quantum walk (DTQW) to improve the accuracy of isomorphic mapping detection, especially for regular graphs. With the help of auxiliary edges, this algorithm can distinguish the symmetric nodes efficiently and, thus, deduct the qualified isomorphic mapping by rounds of selections. The experiments tested on 1585 pairs of graphs demonstrated that our algorithm has a better performance compared with other state-of-the-art algorithms.
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.
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.
Quantum walks, both discrete and continuous, serve as fundamental tools in quantum information processing with diverse applications. This work introduces a hybrid quantum walk model that integrates the coin mechanism of discrete walks with the Hamiltonian-driven time evolution of continuous walks. Through systematic analysis of probability distributions, standard deviations, and entanglement entropy on fundamental graph structures, we reveal distinctive dynamical characteristics that differentiate our model from conventional quantum walk paradigms. The proposed framework demonstrates unifying capabilities by naturally encompassing existing quantum walk models as special cases. Two significant applications emerge from this hybrid architecture: (1) We develop a novel protocol for perfect state transfer(PST) in general connected graphs, overcoming the limitations of previous graph-specific approaches. A PST on a tree graph has been implemented on a quantum superconducting processor. (2) We devise a quantum algorithm for multiplying K adjacency matrices of n -vertex regular graphs with time complexity O ( n 2 d 1 ⋯ d K ), outperforming classical matrix multiplication ( O ( n 2.371552 )) when vertex degrees d i are bounded. The algorithm’s efficacy for triangle counting is experimentally validated through the quantum simulation on PennyLane. These results establish the hybrid quantum walk as a versatile framework bridging discrete and continuous paradigms while enabling practical quantum advantage in graph computation tasks.