Abstract We provide a mathematical framework for identifying the shortest path in a maze using a Grover walk, which becomes non-unitary by introducing absorbing holes. In this study, we define the maze as a network with vertices connected by unweighted edges. Our analysis of the stationary state of the truncated Grover walk on finite graphs, where we strategically place absorbing holes and self-loops on specific vertices, demonstrates that this approach can effectively solve mazes. By setting arbitrary start and goal vertices in the underlying graph, we obtain the following long-time results: (i) in tree structures, the probability amplitude is concentrated exclusively along the shortest path between start and goal; (ii) in ladder-like structures with additional paths, the probability amplitude is maximized near the shortest path.
Abstract We provide a mathematical framework for identifying the shortest path in a maze using a Grover walk, which becomes non-unitary by introducing absorbing holes. In this study, we define the maze as a network with vertices connected by unweighted edges. Our analysis of the stationary state of the truncated Grover walk on finite graphs, where we strategically place absorbing holes and self-loops on specific vertices, demonstrates that this approach can effectively solve mazes. By setting arbitrary start and goal vertices in the underlying graph, we obtain the following long-time results: (i) in tree structures, the probability amplitude is concentrated exclusively along the shortest path between start and goal; (ii) in ladder-like structures with additional paths, the probability amplitude is maximized near the shortest path.
Standard Grover quantum walks concentrate amplitude on a goal node in a struc- tured graph, making them useful for maze solving. However, in graphs with cycles, interference from non-optimal paths reduces goal probability. This paper proposes an enhanced Grover walk framework tailored to unicyclic structures. The approach mod- ifies the projection operator and navigation vector to mitigate destructive interference. Empirical evaluation using classical and quantum simulations demonstrates improved convergence, reduced sink absorption, and up to 20% higher goal probabilities. The technique generalizes to other low-cycle graphs like ladders, offering a robust tool for quantum-assisted search. The technique is further extended to ladder graphs. Keywords: quantum search, grover walks, probability-based search
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.
Given an undirected, weighted graph, with n vertices and m edges, and two special vertices s and t, the problem is to find the shortest path between them. We give two bounded-error quantum algorithms with improved runtime in the adjacency list model that solve the problem on special classes of graphs defined via pathfinding probabilities of classical random walks and the electrical network framework. Firstly, we give a simple quantum algorithm based on sampling edges from a graph via the quantum flow state and running a classical algorithm on the sampled edges. It runs in O~(l2m) expected time and uses O(logn) space on graphs where the shortest s-t path is also a minimum resistance s-t subgraph. Our main algorithm can be thought of as a divide and conquer version of this approach and works on a special class of graphs where classical loop-erased random walk has a probability q>0.537 of finding the shortest s-t path. In such cases the quantum algorithm outputs the shortest s-t path with high probability in O(ℓm) expected time and O(logn) space, where l is the length (or total weight, in case of weighted graphs) of the shortest s-t path. This algorithm can be parallelised to O~(lm) circuit depth when using O(llogn) space. With the latter we partially resolve with an affirmative answer the open problem of whether a path between two vertices can be found in the number of steps required to detect it.
We will give an introduction into the quantum search algorithms on the Markov chains introduced by Szegedy and recent modifications based on partially absorbing Markov chains due to Krovi et al.Algorithmica 74, 851 (2016) It has been shown that a quantum search can find a set of marked vertices quadratically faster (in units of the hitting time) for any reversible Markov chain.The proofs are based on certain properties of the stationary state of the partially absorbing walk and rely on quantum phase estimation techniques.We will offer an alternative view of the underlying mechanism of the quantum search based on spectral properties of the quantum walk operator.By considering the complete graph as an example, we identify the relevant two-level quantum subspace leading to a Grover-like rotation in the underlying vector space.
We analyze the potential for different types of searches using the formalism of scattering random walks on quantum computers. Given a particular type of graph consisting of nodes and connections, a ``tree maze,'' we would like to find a selected final node as quickly as possible, faster than any classical search algorithm. We show that this can be done using a quantum random walk, both through numerical calculations as well as by using the eigenvectors and eigenvalues of the quantum system.