We introduce a quantum dynamic programming framework that allows us to directly extend to the quantum realm a large body of classical dynamic programming algorithms. The corresponding quantum dynamic programming algorithms retain the same space complexity as their classical counterpart, while achieving a computational speedup. For a combinatorial (search or optimization) problem P and an instance I of P, such a speedup can be expressed in terms of the average degree δ of the dependency digraph GP(I) of I, determined by a recursive formulation of P. The nodes of this graph are the subproblems of P induced by I and its arcs are directed from each subproblem to those on whose solution it relies. In particular, our framework allows us to solve the considered problems in Õ(|V (GP(I))|√δ) time. As an example, we obtain a quantum version of the Bellman-Ford algorithm for computing shortest paths from a single source vertex to all the other vertices in a weighted n-vertex digraph with m edges that runs in Õ(n√nm) time, which improves the best known classical upper bound when m ∈ Ω(n1.4).We introduce a quantum dynamic programming framework that allows us to directly extend to the quantum realm a large body of classical dynamic programming algorithms. The corresponding quantum dynamic programming algorithms retain the same space complexity as their classical counterpart, while achieving a computational speedup. For a combinatorial (search or optimization) problem P and an instance I of P, such a speedup can be expressed in terms of the average degree δ of the dependency digraph GP(I) of I, determined by a recursive formulation of P. The nodes of this graph are the subproblems of P induced by I and its arcs are directed from each subproblem to those on whose solution it relies. In particular, our framework allows us to solve the considered problems in Õ(|V (GP(I))|√δ) time. As an example, we obtain a quantum version of the Bellman-Ford algorithm for computing shortest paths from a single source vertex to all the other vertices in a weighted n-vertex digraph with m edges that runs in Õ(n√nm) time, which improves the best known classical upper bound when m ∈ Ω(n1.4).

Jan 1, 20250 citations

Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms

Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista +2 more

We introduce a quantum dynamic programming framework that allows us to directly extend to the quantum realm a large body of classical dynamic programming algorithms. The corresponding quantum dynamic programming algorithms retain the same space complexity as their classical counterpart, while achieving a computational speedup. For a combinatorial (search or optimization) problem $\mathcal P$ and an instance $I$ of $\mathcal P$ , such a speedup can be expressed in terms of the average degree $δ$ of the dependency digraph $G_{\mathcal{P}}(I)$ of $I$ , determined by a recursive formulation of $\mathcal P$ . The nodes of this graph are the subproblems of $\mathcal P$ induced by $I$ and its arcs are directed from each subproblem to those on whose solution it relies. In particular, our framework allows us to solve the considered problems in $\tilde{O}(|V(G_{\mathcal{P}}(I))| \sqrtδ)$ time. As an example, we obtain a quantum version of the Bellman-Ford algorithm for computing shortest paths from a single source vertex to all the other vertices in a weighted $n$ -vertex digraph with $m$ edges that runs in $\tilde{O}(n\sqrt{nm})$ time, which improves the best known classical upper bound when $m \in Ω(n^{1.4})$ .We introduce a quantum dynamic programming framework that allows us to directly extend to the quantum realm a large body of classical dynamic programming algorithms. The corresponding quantum dynamic programming algorithms retain the same space complexity as their classical counterpart, while achieving a computational speedup. For a combinatorial (search or optimization) problem $\mathcal P$ and an instance $I$ of $\mathcal P$, such a speedup can be expressed in terms of the average degree $δ$ of the dependency digraph $G_{\mathcal{P}}(I)$ of $I$, determined by a recursive formulation of $\mathcal P$. The nodes of this graph are the subproblems of $\mathcal P$ induced by $I$ and its arcs are directed from each subproblem to those on whose solution it relies. In particular, our framework allows us to solve the considered problems in $\tilde{O}(|V(G_{\mathcal{P}}(I))| \sqrtδ)$ time. As an example, we obtain a quantum version of the Bellman-Ford algorithm for computing shortest paths from a single source vertex to all the other vertices in a weighted $n$-vertex digraph with $m$ edges that runs in $\tilde{O}(n\sqrt{nm})$ time, which improves the best known classical upper bound when $m \in Ω(n^{1.4})$.

