Maze Solving by a Quantum Walk with Sinks and Self-Loops: Numerical Analysis
Open Access
Abstract
Maze-solving by natural phenomena is a symbolic result of the autonomous optimization induced by a natural system. We present a method for finding the shortest path on a maze consisting of a bipartite graph using a discrete-time quantum walk, which is a toy model of many kinds of quantum systems. By evolving the amplitude distribution according to the quantum walk on a kind of network with sinks, which is the exit of the amplitude, the amplitude distribution remains eternally on the paths between two self-loops indicating the start and the goal of the maze. We performed a numerical analysis of some simple cases and found that the shortest paths were detected by the chain of the maximum trapped densities in most cases of bipartite graphs. The counterintuitive dependence of the convergence steps on the size of the structure of the network was observed in some cases, implying that the asymmetry of the network accelerates or decelerates the convergence process. The relation between the amplitude remaining and distance of the path is also discussed briefly.Keywords
This publication has 27 references indexed in Scilit:
- Finding structural anomalies in graphs by means of quantum walksPhysical Review A, 2010
- Searching via walking: How to find a marked clique of a complete graph using quantum walksPhysical Review A, 2010
- Quantum searches on highly symmetric graphsPhysical Review A, 2009
- Quantum random walks: an introductory overviewContemporary Physics, 2009
- Spatial search by quantum walkPhysical Review A, 2004
- Quantum walks based on an interferometric analogyPhysical Review A, 2003
- Quantum random-walk search algorithmPhysical Review A, 2003
- Glow discharge in microfluidic chips for visible analog computingLab on a Chip, 2002
- Quantum Mechanics Helps in Searching for a Needle in a HaystackPhysical Review Letters, 1997
- A note on two problems in connexion with graphsNumerische Mathematik, 1959