  We consider the quantum time complexity of the all pairs shortest paths
(APSP) problem and some of its variants. The trivial classical algorithm for
APSP and most all pairs path problems runs in $O(n^3)$ time, while the trivial
algorithm in the quantum setting runs in $\tilde{O}(n^{2.5})$ time, using
Grover search. A major open problem in classical algorithms is to obtain a
truly subcubic time algorithm for APSP, i.e. an algorithm running in
$O(n^{3-\varepsilon})$ time for constant $\varepsilon>0$. To approach this
problem, many truly subcubic time classical algorithms have been devised for
APSP and its variants for structured inputs. Some examples of such problems are
APSP in geometrically weighted graphs, graphs with small integer edge weights
or a small number of weights incident to each vertex, and the all pairs
earliest arrivals problem. In this paper we revisit these problems in the
quantum setting and obtain the first nontrivial (i.e. $O(n^{2.5-\varepsilon})$
time) quantum algorithms for the problems.

Quantum Physics;Data Structures and Algorithms