A classical approach to the graph isomorphism problem using quantum walks
Open accessThe DOI matches its Crossref record; 13 of the 13 references it cites were found in a registry or an index.
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Indeed, quantum walks have been successfully applied to database search [6] and graph isomorphism [7] problems.”
From Multi-walker discrete time quantum walks on arbitrary graphs, their properties and their photonic implementation (2011) · cites this paper as [7]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Quantum random walks: An introductory overview
Kempe, J. (2003) · Contemporary Physics · doi:10.1080/00107151031000110776 · Cited by 1,413
Quantum random-walk search algorithm
Shenvi, N., Kempe, J., & Whaley, K. B. (2003) · Physical Review A · doi:10.1103/physreva.67.052307 · Cited by 1,150
Isomorphism of graphs of bounded valence can be tested in polynomial time
Luks, E. M. (1982) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(82)90009-5 · Cited by 645
QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS
AMBAINIS, A. (2003) · International Journal of Quantum Information · doi:10.1142/s0219749903000383 · Cited by 632
Babai, L., & Luks, E. M. (1983) · Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83 · doi:10.1145/800061.808746 · Cited by 410
Köbler, J., Schöning, U., & Torán, J. (1993) · Birkhäuser Boston eBooks · doi:10.1007/978-1-4612-0333-9 · Cited by 297
Implementing the quantum random walk
Travaglione, B. C., & Milburn, G. J. (2002) · Physical Review A · doi:10.1103/physreva.65.032310 · Cited by 295
Controlling discrete quantum walks: coins and initial states
Tregenna, B., Flanagan, W., Maile, R., & Kendon, V. (2003) · New Journal of Physics · doi:10.1088/1367-2630/5/1/383 · Cited by 264
Zemlyachenko, V. N., Korneenko, N. M., & Tyshkevich, R. I. (1985) · Journal of Mathematical Sciences · doi:10.1007/bf02104746 · Cited by 174
Graph isomorphism, general remarks
Miller, G. L. (1979) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(79)90043-6 · Cited by 93
Research works printed but not linked: 4
- Hopcroft J, 1971, J. Comput. Syst. Sci., 1, 32
- Mackay B, 1981, Congr. Numer., 30, 45
- Graham R, 1995, Handbook of Combinatorics, 2
- Gross J, 2004, Handbook of Graph Theory
Cited by
Konno, N. (2008) · Lecture notes in mathematics · doi:10.1007/978-3-540-69365-9_7 · Cited by 252
Quantum walk and its application domains: A systematic review
Kadian, K., Garhwal, S., & Kumar, A. (2021) · Computer Science Review · doi:10.1016/j.cosrev.2021.100419 · Cited by 204
Two-particle quantum walks: Entanglement and graph isomorphism testing
Berry, S. D., & Wang, J. B. (2011) · Physical Review A · doi:10.1103/physreva.83.042317 · Cited by 152
Self-citationTwo-particle quantum walks applied to the graph isomorphism problem
Gamble, J. K., Friesen, M., Zhou, D., Joynt, R., & Coppersmith, S. N. (2010) · Physical Review A · doi:10.1103/physreva.81.052313 · Cited by 145
Experimental quantum fast hitting on hexagonal graphs
Tang, H., Di Franco, C., Shi, Z.-Y., He, T.-S., Feng, Z., Gao, J., Sun, K., Li, Z.-M., Jiao, Z.-Q., Wang, T.-Y., et al. (2018) · Nature Photonics · doi:10.1038/s41566-018-0282-5 · Cited by 113
Metadata
- Authors
- Douglas, B. L., & Wang, J. B.
- Affiliations
- The University of Western Australia (AU)
- Venue
- Journal of Physics A: Mathematical and Theoretical
- Publisher
- IOP Publishing
- Published
- 2008-02-05
- Volume
- 41
- Issue
- 7
- Pages
- 075303
- ISSN
- 1751-8113 (ISSN-L)
- 1751-8121
- OpenAlex
- W2094509719
- Cited by
- 126
- References
- 13
- Citations by year
- 2026: 2 · 2025: 9 · 2024: 5 · 2023: 3 · 2022: 4 · 2021: 11 · 2020: 12 · 2019: 8 · 2018: 15 · 2017: 11 · 2016: 4 · 2015: 7 · 2014: 8 · 2013: 4 · 2012: 7
- FWCI
- 8.46
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Journal of Physics A Mathematical and Theoretical (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- UWA Profiles and Research Repository (UWA) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Graph Theory and Algorithms
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Keywords
- graph isomorphism, quantum walks, discrete-time quantum walks, classical random walks, strongly regular graphs, quantum algorithms, graph databases
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: A classical approach to the graph isomorphism problem using quantum walks. https://app.cochat.ai/papers/10.1088/1751-8113/41/7/075303
- The paper
- Douglas, B. L., & Wang, J. B. (2008). A classical approach to the graph isomorphism problem using quantum walks. Journal of Physics A: Mathematical and Theoretical. https://doi.org/10.1088/1751-8113/41/7/075303
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.