Maze Solving by a Quantum Walk with Sinks and Self-Loops: Numerical Analysis

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

• discrete-time quantum walk
• scattering quantum random walk
• Grover walk
• pathfinding
• network