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 (23)

• Quantum Mechanics helps in searching for a needle in a haystack
• Quantum Computation and Decision Trees
• 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
• A 2D Quantum Walk Simulation of Two-Particle Dynamics
• Optimized quantum random-walk search algorithms
• Quantum walks based on an interferometric analogy
• 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
• 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
• Equivalence between discrete quantum walk models in arbitrary topologies
• Quantum walks as a probe of structural anomalies in graphs
• Finding structural anomalies in star graphs: A general approach
• Finding Structural Anomalies in Star Graphs Using Quantum Walks: A General Approach
• Searches on star graphs and equivalent oracle problems

Cited by in corpus (3)

• Finding paths in tree graphs with a quantum walk
• Quantum walk based state transfer algorithms on the complete M-partite graph
• Scattering Quantum Random Walks on Square Grids and Randomly Generated Mazes