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)

DOI: 10.48550/arxiv.1807.05209

Related papers

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 0n to 1n 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.817n). 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.817n), and graph bandwidth in time O*(2.946n). Then we use similar ideas to solve the travelling salesman problem and minimum set cover in time O*(1.728n).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 0n to 1n 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.817n). 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.817n), and graph bandwidth in time O*(2.946n). Then we use similar ideas to solve the travelling salesman problem and minimum set cover in time O*(1.728n).

Society for Industrial and Applied Mathematics eBooksJan 1, 201975 citations

Quantum Speedups for Dynamic Programming on n-Dimensional Lattice Graphs

Adam Glos, Martins Kokainis, Ryuhei Mori +1 more

Motivated by the quantum speedup for dynamic programming on the Boolean hypercube by Ambainis et al. (2019), we investigate which graphs admit a similar quantum advantage. In this paper, we examine a generalization of the Boolean hypercube graph, the $n$ -dimensional lattice graph $Q(D,n)$ with vertices in $\{0,1,\ldots,D\}^n$ . We study the complexity of the following problem: given a subgraph $G$ of $Q(D,n)$ via query access to the edges, determine whether there is a path from $0^n$ to $D^n$ . While the classical query complexity is $\widetildeΘ((D+1)^n)$ , we show a quantum algorithm with complexity $\widetilde O(T_D^n)$ , where $T_D < D+1$ . The first few values of $T_D$ are $T_1 \approx 1.817$ , $T_2 \approx 2.660$ , $T_3 \approx 3.529$ , $T_4 \approx 4.421$ , $T_5 \approx 5.332$ . We also prove that $T_D \geq \frac{D+1}{\mathrm e}$ , thus for general $D$ , this algorithm does not provide, for example, a speedup, polynomial in the size of the lattice. While the presented quantum algorithm is a natural generalization of the known quantum algorithm for $D=1$ by Ambainis et al., the analysis of complexity is rather complicated. For the precise analysis, we use the saddle-point method, which is a common tool in analytic combinatorics, but has not been widely used in this field. We then show an implementation of this algorithm with time complexity $\text{poly}(n)^{\log n} T_D^n$ , and apply it to the Set Multicover problem. In this problem, $m$ subsets of $[n]$ are given, and the task is to find the smallest number of these subsets that cover each element of $[n]$ at least $D$ times. While the time complexity of the best known classical algorithm is $O(m(D+1)^n)$ , the time complexity of our quantum algorithm is $\text{poly}(m,n)^{\log n} T_D^n$ .Motivated by the quantum speedup for dynamic programming on the Boolean hypercube by Ambainis et al. (2019), we investigate which graphs admit a similar quantum advantage. In this paper, we examine a generalization of the Boolean hypercube graph, the $n$-dimensional lattice graph $Q(D,n)$ with vertices in $\{0,1,\ldots,D\}^n$. We study the complexity of the following problem: given a subgraph $G$ of $Q(D,n)$ via query access to the edges, determine whether there is a path from $0^n$ to $D^n$. While the classical query complexity is $\widetildeΘ((D+1)^n)$, we show a quantum algorithm with complexity $\widetilde O(T_D^n)$, where $T_D < D+1$. The first few values of $T_D$ are $T_1 \approx 1.817$, $T_2 \approx 2.660$, $T_3 \approx 3.529$, $T_4 \approx 4.421$, $T_5 \approx 5.332$. We also prove that $T_D \geq \frac{D+1}{\mathrm e}$, thus for general $D$, this algorithm does not provide, for example, a speedup, polynomial in the size of the lattice. While the presented quantum algorithm is a natural generalization of the known quantum algorithm for $D=1$ by Ambainis et al., the analysis of complexity is rather complicated. For the precise analysis, we use the saddle-point method, which is a common tool in analytic combinatorics, but has not been widely used in this field. We then show an implementation of this algorithm with time complexity $\text{poly}(n)^{\log n} T_D^n$, and apply it to the Set Multicover problem. In this problem, $m$ subsets of $[n]$ are given, and the task is to find the smallest number of these subsets that cover each element of $[n]$ at least $D$ times. While the time complexity of the best known classical algorithm is $O(m(D+1)^n)$, the time complexity of our quantum algorithm is $\text{poly}(m,n)^{\log n} T_D^n$.

arXiv:2104.14384Leibniz international proceedings in informaticsJan 1, 20216 citations

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

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 Speedups for Polynomial-Time Dynamic Programming Algorithms

Caroppo, Susanna, Da Lozzo, Giordano, 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 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 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

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)

n

-dimensional lattice graph

Q(D,n)

with vertices in

\{0,1,\ldots,D\}^n

. We study the complexity of the following problem: given a subgraph

G

Q(D,n)

via query access to the edges, determine whether there is a path from

0^n

D^n

. While the classical query complexity is

\widetildeΘ((D+1)^n)

, we show a quantum algorithm with complexity

\widetilde O(T_D^n)

, where

T_D < D+1

. The first few values of

T_D

are

T_1 \approx 1.817

T_2 \approx 2.660

T_3 \approx 3.529

T_4 \approx 4.421

T_5 \approx 5.332

. We also prove that

T_D \geq \frac{D+1}{\mathrm e}

, thus for general

D

, this algorithm does not provide, for example, a speedup, polynomial in the size of the lattice. While the presented quantum algorithm is a natural generalization of the known quantum algorithm for

D=1

by Ambainis et al., the analysis of complexity is rather complicated. For the precise analysis, we use the saddle-point method, which is a common tool in analytic combinatorics, but has not been widely used in this field. We then show an implementation of this algorithm with time complexity

\text{poly}(n)^{\log n} T_D^n

, and apply it to the Set Multicover problem. In this problem,

m

subsets of

[n]

are given, and the task is to find the smallest number of these subsets that cover each element of

[n]

at least

D

times. While the time complexity of the best known classical algorithm is

O(m(D+1)^n)

, the time complexity of our quantum algorithm is

\text{poly}(m,n)^{\log n} T_D^n

\widetilde O(1.859^n)

time and

\widetilde O(1.315^n)

QRAM space.

\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.