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

arXiv:0705.2531 · Journal of Physics A Mathematical and Theoretical

A classical approach to the graph isomorphism problem using quantum walks

B. L. Douglas, J. B. Wang

Published Feb 5, 2008• 124 citations
arXivHTMLPDF

Abstract

Given the extensive application of classical random walks to classical algorithms in a variety of fields, their quantum analogue in quantum walks is expected to provide a fruitful source of quantum algorithms. So far, however, such algorithms have been scarce. In this work, we enumerate some important differences between quantum and classical walks, leading to their markedly different properties. We show that for many practical purposes, the implementation of quantum walks can be efficiently achieved using a classical computer. We then develop both classical and quantum graph isomorphism algorithms based on discrete-time quantum walks. We show that they are effective in identifying isomorphism classes of large databases of graphs, in particular groups of strongly regular graphs. We consider this approach to represent a promising candidate for an efficient solution to the graph isomorphism problem, and believe that similar methods employing quantum walks, or derivatives of these walks, may prove beneficial in constructing other algorithms for a variety of purposes.

DOI
10.1088/1751-8113/41/7/075303

Related papers

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 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 and classical algorithms for graph classification and search problems

B. L. Douglas

[Truncated abstract] This thesis is split into three parts, each addressing the overarching theme of applying graph theoretic techniques to classi cation and search problems. Part I explores this theme in the context of quantum algorithms, in particular involving quantum walks, coined by Aharonov et al. in 1993 [1]. As a quantum analogue to classical random walks, quantum walks represent a promising candidate for quantum algorithms providing speed-ups over known classical methods. I will discuss two categories of quantum walk algorithms; quantum search and graph isomorphism. In particular, the e ciency of quantum walk based search algorithms on various families of graphs will be investigated, linking both e ciency of quantum circuit implementation and the complexity of the search problem to the symmetry of the underlying graphs. Several families of graphs are presented that are amenable to efficient quantum walk based searching, together with explicit quantum circuit implementations. In the case of the n-cube, I show that O(p2n) steps of a quanum walk are suffcient to nd a marked sub-d-cube (where d

•Jan 1, 2011•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•28 citations

Discrete Quantum Walks on Graphs and Digraphs

Chris D. Godsil, Hanmeng Zhan

Discrete quantum walks are quantum analogues of classical random walks. They are an important tool in quantum computing and a number of algorithms can be viewed as discrete quantum walks, in particular Grover's search algorithm. These walks are constructed on an underlying graph, and so there is a relation between properties of walks and properties of the graph. This book studies the mathematical problems that arise from this connection, and the different classes of walks that arise. Written at a level suitable for graduate students in mathematics, the only prerequisites are linear algebra and basic graph theory; no prior knowledge of physics is required. The text serves as an introduction to this important and rapidly developing area for mathematicians and as a detailed reference for computer scientists and physicists working on quantum information theory.

Cambridge University Press eBooks•Dec 23, 2022•15 citations

Quantum Computation and Isomorphism Testing

David J. Rosenbaum

In this thesis, we study quantum computation and algorithms for isomorphism problems. Some of the problems that we cover are fundamentally quantum and therefore require quantum techniques. For other problems, classical approaches are more appropriate; however, we often give quantum variants of our classical algorithms as well. The field of quantum computation aims to accelerate algorithms by exploiting the laws of quantum mechanics. Several quantum algorithms are known that are exponentially faster than the best classical algorithms known for the same problems, including several which are relevant to cryptography. Quantum computing is therefore of great importance. On the theory side, it has already transformed our notions of which problems are tractable and which are not. On the practical side, the construction of a quantum computer would render many popular techniques for encryption obsolete. We derive several results in quantum computation. Quantum algorithms are normally formulated in an abstract way that ignores practical details such as where different parts of the computation are located physically. Using naive methods for translating these algorithms into practical quantum computing technologies increases the time complexity by a linear factor, while previous work reduced this factor to a square root. We further reduce this factor to a constant at the cost of requiring additional space. This retroactively justifies an important assumption made in many quantum algorithms. Another interesting problem is to determine the query complexity of extracting different types of information from physical processes. In the case of deterministic processes, it is well known that quantum algorithms cannot outperform deterministic algorithms by more than an exponential factor. We show --- somewhat surprisingly --- that when the process is allowed to be randomized, there are problems that have a constant quantum query complexity but cannot be solved classically no matter how many queries are made. In fact, we show how to construct such an infinity-vs-one separation from any weaker separation between the classical and quantum query complexities. In an isomorphism problem, we seek to determine if two algebraic or combinatorial objects have the same structure. One of the most well-known of these is the graph isomorphism problem, which is interesting since it is suspected to be of complexity intermediate between P and the NP-complete problems. We transition from quantum computation to isomorphism testing by considering the tree isomorphism problem. While linear-time classical algorithms are known for this problem, we show that a promising framework for developing efficient quantum algorithms for graph isomorphism, known as the state preparation approach, can also solve tree isomorphism. While this result might seem modest, it is important to know that the state preparation approach works for trees, since otherwise there would be little hope of using it to obtain efficient algorithms for more interesting classes of graphs. We also derive a powerful primitive along the way that is of independent interest. Next, we study the group isomorphism problem, which is a special case of graph isomorphism. Group isomorphism is suspected to be significantly easier than graph isomorphism, but still has unknown complexity. While group isomorphism is already of interest since it is a fundamental computational question about groups, searching for faster algorithms for group isomorphism is therefore also one way of approaching the graph isomorphism problem. We use collision detection methods to give a classical algorithm that obtains a square-root speedup over the best algorithm previously known for the general group isomorphism problem. For the solvable groups (which are conjectured to be difficult and contain almost all groups), we combine our collision detection techniques with group-theoretic methods to obtain a classical fourth-root speedup over the best algorithm known previously. Prior to this work, it was a longstanding open problem to obtain any improvement for either of these classes of groups. Finally, we give a general framework that yields speedups for many isomorphism problems. In particular, it yields the square-root speedup for testing isomorphism of general groups mentioned above. All of our group isomorphism-testing algorithms also have quantum variants that are slightly faster than their classical counterparts.

•Jan 1, 2015•2 citations
Given the extensive application of classical random walks to classical algorithms in a variety of fields, their quantum analogue in quantum walks is expected to provide a fruitful source of quantum algorithms. So far, however, such algorithms have been scarce. In this work, we enumerate some important differences between quantum and classical walks, leading to their markedly different properties. We show that for many practical purposes, the implementation of quantum walks can be efficiently achieved using a classical computer. We then develop both classical and quantum graph isomorphism algorithms based on discrete-time quantum walks. We show that they are effective in identifying isomorphism classes of large databases of graphs, in particular groups of strongly regular graphs. We consider this approach to represent a promising candidate for an efficient solution to the graph isomorphism problem, and believe that similar methods employing quantum walks, or derivatives of these walks, may prove beneficial in constructing other algorithms for a variety of purposes.
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.
[Truncated abstract] This thesis is split into three parts, each addressing the overarching theme of applying graph theoretic techniques to classi cation and search problems. Part I explores this theme in the context of quantum algorithms, in particular involving quantum walks, coined by Aharonov et al. in 1993 [1]. As a quantum analogue to classical random walks, quantum walks represent a promising candidate for quantum algorithms providing speed-ups over known classical methods. I will discuss two categories of quantum walk algorithms; quantum search and graph isomorphism. In particular, the e ciency of quantum walk based search algorithms on various families of graphs will be investigated, linking both e ciency of quantum circuit implementation and the complexity of the search problem to the symmetry of the underlying graphs. Several families of graphs are presented that are amenable to efficient quantum walk based searching, together with explicit quantum circuit implementations. In the case of the n-cube, I show that O(p2n) steps of a quanum walk are suffcient to nd a marked sub-d-cube (where d
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.
Discrete quantum walks are quantum analogues of classical random walks. They are an important tool in quantum computing and a number of algorithms can be viewed as discrete quantum walks, in particular Grover's search algorithm. These walks are constructed on an underlying graph, and so there is a relation between properties of walks and properties of the graph. This book studies the mathematical problems that arise from this connection, and the different classes of walks that arise. Written at a level suitable for graduate students in mathematics, the only prerequisites are linear algebra and basic graph theory; no prior knowledge of physics is required. The text serves as an introduction to this important and rapidly developing area for mathematicians and as a detailed reference for computer scientists and physicists working on quantum information theory.
In this thesis, we study quantum computation and algorithms for isomorphism problems. Some of the problems that we cover are fundamentally quantum and therefore require quantum techniques. For other problems, classical approaches are more appropriate; however, we often give quantum variants of our classical algorithms as well. The field of quantum computation aims to accelerate algorithms by exploiting the laws of quantum mechanics. Several quantum algorithms are known that are exponentially faster than the best classical algorithms known for the same problems, including several which are relevant to cryptography. Quantum computing is therefore of great importance. On the theory side, it has already transformed our notions of which problems are tractable and which are not. On the practical side, the construction of a quantum computer would render many popular techniques for encryption obsolete. We derive several results in quantum computation. Quantum algorithms are normally formulated in an abstract way that ignores practical details such as where different parts of the computation are located physically. Using naive methods for translating these algorithms into practical quantum computing technologies increases the time complexity by a linear factor, while previous work reduced this factor to a square root. We further reduce this factor to a constant at the cost of requiring additional space. This retroactively justifies an important assumption made in many quantum algorithms. Another interesting problem is to determine the query complexity of extracting different types of information from physical processes. In the case of deterministic processes, it is well known that quantum algorithms cannot outperform deterministic algorithms by more than an exponential factor. We show --- somewhat surprisingly --- that when the process is allowed to be randomized, there are problems that have a constant quantum query complexity but cannot be solved classically no matter how many queries are made. In fact, we show how to construct such an infinity-vs-one separation from any weaker separation between the classical and quantum query complexities. In an isomorphism problem, we seek to determine if two algebraic or combinatorial objects have the same structure. One of the most well-known of these is the graph isomorphism problem, which is interesting since it is suspected to be of complexity intermediate between P and the NP-complete problems. We transition from quantum computation to isomorphism testing by considering the tree isomorphism problem. While linear-time classical algorithms are known for this problem, we show that a promising framework for developing efficient quantum algorithms for graph isomorphism, known as the state preparation approach, can also solve tree isomorphism. While this result might seem modest, it is important to know that the state preparation approach works for trees, since otherwise there would be little hope of using it to obtain efficient algorithms for more interesting classes of graphs. We also derive a powerful primitive along the way that is of independent interest. Next, we study the group isomorphism problem, which is a special case of graph isomorphism. Group isomorphism is suspected to be significantly easier than graph isomorphism, but still has unknown complexity. While group isomorphism is already of interest since it is a fundamental computational question about groups, searching for faster algorithms for group isomorphism is therefore also one way of approaching the graph isomorphism problem. We use collision detection methods to give a classical algorithm that obtains a square-root speedup over the best algorithm previously known for the general group isomorphism problem. For the solvable groups (which are conjectured to be difficult and contain almost all groups), we combine our collision detection techniques with group-theoretic methods to obtain a classical fourth-root speedup over the best algorithm known previously. Prior to this work, it was a longstanding open problem to obtain any improvement for either of these classes of groups. Finally, we give a general framework that yields speedups for many isomorphism problems. In particular, it yields the square-root speedup for testing isomorphism of general groups mentioned above. All of our group isomorphism-testing algorithms also have quantum variants that are slightly faster than their classical counterparts.