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 (20)
- A Quantum Random Walk Search Algorithm
- Quantum walks of correlated particles
- Spatial search by quantum walk
- Quantum Walk in Position Space with Single Optically Trapped Atoms
- Photons Walking the Line: A quantum walk with adjustable coin operations
- Realization of quantum walks with negligible decoherence in waveguide lattices
- Quantum walk of a trapped ion in phase space
- An example of the difference between quantum and classical random walks
- 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
- Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs
- Searching via walking: How to find a marked subgraph of a graph using quantum walks
- Finding structural anomalies in graphs by means of quantum walks
- Quantum walks as a probe of structural anomalies in graphs
- Finding structural anomalies in star graphs: A general approach
- 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
Cited by in corpus (10)
- Aperiodic space-inhomogeneous quantum walks: localization properties, energy spectra and enhancement of entanglement
- Quantum spatial search in two-dimensional waveguide arrays
- Quantum walk based state transfer algorithms on the complete M-partite graph
- Controlled quantum search on structured databases
- Optimizing the walk coin in the quantum random walk search algorithm through machine learning
- Scattering Quantum Random Walks on Square Grids and Randomly Generated Mazes
- Localization of quantum walk with classical randomness: Comparison between manual methods and supervised machine learning
- High robustness quantum walk search algorithm with qudit Householder traversing coin, machine learning study
- QWalkVec: Node Embedding by Quantum Walk
- The Open Quantum Brownian Motion and continual measurements