A classical approach to the graph isomorphism problem using quantum walks
From MaRDI portal
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.
Recommendations
- An enhanced classical approach to graph isomorphism using continuous-time quantum walk
- A quantum-walk-inspired adiabatic algorithm for solving graph isomorphism problems
- Physically-motivated dynamical algorithms for the graph isomorphism problem
- A graph isomorphism algorithm using signatures computed via quantum walk search model
- Exponential algorithmic speedup by a quantum walk
Cited in
(31)- Graph matching using the interference of continuous-time quantum walks
- GPU-accelerated algorithms for many-particle continuous-time quantum walks
- Two quantum coins sharing a walker
- Cospectrality preserving graph modifications and eigenvector properties via walk equivalence of vertices
- Continuous-time quantum walks on strongly regular graphs with loops and its application to spatial search for multiple marked vertices
- Quantum walks with memory provided by parity of memory
- Efficient quantum circuits for Szegedy quantum walks
- Quantum walks on two kinds of two-dimensional models
- Quantum walk and its application domains: a systematic review
- Discrete-time quantum walk algorithm for ranking nodes on a network
- Szegedy quantum walks with memory on regular graphs
- Quantum walk inspired algorithm for graph similarity and isomorphism
- A systematic method to building Dirac quantum walks coupled to electromagnetic fields
- Overview: recent development and applications of reduction and lackadaisicalness techniques for spatial search quantum walk in the near term
- Three-state quantum walk on the Cayley graph of the dihedral group
- A quantum-walk-inspired adiabatic algorithm for solving graph isomorphism problems
- Efficient quantum circuits for continuous-time quantum walks on composite graphs
- On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism
- \textit{pyCTQW}: a continuous-time quantum walk simulator on distributed memory computers
- An enhanced classical approach to graph isomorphism using continuous-time quantum walk
- Discrete-time interacting quantum walks and quantum hash schemes
- \(Qcompiler\): quantum compilation with the CSD method
- Local feature point extraction for quantum images
- Multi-Walker discrete time quantum walks on arbitrary graphs, their properties and their photonic implementation
- A graph isomorphism algorithm using signatures computed via quantum walk search model
- Phase-modified CTQW unable to distinguish strongly regular graphs efficiently
- Quantum walks, Ihara zeta functions and cospectrality in regular graphs
- Entanglement entropy in the ground state of supersymmetric fermion lattice models
- Quantum walks under superposition of causal order
- Entanglement dynamics of two-particle quantum walks
- Graph isomorphism and Gaussian boson sampling
This page was built for publication: A classical approach to the graph isomorphism problem using quantum walks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5454303)
