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).
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).
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.
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.
Let G be a strongly regular graph of prime order p with connection degree k≥6. We prove that the \emph{quantum walk characteristic polynomial} χq(G,λ):=det(λI−UG), where UG is the coined quantum walk operator on G, completely determines G up to isomorphism within the class of strongly regular graphs of the same order.
The proof proceeds in three steps. First, we show that UG block-diagonalizes under the discrete Fourier transform over Zp, yielding p blocks UG(j) of size k×k. Second, we prove an explicit formula χq(UG(j),λ)=(λ−1)(k−2)/2(λ+1)(k−2)/2(λ2−k2AG(j)λ+1), from which the Fourier coefficient AG(j) is recovered as the unique real part of an eigenvalue of UG(j) distinct from ±1. Third, the inverse discrete Fourier transform recovers the connection set S of G, and Turner's theorem (1967) identifies G up to isomorphism. As a consequence, graph isomorphism is decidable in polynomial time within this class using the quantum walk spectrum, without resorting to the general quasi-polynomial algorithm of Babai (2016).
This paper investigates the application of quantum walk algorithms to large-scale graph search problems. Classical algorithms often struggle with the computational complexity of exploring vast graphs, particularly when searching for specific patterns or nodes. Quantum walks, inspired by the probabilistic nature of random walks, provide a promising alternative by utilizing quantum superposition and interference to accelerate the search process. We explore the theoretical framework and potential advantages of employing quantum walks for graph traversal, focusing on scenarios where exponential speedups are theoretically possible. This work aims to demonstrate the potential of quantum computing to tackle computationally demanding graph search tasks that are currently intractable for classical methods. The core concept leverages the ability to simultaneously explore multiple paths within a graph, drastically reducing the search time compared to sequential exploration. We present a foundational understanding of quantum walk implementation and analyze its suitability for various graph search algorithms.
This paper investigates the application of quantum walk algorithms to graph traversal problems. Traditional graph traversal algorithms often suffer from performance limitations when dealing with large and complex graphs due to their inherent sequential nature. We propose utilizing quantum walks, quantum analogs of random walks, as a potential solution. Quantum walks leverage quantum superposition and interference to enable more efficient exploration of the graph. We present a theoretical framework for designing quantum walk-based algorithms for graph traversal, focusing on key aspects such as Hamiltonian construction, walker evolution, and measurement strategies. Our work demonstrates the potential for exponential speedups for specific graph algorithms compared to their classical counterparts. We analyze the core principles underpinning this approach and highlight the advantages of quantum walk based algorithms for graph traversal.