Two-particle quantum walks applied to the graph isomorphism problem
Open accessAbstract
We show that the quantum dynamics of interacting and noninteracting quantum particles are fundamentally different in the context of solving a particular computational problem. Specifically, we consider the graph isomorphism problem, in which one wishes to determine whether two graphs are isomorphic (related to each other by a relabeling of the graph vertices), and focus on a class of graphs with particularly high symmetry called strongly regular graphs (SRGs). We study the Green's functions that characterize the dynamical evolution single-particle and two-particle quantum walks on pairs of nonisomorphic SRGs and show that interacting particles can distinguish nonisomorphic graphs that noninteracting particles cannot. We obtain the following specific results. (1) We prove that quantum walks of two noninteracting particles, fermions or bosons, cannot distinguish certain pairs of nonisomorphic SRGs. (2) We demonstrate numerically that two interacting bosons are more powerful than single particles and two noninteracting particles, in that quantum walks of interacting bosons distinguish all nonisomorphic pairs of SRGs that we examined. By utilizing high-throughput computing to perform over 500 million direct comparisons between evolution operators, we checked all tabulated pairs of nonisomorphic SRGs, including graphs with up to 64 vertices. (3) By performing a short-time expansion of the evolution operator, we derive distinguishing operators that provide analytic insight into the power of the interacting two-particle quantum walk.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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?
For quantum walks of more than one indistinguishable particle, classical theory no longer provides a sufficient description; quantum theory predicts that probability amplitudes interfere leading to distinctly non-classical correlations.
“In contrast, for quantum walks of more than one indistinguishable particle, classical theory no longer provides a sufficient description-quantum theory predicts that probability amplitudes interfere leading to distinctly non-classical correlations [19, 20].”
From Quantum Walks of Correlated Photons (2010) · cites this paper as [20]
The Introduction (p. 1) says classical and quantum random walks can have qualitatively different properties. The Introduction (p. 2) discusses altered dynamics from effective statistical interactions in walks of indistinguishable bosons. Our copy does not state that interfering probability amplitudes produce distinctly non-classical correlations in multiparticle walks, so that specific mechanism is not supported. (LLM, conf=0.78)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Godsil, C., & Royle, G. (2001) · Graduate Texts in Mathematics · doi:10.1007/978-1-4613-0163-9 · Cited by 8,154 · see citing works
Fernández, T. A. (2006) · conference · Cited by 5,362 · see citing works
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,098 · see citing works
Aharonov, Y., Davidovich, L., & Zagury, N. (1993) · Physical Review A · doi:10.1103/physreva.48.1687 · Cited by 1,622 · see citing works
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 · see citing works
Universal Computation by Quantum Walk
Childs, A. M. (2009) · Physical Review Letters · doi:10.1103/physrevlett.102.180501 · Cited by 1,002 · see citing works
Why is it so difficult to beat the random walk forecast of exchange rates?
Kilian, L., & Taylor, M. P. (2003) · Journal of International Economics · doi:10.1016/s0022-1996(02)00060-0 · Cited by 797 · see citing works
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 660 · see citing works
QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS
AMBAINIS, A. (2003) · International Journal of Quantum Information · doi:10.1142/s0219749903000383 · Cited by 632 · see citing works
An Example of the Difference Between Quantum and Classical Random Walks
Childs, A. M., Farhi, E., & Gutmann, S. (2002) · Quantum Information Processing · doi:10.1023/a:1019609420309 · Cited by 481 · see citing works
Quantum Walk of a Trapped Ion in Phase Space
Schmitz, H., Matjeschk, R., Schneider, C., Glueckert, J., Enderlein, M., Huber, T., & Schaetz, T. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.090504 · Cited by 462 · see citing works
Proceedings of the twenty-eighth annual ACM symposium on Theory of computing
Miller, G. L. (1996) · Cited by 401 · see citing works
Implementing the quantum random walk
Travaglione, B. C., & Milburn, G. J. (2002) · Physical Review A · doi:10.1103/physreva.65.032310 · Cited by 295 · see citing works
Ryan, C. A., Laforest, M., Boileau, J. C., & Laflamme, R. (2005) · Physical Review A · doi:10.1103/physreva.72.062317 · Cited by 280 · see citing works
Hubaut, X. (1975) · Discrete Mathematics · doi:10.1016/0012-365x(75)90057-6 · Cited by 245 · see citing works
Graph isomorphism is in the low hierarchy
Schöning, U. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90010-4 · Cited by 235 · see citing works
Interface Mobility from Interface Random Walk
Trautt, Z., Upmanyu, M., & Karma, A. (2006) · Science · doi:10.1126/science.1131988 · Cited by 138 · see citing works
One-dimensional quantum walks with absorbing boundaries
Bach, E., Coppersmith, S. N., Goldschen, M. P., Joynt, R., & Watrous, J. (2004) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2004.03.005 · Cited by 135 · see citing works
Self-citationA classical approach to the graph isomorphism problem using quantum walks
Douglas, B. L., & Wang, J. B. (2008) · Journal of Physics A: Mathematical and Theoretical · doi:10.1088/1751-8113/41/7/075303 · Cited by 126 · see citing works
Optimized quantum random-walk search algorithms on the hypercube
Potoček, V., Gábris, A., Kiss, T., & Jex, I. (2009) · Physical Review A · doi:10.1103/physreva.79.012325 · Cited by 116 · see citing works
A Matrix Representation of Graphs and its Spectrum as a Graph Invariant
Emms, D., Hancock, E. R., Severini, S., et al. (2006) · The Electronic Journal of Combinatorics · doi:10.37236/1060 · Cited by 82 · see citing works
Continuous-time quantum walks on a cycle graph
Solenov, D., & Fedichkin, L. E. (2006) · Physical Review A · doi:10.1103/physreva.73.012313 · Cited by 80 · see citing works
One- and two-dimensional quantum walks in arrays of optical traps
Eckert, K., Mompart, J., Birkl, G., & Lewenstein, M. (2005) · Physical Review A · doi:10.1103/physreva.72.012327 · Cited by 74 · see citing works
Quantum searches on highly symmetric graphs
Reitzner, D., Hillery, M. S., Feldman, E., & Bužek, V. (2009) · Physical Review A · doi:10.1103/physreva.79.012323 · Cited by 72 · see citing works
Bose-Einstein condensation in inhomogeneous Josephson arrays
Burioni, R., Cassi, D., Meccoli, I., Rasetti, M., Regina, S., Sodano, P., & Vezzani, A. (2000) · Europhysics Letters (EPL) · doi:10.1209/epl/i2000-00431-5 · Cited by 65 · see citing works
Quantum phase transition using quantum walks in an optical lattice
Chandrashekar, C. M., & Laflamme, R. (2008) · Physical Review A · doi:10.1103/physreva.78.022314 · Cited by 55 · see citing works
Coined quantum walks lift the cospectrality of graphs and trees
Emms, D., Simone Severini, B., Wilson, R. C., & Hancock, E. R. (2008) · Pattern Recognition · doi:10.1016/j.patcog.2008.10.025 · Cited by 55 · see citing works
Physically-motivated dynamical algorithms for the graph isomorphism problem
Shiau, S.-Y., Joynt, R., & Coppersmith, S. N. (2005) · Quantum Information and Computation · doi:10.26421/qic5.6-7 · Cited by 34 · see citing works
Self-citationBose-Einstein condensation on inhomogeneous networks: Mesoscopic aspects versus thermodynamic limit
Buonsante, P., Burioni, R., Cassi, D., et al. (2002) · Physical review. B, Condensed matter · doi:10.1103/physrevb.66.094207 · Cited by 31 · see citing works
Quantum random walk of the field in an externally driven cavity
Agarwal, G. S., & Pathak, P. K. (2005) · Physical Review A · doi:10.1103/physreva.72.033815 · Cited by 28 · see citing works
Random walk models for DNA synapsis by resolvase
Sessions, R. B., Oram, M., Szczelkun, M. D., et al. (1997) · Journal of Molecular Biology · doi:10.1006/jmbi.1997.1108 · Cited by 25 · see citing works
Quantum random walks without walking
Manouchehri, K., & Wang, J. B. (2009) · Physical Review A · doi:10.1103/physreva.80.060304 · Cited by 17 · see citing works
Mancini, F. P., Sodano, P., & Trombettoni, A. (2007) · AIP conference proceedings · doi:10.1063/1.2751999 · Cited by 2 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Quantum Walks of Correlated Photons
Peruzzo, A., Lobino, M., Matthews, J. C. F., Matsuda, N., Politi, A., Poulios, K., Zhou, X.-Q., Lahini, Y., Ismail, N., Wörhoff, K., et al. (2010) · Science · doi:10.1126/science.1193515 · Cited by 929 · see citing works
Two-Particle Bosonic-Fermionic Quantum Walk via Integrated Photonics
Sansoni, L., Sciarrino, F., Vallone, G., Mataloni, P., Crespi, A., Ramponi, R., & Osellame, R. (2012) · Physical Review Letters · doi:10.1103/physrevlett.108.010502 · Cited by 578 · see citing works
QASMBench: A Low-Level Quantum Benchmark Suite for NISQ Evaluation and Simulation
Li, A., Stein, S., Krishnamoorthy, S., & Ang, J. (2023) · ACM Transactions on Quantum Computing · doi:10.1145/3550488 · Cited by 183 · see citing works
Rohde, P. P., Schreiber, A., Štefaňák, M., Jex, I., & Silberhorn, C. (2011) · New Journal of Physics · doi:10.1088/1367-2630/13/1/013001 · Cited by 81 · see citing works
A quantum walk-assisted approximate algorithm for bounded NP optimisation problems
Marsh, S., & Wang, J. B. (2019) · Quantum Information Processing · doi:10.1007/s11128-019-2171-3 · Cited by 50 · see citing works
Quantum walks and Dirac cellular automata on a programmable trapped-ion quantum computer
Huerta Alderete, C., Singh, S., Nguyen, N. H., Zhu, D., Balu, R., Monroe, C., Chandrashekar, C. M., & Linke, N. M. (2020) · Nature Communications · doi:10.1038/s41467-020-17519-4 · Cited by 48 · see citing works
Multi-particle quantum walks on 3D integrated photonic chip
Zhou, W.-H., Wang, X.-W., Ren, R.-J., Fu, Y.-X., Chang, Y.-J., Xu, X.-Y., Tang, H., & Jin, X.-M. (2024) · Light: Science & Applications · doi:10.1038/s41377-024-01627-7 · Cited by 16 · see citing works
Singh, S., Alderete, C. H., Balu, R., Monroe, C., Linke, N. M., & Chandrashekar, C. M. (2021) · Physical Review A · doi:10.1103/physreva.104.062401 · Cited by 13 · see citing works
- Authors
- Gamble, J. K., Friesen, M., Zhou, D., Joynt, R., & Coppersmith, S. N.
- Affiliations
- University of Wisconsin–Madison (US)
- Venue
- Physical Review A
- Publisher
- American Physical Society (APS)
- Published
- 2010-05-13
- Volume
- 81
- Issue
- 5
- ISSN
- 0556-2791 (ISSN-L)
- 1050-2947
- 1094-1622
- OpenAlex
- W2046796099
- Cited by
- 145
- References
- 33
- Citations by year
- 2026: 1 · 2025: 4 · 2024: 8 · 2023: 7 · 2022: 7 · 2021: 9 · 2020: 8 · 2019: 13 · 2018: 7 · 2017: 10 · 2016: 13 · 2015: 12 · 2014: 10 · 2013: 7 · 2012: 15
- FWCI
- 12.16
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Physical Review A (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Bulletin of the American Physical Society
- Funders
- National Science Foundation
- U.S. Department of Defense
- Army Research Office
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Mechanics and Applications
- Keywords
- two-particle quantum walk, graph isomorphism problem, strongly regular graphs, interacting bosons, fermions, Green's function, evolution operator, short-time expansion, quantum computing
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
