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.
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.
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 n vertices drawn from the Erdős--Rényi distribution 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 O(n3/2logn/ε), where ε parameterizes the approximation threshold. We complement this with an Ω(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.
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.
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).
Abstract The problem of detecting communities in real-world networks has been extensively studied in the past, but most of the existing approaches work on single-domain networks, i.e. they consider only one type of relationship between nodes. Single-domain networks may contain noisy edges and they may lack some important information. Thus, some authors have proposed to consider the multiple relationships that connect the nodes of a network, thus obtaining multi-domain networks. However, most community detection approaches are limited to multi-layer networks, i.e. networks generated from the superposition of several single-domain networks (called layers) that are regarded as independent of each other. In addition to being computationally expensive, multi-layer approaches might yield inaccurate results because they ignore potential dependencies between layers. This paper proposes a multi-domain discrete-time quantum walks (MDQW) model for multi-domain networks. First, the walking space of network nodes in multi-domain network is constructed. Second, the quantum permutation circuit of the coin state is designed based on the coded particle state. Then, using different coin states, the shift operator performs several quantum walks on the particles. Finally, the corresponding update rule is selected to move the node according to the measurement result of the quantum state. With continuous update iteration, the shift operator automatically optimizes the discovered community structure. We experimentally compared our MDQW method with four state-of-the-art competitors on five real datasets. We used the normalized mutual information (NMI) to compare clustering quality, and we report an increase in NMI of up to 3.51 of our MDQW method in comparison with the second-best performing competitor. The MDQW method is much faster than its competitors, allowing us to conclude that MDQW is a useful tool in the analysis of large real-life multi-domain networks. Finally, we illustrate the usefulness of our approach on two real-world case studies.
This work introduces a graph-phased Szegedy's quantum walk, which incorporates link phases and local arbitrary phase rotations (APR), unlocking new possibilities for quantum algorithm efficiency. We demonstrate how to adapt quantum circuits to these advancements, allowing phase patterns that ensure computational practicality. The graph-phased model broadens the known equivalence between coined quantum walks and Szegedy's model, accommodating a wider array of coin operators. Through illustrative examples, we reveal intriguing disparities between classical and quantum interpretations of walk dynamics. Remarkably, local APR phases emerge as powerful tools for marking graph nodes, optimizing quantum searches without altering graph structure. We further explore the surprising nuances between single and double operator approaches, highlighting a greater range of compatible coins with the latter. To facilitate these advancements, we present an improved classical simulation algorithm, which operates with superior efficiency. This study not only refines quantum walk methodologies but also paves the way for future explorations, including potential applications in quantum search and PageRank algorithms. Our findings illuminate the path towards more versatile and powerful quantum computing paradigms.