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

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.

Automated summary

The method utilizes quantum walk to find the shortest path on a bipartite graph maze, with the amplitude distribution evolving on the network remaining eternally on the paths. Through numerical analysis, it was found that the shortest paths can be detected by the chain of maximum trapped densities in most cases, with observed counterintuitive dependence of convergence steps on network structure size. The relationship between amplitude remaining and distance of the path is also briefly discussed.