Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1410.6220

Quantum algorithms for shortest paths problems in structured instances

Aran Nayebi, Virginia Vassilevska Williams

Published Oct 23, 2014• 10 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1410.6220

Related papers

Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model

Taisuke Izumi, François Le Gall

The All-Pairs Shortest Path problem (APSP) is one of the most central problems in distributed computation. In the CONGEST-CLIQUE model, in which n nodes communicate with each other over a fully connected network by exchanging messages of O(łog n) bits in synchronous rounds, the best known general algorithm for APSP uses Õ(n1/3) rounds. Breaking this barrier is a fundamental challenge in distributed graph algorithms. In this paper we investigate for the first time quantum distributed algorithms in the CONGEST-CLIQUE model, where nodes can exchange messages of O(log n) quantum bits, and show that this barrier can be broken: we construct a Õ(n1/4)-round quantum distributed algorithm for the APSP over directed graphs with polynomial weights in the CONGEST-CLIQUE model. This speedup in the quantum setting contrasts with the case of the standard CONGEST model, for which Elkin et al. (PODC 2014) showed that quantum communication does not offer significant advantages over classical communication.

arXiv:1906.02456•ACM Symposium on Principles of Distributed Computing (PODC)•Jul 16, 2019•29 citations

Advances in quantum algorithms for the shortest path problem

Adam Wesołowski, Stephen Piddock

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.10427•Aug 19, 2024•13 citations

A-1-20 On the Quantum Query Complexity of All-Pairs Shortest Paths

Fuwei Cai, Satoshi Tayu, Shuichi Ueno

We show lower bounds for the quantum query complex-ity of the all-pairs shortest paths problem (APSP) for non-negatively weighted directed graphs (digraphs), both in the adjacency matrix model and in an adja-

電子情報通信学会総合大会講演論文集•Mar 7, 2007•1 citation

Quantum Algorithmic Complexity in Graph Theory -Shortest Path Problems and Quantum Acceleration Mechanisms

Jeffrey Quinn Cordova

We provide a rigorous theoretical analysis of quantum algorithms for shortest path problems in weighted graphs, establishing complexity-theoretic foundations for quantum acceleration in this fundamental computational domain. Building upon recent quantum adaptations of classical graph algorithms, we develop a unified framework that characterizes when and why quantum approaches offer computational advantages for single-source and all-pairs shortest path computations. Our analysis encompasses both positive-weight and negative-weight scenarios, deriving conditional speedup theorems that depend on graph structure, weight distribution, and oracle access models. We prove that quantum amplitude amplification and quantum walks can provide polynomial to exponential speedups under specific structural assumptions, while establishing hardness results that identify problem instances where quantum advantage is provably absent. The theoretical framework introduces novel complexity measures that capture graph-theoretic properties relevant to quantum algorithm performance, including quantum diameter, entanglement capacity, and interference efficiency. We extend our analysis to dynamic graph scenarios where edge weights evolve over time, establishing bounds on quantum advantage preservation under graph modifications. This work contributes fundamental insights into quantum algorithmic graph theory, clarifying the boundaries of quantum computational advantage and providing theoretical guidance for algorithm design in network optimization, routing, and graph analytics applications.

•Oct 21, 2025•0 citations

Quantum Algorithm for Shortest Path Search in Directed Acyclic Graph

Kamil Ravilevich Khadiev, Liliya Safina

In this work, we consider a well-known “Single Source Shortest Path Search” problems for weighted directed acyclic graphs (DAGs). We suggest a quantum algorithm with time complexity $O(\sqrt {nm} \,\log \;n)$ and O(1/n) error probability, where n is a number of Vertexes, m is the number of edges. We use quantum dynamic programming approach (Khadiev, 2018) and Dürr and Høyer minimum search algorithm to speed up our search. Our algorithm is better than C. Dürr and coauthors’ quantum algorithm for an undirected graph. The time complexity of C. Dürr’s algorithm is $O(\sqrt {nm} \,{(\log \;n)^2})$ . The best known deterministic algorithm for the problem is based on a dynamic programming approach and its time complexity is O (n + m). At the same time, if we use algorithms for general graphs, then we do not get better results. The time complexity of best implementations of Dijkstra’s algorithm with Fibonacci heap is O (m + n log n).

Moscow University Computational Mathematics and Cybernetics•Jan 1, 2019•5 citations

A quantum algorithm for finding length of shortest path in the connected weighted graph

Mir Shahriar Emami, M. Tabasi, Hossein Keshmiri