arXiv:2507.00823Jul 1, 20250 citations

Quantum Algorithms for Solving Dynamic Programming Problems

Pooya Ronagh

We present a general quantum algorithm for solving finite-horizon dynamic programming problems. Up to polylogarithmic factors, our algorithm provides a quadratic quantum advantage in terms of the number of states of a given dynamic programming problem. This speedup comes at the expense of the appearance of other polynomial factors representative of the number of actions of the dynamic programming problem, the maximum value of the instantaneous reward, and the time horizon of the problem. Our algorithm can be applied to combinatorial optimization problems solved classically using dynamic programming techniques. As one application, we show that the travelling salesperson problem can be solved in $O^*(\lceil c \rceil^4 \sqrt{2^n})$ on a quantum computer, where $n$ is the number of vertices of the underlying graph and $\lceil c \rceil$ is its maximum edge-weight. As another example, we show that the minimum set-cover problem can be solved in $O(\sqrt{2^n} \operatorname{poly}(m, n))$ , where $m$ is the number of sets used to cover a universe of size $n$ . Finally, we prove lower bounds for the query complexity of quantum algorithms and classical randomized algorithms for solving dynamic programming problems, and show that no greater-than-quadratic speedup in either the number of states or number of actions can be achieved for solving dynamic programming problems using quantum algorithms.We present a general quantum algorithm for solving finite-horizon dynamic programming problems. Up to polylogarithmic factors, our algorithm provides a quadratic quantum advantage in terms of the number of states of a given dynamic programming problem. This speedup comes at the expense of the appearance of other polynomial factors representative of the number of actions of the dynamic programming problem, the maximum value of the instantaneous reward, and the time horizon of the problem. Our algorithm can be applied to combinatorial optimization problems solved classically using dynamic programming techniques. As one application, we show that the travelling salesperson problem can be solved in $O^*(\lceil c \rceil^4 \sqrt{2^n})$ on a quantum computer, where $n$ is the number of vertices of the underlying graph and $\lceil c \rceil$ is its maximum edge-weight. As another example, we show that the minimum set-cover problem can be solved in $O(\sqrt{2^n} \operatorname{poly}(m, n))$, where $m$ is the number of sets used to cover a universe of size $n$. Finally, we prove lower bounds for the query complexity of quantum algorithms and classical randomized algorithms for solving dynamic programming problems, and show that no greater-than-quadratic speedup in either the number of states or number of actions can be achieved for solving dynamic programming problems using quantum algorithms.

Jun 5, 201913 citations

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.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, 20250 citations

Quantum Speedups for Exponential-Time Dynamic Programming Algorithms

Andris Ambainis, Kaspars Balodis, Jānis Iraids +3 more

In this paper we study quantum algorithms for NP-complete problems whose best classical algorithm is an exponential time application of dynamic programming. We introduce the path in the hypercube problem that models many of these dynamic programming algorithms. In this problem we are asked whether there is a path from $0^n$ to $1^n$ in a given subgraph of the Boolean hypercube, where the edges are all directed from smaller to larger Hamming weight. We give a quantum algorithm that solves path in the hypercube in time $O^*(1.817^n)$ . The technique combines Grover's search with computing a partial dynamic programming table. We use this approach to solve a variety of vertex ordering problems on graphs in the same time $O^*(1.817^n)$ , and graph bandwidth in time $O^*(2.946^n)$ . Then we use similar ideas to solve the travelling salesman problem and minimum set cover in time $O^*(1.728^n)$ .In this paper we study quantum algorithms for NP-complete problems whose best classical algorithm is an exponential time application of dynamic programming. We introduce the path in the hypercube problem that models many of these dynamic programming algorithms. In this problem we are asked whether there is a path from $0^n$ to $1^n$ in a given subgraph of the Boolean hypercube, where the edges are all directed from smaller to larger Hamming weight. We give a quantum algorithm that solves path in the hypercube in time $O^*(1.817^n)$. The technique combines Grover's search with computing a partial dynamic programming table. We use this approach to solve a variety of vertex ordering problems on graphs in the same time $O^*(1.817^n)$, and graph bandwidth in time $O^*(2.946^n)$. Then we use similar ideas to solve the travelling salesman problem and minimum set cover in time $O^*(1.728^n)$.

