Classical approach to the graph isomorphism problem using quantum walks
arXiv:0705.2531 · doi:10.1088/1751-8113/41/7/075303
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.
References in corpus (4)
Cited by in corpus (48)
- Two-particle quantum walks applied to the graph isomorphism problem
- Experimental Quantum Fast Hitting on Hexagonal Graphs
- Efficient Quantum Walk on a Quantum Processor
- Quantum walk-based search and centrality
- Multi-walker discrete time quantum walks on arbitrary graphs, their properties, and their photonic implementation
- Review on Quantum Walk Computing: Theory, Implementation, and Application
- Centrality measure based on continuous-time quantum walks and experimental realization
- Graph isomorphism and Gaussian boson sampling
- Combinatorial optimisation via highly efficient quantum walks
- Quantum walks and Dirac cellular automata on a programmable trapped-ion quantum computer
- Solving the Graph Isomorphism Problem with a Quantum Annealer
- Efficient quantum circuits for Szegedy quantum walks
- Discrete-time quantum walk algorithm for ranking nodes on a network
- Implementation of multidimensional quantum walks using linear optics and classical light
- From classical to quantum walks with stochastic resetting on networks
- Bounds on the dynamics of periodic quantum walks and emergence of the gapless and gapped Dirac equation
- Entanglement dynamics and quasi-periodicity in discrete quantum walks
- Photonic quantum walks with four-dimensional coins
- Solutions of a two-particle interacting quantum walk
- Efficient quantum circuits for continuous-time quantum walks on composite graphs
- Topological quantum walks: theory and experiments
- Generic Quantum Walks with Memory
- Quantum centrality testing on directed graphs via PT-symmetric quantum walks
- Cospectrality preserving graph modifications and eigenvector properties via walk equivalence of vertices
- Quantum random walks without walking
- Efficient implementation of discrete-time quantum walks on quantum computers
- Decoherence enhances performance of quantum walks applied to graph isomorphism testing
- Qcompiler: quantum compilation with CSD method
- Quantum circuits for the realization of equivalent forms of one-dimensional discrete-time quantum walks on near-term quantum hardware
- Highly noise resistant multipartite quantum correlations
- Entanglement and interaction in a topological quantum walk
- Quantum walker as a probe for its coin parameter
- GPU-accelerated algorithms for many-particle continuous-time quantum walks
- Localization of discrete time quantum walks on the glued trees
- Nonlinear flip-flop quantum walks through potential barriers
- Complexity Bounds on Quantum Search Algorithms in finite-dimensional Networks
- On quantum invariants and the graph isomorphism problem
- Quantum walks in polycyclic aromatic hydrocarbons
- Two-level Quantum Walkers on Directed Graphs I: Universal Quantum Computing
- Quantum walks on two kinds of two-dimensional models
- Implementation of Continuous-Time Quantum Walk on Sparse Graph
- Quantum information spreading in a disordered quantum walk
- The switching effect of the side chain on quantum walks on triple graphs
- Conditional limit measure of one-dimensional quantum walk with absorbing sink
- Dynamics and computation in linear open quantum walks
- Optimization for the propagation of a multiparticle quantum walk in a one-dimensional lattice
- Quantum walks under superposition of causal order
- Hybrid atom-molecule quantum walks in one-dimensional optical lattice