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 $\tilde{O}(l^2\sqrt{m})$ expected time and uses $O(\log{n})$ 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 $\widetilde{O}(\ell\sqrt{m})$ expected time and $O(\log{n})$ 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 $\tilde{O}(\sqrt{lm})$ circuit depth when using $O(l\log{n})$ 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.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 $\tilde{O}(l^2\sqrt{m})$ expected time and uses $O(\log{n})$ 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 $\widetilde{O}(\ell\sqrt{m})$ expected time and $O(\log{n})$ 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 $\tilde{O}(\sqrt{lm})$ circuit depth when using $O(l\log{n})$ 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.

arXiv:2408.10427Aug 19, 20241 citation

Finding paths with quantum walks

Mark S. Hillery

Bulletin of the American Physical SocietyMar 8, 20190 citations

A mathematical framework for maze solving using quantum walks

Leo Matsuoka, Hiromichi Ohno, Etsuo Segawa

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.

arXiv:2411.12191Quantum Information ProcessingMar 17, 20252 citations

Applications of quantum walk algorithms

de Jan Vos

Aug 1, 20060 citations

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

\tilde{O}(l^2\sqrt{m})

expected time and uses

O(\log{n})

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

\widetilde{O}(\ell\sqrt{m})

expected time and

O(\log{n})

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

\tilde{O}(\sqrt{lm})

circuit depth when using

O(l\log{n})

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.