arXiv:1807.05209Jul 13, 20181 citation

Quantum Time-Space Tradeoffs for Exponential Dynamic Programming

Susanna Caroppo, Jevgēnijs Vihrovs, Dārta Zajakina +1 more

We investigate the quantum algorithms for dynamic programming by Ambainis et al. (SODA'19). While giving provable complexity speedups and applicable to a variety of NP-hard problems, these algorithms have a notable drawback: they require a large amount of Quantum Random Access Memory (QRAM), which potentially could be very challenging to implement in a physical quantum computer. In this work, we study how we can improve the space complexity by trading it for time, while still retaining a speedup over the classical algorithms. We show novel quantum time-space tradeoffs by combining different classical approaches with quantum techniques. For instance, we show that the Travelling Salesman Problem can be solved quantumly in $\widetilde O(1.859^n)$ time and $\widetilde O(1.315^n)$ QRAM space.We investigate the quantum algorithms for dynamic programming by Ambainis et al. (SODA'19). While giving provable complexity speedups and applicable to a variety of NP-hard problems, these algorithms have a notable drawback: they require a large amount of Quantum Random Access Memory (QRAM), which potentially could be very challenging to implement in a physical quantum computer. In this work, we study how we can improve the space complexity by trading it for time, while still retaining a speedup over the classical algorithms. We show novel quantum time-space tradeoffs by combining different classical approaches with quantum techniques. For instance, we show that the Travelling Salesman Problem can be solved quantumly in $\widetilde O(1.859^n)$ time and $\widetilde O(1.315^n)$ QRAM space.

quant-pharXiv:2604.02233Leibniz international proceedings in informaticsApr 3, 20260 citations

\mathcal P

and an instance

I

\mathcal P

, such a speedup can be expressed in terms of the average degree

δ

of the dependency digraph

G_{\mathcal{P}}(I)

I

, determined by a recursive formulation of

\mathcal P

. The nodes of this graph are the subproblems of

\mathcal P

induced by

I

and its arcs are directed from each subproblem to those on whose solution it relies. In particular, our framework allows us to solve the considered problems in

\tilde{O}(|V(G_{\mathcal{P}}(I))| \sqrtδ)

time. As an example, we obtain a quantum version of the Bellman-Ford algorithm for computing shortest paths from a single source vertex to all the other vertices in a weighted

n

-vertex digraph with

m

edges that runs in

\tilde{O}(n\sqrt{nm})

time, which improves the best known classical upper bound when

m \in Ω(n^{1.4})

O^*(\lceil c \rceil^4 \sqrt{2^n})

on a quantum computer, where

n

is the number of vertices of the underlying graph and

\lceil c \rceil

is its maximum edge-weight. As another example, we show that the minimum set-cover problem can be solved in

O(\sqrt{2^n} \operatorname{poly}(m, n))

, where

m

is the number of sets used to cover a universe of size

n

. Finally, we prove lower bounds for the query complexity of quantum algorithms and classical randomized algorithms for solving dynamic programming problems, and show that no greater-than-quadratic speedup in either the number of states or number of actions can be achieved for solving dynamic programming problems using quantum algorithms.

0^n

1^n

in a given subgraph of the Boolean hypercube, where the edges are all directed from smaller to larger Hamming weight. We give a quantum algorithm that solves path in the hypercube in time

O^*(1.817^n)

. The technique combines Grover's search with computing a partial dynamic programming table. We use this approach to solve a variety of vertex ordering problems on graphs in the same time

O^*(1.817^n)

, and graph bandwidth in time

O^*(2.946^n)

. Then we use similar ideas to solve the travelling salesman problem and minimum set cover in time

O^*(1.728^n)

\widetilde O(1.859^n)

time and

\widetilde O(1.315^n)

QRAM space.