Finding paths with quantum walks or quantum walking through a maze

Abstract

We show that it is possible to use a quantum walk to find a path from one marked vertex to another. In the specific case of $M$ stars connected in a chain, one can find the path from the first star to the last one in $O(M\sqrt{N})$ steps, where $N$ is the number of spokes of each star. First we provide an analytical result showing that by starting in a phase-modulated highly superposed initial state we can find the path in $O(M\sqrt{N}\log M)$ steps. Next, we improve this efficiency by showing that the recovery of the path can also be performed by a series of successive searches when we start at the last known position and search for the next connection in $O(\sqrt{N})$ steps leading to the overall efficiency of $O(M\sqrt{N})$. For this result we use the analytical solution that can be obtained for a ring of stars of double the length of the chain.

10 pages, 3 figures, this version contains updated parts and added Appendices

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 walks on quotient graphs
• Quantum searches on highly symmetric graphs
• Perfect state transfer by means of discrete-time quantum walk search algorithms on highly symmetric graphs
• Finding Structural Anomalies in Star Graphs Using Quantum Walks: A General Approach
• Searches on star graphs and equivalent oracle problems

Cited by in corpus (1)

• Finding paths in tree graphs with a quantum walk