In this paper we are going to discuss on the Quantum Computation approach and then we present a Quantum Algorithm for finding the estimation of the shortest path length between two vertices in a connected weighted graph with a polynomial time complexity O(n) whereas this problem based on the classic algorithm can be solved with time complexity about O(n2 -n).

International Conference on Parallel and Distributed Computing and Networks•Feb 12, 2008•0 citations
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(n3)O(n^3)O(n3) time, while the trivial algorithm in the quantum setting runs in O~(n2.5)\tilde{O}(n^{2.5})O~(n2.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(n3−ε)O(n^{3-\varepsilon})O(n3−ε) time for constant ε>0\varepsilon>0ε>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(n2.5−ε)O(n^{2.5-\varepsilon})O(n2.5−ε) time) quantum algorithms for the problems.
The All-Pairs Shortest Path problem (APSP) is one of the most central problems in distributed computation. In the CONGEST-CLIQUE model, in which n nodes communicate with each other over a fully connected network by exchanging messages of O(łog n) bits in synchronous rounds, the best known general algorithm for APSP uses Õ(n1/3) rounds. Breaking this barrier is a fundamental challenge in distributed graph algorithms. In this paper we investigate for the first time quantum distributed algorithms in the CONGEST-CLIQUE model, where nodes can exchange messages of O(log n) quantum bits, and show that this barrier can be broken: we construct a Õ(n1/4)-round quantum distributed algorithm for the APSP over directed graphs with polynomial weights in the CONGEST-CLIQUE model. This speedup in the quantum setting contrasts with the case of the standard CONGEST model, for which Elkin et al. (PODC 2014) showed that quantum communication does not offer significant advantages over classical communication.
Given an undirected, weighted graph, with nnn vertices and mmm edges, and two special vertices sss and ttt, 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)\tilde{O}(l^2\sqrt{m})O~(l2m​) expected time and uses O(log⁡n)O(\log{n})O(logn) space on graphs where the shortest sss-ttt path is also a minimum resistance sss-ttt 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.537q>0.537q>0.537 of finding the shortest sss-ttt path. In such cases the quantum algorithm outputs the shortest sss-ttt path with high probability in O~(ℓm)\widetilde{O}(\ell\sqrt{m})O(ℓm​) expected time and O(log⁡n)O(\log{n})O(logn) space, where lll is the length (or total weight, in case of weighted graphs) of the shortest sss-ttt path. This algorithm can be parallelised to O~(lm)\tilde{O}(\sqrt{lm})O~(lm​) circuit depth when using O(llog⁡n)O(l\log{n})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 provide a rigorous theoretical analysis of quantum algorithms for shortest path problems in weighted graphs, establishing complexity-theoretic foundations for quantum acceleration in this fundamental computational domain. Building upon recent quantum adaptations of classical graph algorithms, we develop a unified framework that characterizes when and why quantum approaches offer computational advantages for single-source and all-pairs shortest path computations. Our analysis encompasses both positive-weight and negative-weight scenarios, deriving conditional speedup theorems that depend on graph structure, weight distribution, and oracle access models. We prove that quantum amplitude amplification and quantum walks can provide polynomial to exponential speedups under specific structural assumptions, while establishing hardness results that identify problem instances where quantum advantage is provably absent. The theoretical framework introduces novel complexity measures that capture graph-theoretic properties relevant to quantum algorithm performance, including quantum diameter, entanglement capacity, and interference efficiency. We extend our analysis to dynamic graph scenarios where edge weights evolve over time, establishing bounds on quantum advantage preservation under graph modifications. This work contributes fundamental insights into quantum algorithmic graph theory, clarifying the boundaries of quantum computational advantage and providing theoretical guidance for algorithm design in network optimization, routing, and graph analytics applications.
In this work, we consider a well-known “Single Source Shortest Path Search” problems for weighted directed acyclic graphs (DAGs). We suggest a quantum algorithm with time complexity O(nm log⁡  n)O(\sqrt {nm} \,\log \;n)O(nm​logn) and O(1/n) error probability, where n is a number of Vertexes, m is the number of edges. We use quantum dynamic programming approach (Khadiev, 2018) and Dürr and Høyer minimum search algorithm to speed up our search. Our algorithm is better than C. Dürr and coauthors’ quantum algorithm for an undirected graph. The time complexity of C. Dürr’s algorithm is O(nm (log⁡  n)2)O(\sqrt {nm} \,{(\log \;n)^2})O(nm​(logn)2) . The best known deterministic algorithm for the problem is based on a dynamic programming approach and its time complexity is O (n + m). At the same time, if we use algorithms for general graphs, then we do not get better results. The time complexity of best implementations of Dijkstra’s algorithm with Fibonacci heap is O (m + n log n).