Finding paths in tree graphs with a quantum walk
arXiv:1710.05084 · doi:10.1103/PhysRevA.97.012308
Abstract
In this paper, we analyze the potential for new types of searches using the formalism of scattering random walks on Quantum Computers. Given a particular type of graph consisting of nodes and connections, a "Tree Maze", we would like to find a selected final node as quickly as possible, faster than any classical search algorithm. We show that this can be done using a quantum random walk, both exactly through numerical calculations as well as analytically using eigenvectors and eigenvalues of the quantum system.
References in corpus (11)
- Quantum walks of correlated particles
- Spatial search by quantum walk
- Quantum Walk in Position Space with Single Optically Trapped Atoms
- Realization of quantum walks with negligible decoherence in waveguide lattices
- A 2D Quantum Walk Simulation of Two-Particle Dynamics
- Optimized quantum random-walk search algorithms
- Quantum searches on highly symmetric graphs
- Perfect state transfer by means of discrete-time quantum walk search algorithms on highly symmetric graphs
- Finding paths with quantum walks or quantum walking through a maze
- Finding Structural Anomalies in Star Graphs Using Quantum Walks: A General Approach
- Searches on star graphs and equivalent oracle problems