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

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)

Quantum Speed-ups for Single-machine Scheduling Problems

Camille Grange, Eric Bourreau, Michaël Poss, Vincent t'Kindt

Published Jul 15, 2023• 2 citations
Publisher

Abstract

Grover search is currently one of the main approaches to obtain quantum speed-ups for combinatorial optimization problems. The combination of Quantum Minimum Finding (obtained from Grover search) with dynamic programming has proved particularly efficient to improve the worst-case complexity of several NP-hard optimization problems. Specifically, for these problems, the classical dynamic programming complexity (ignoring the polynomial factors) in O* (cn) can be reduced by a bounded-error hybrid quantum-classical algorithm to O* (cnquant) for cquant < c. In this paper, we extend the resulting hybrid dynamic programming algorithm to three examples of single-machine scheduling problems: minimizing the total weighted completion time with deadlines, minimizing the total weighted completion time with precedence constraints, and minimizing the total weighted tardiness. The extension relies on the inclusion of a pseudo-polynomial term in the state space of the dynamic programming as well as an additive term in the recurrence.

DOI
10.1145/3583133.3596415

Related papers

Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms

Caroppo, Susanna, 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 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 Õ(|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 Õ(n√nm) time, which improves the best known classical upper bound when m ∈ Ω(n1.4).

•Jan 1, 2025•0 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})$.

arXiv:2507.00823•Jul 1, 2025•4 citations

A Quantum Optimization Algorithm for Single Machine Total Weighted Tardiness Minimization

Youhao Steve Wang, Julian Cheng

A single machine total weighted tardiness minimization (TWTM) problem in operational planning is considered. The problem is formulated as an NP-hard constrained combinatorial problem, which has no known deterministic polynomial complexity solution using classical computing. Based on efficient Grover's quantum search and Trugenberger's quantum optimization algorithms, a novel efficient quantum optimization algorithm is proposed to solve the NP-hard single machine TWTM problem, which makes the desired solution satisfying the searching constraints and showing the minimal TWT value be measured with the highest probability.

arXiv:2209.13712•Sep 27, 2022•0 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.

•Jun 5, 2019•15 citations

Grandchildren-Weight-Balanced Binary Search Trees

Caroppo, Susanna, 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 P and an instance I of P, such a speedup can be expressed in terms of the average degree δ of the {dependency digraph} G_𝒫(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 Õ(|V(G_𝒫(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 Õ(n√{nm}) time, which improves the best known classical upper bound when m ∈ Ω(n^{1.4}).

arXiv:2410.08825•Leibniz international proceedings in informatics•Oct 11, 2024•2 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)$.

arXiv:1807.05209•Jul 13, 2018•14 citations
Grover search is currently one of the main approaches to obtain quantum speed-ups for combinatorial optimization problems. The combination of Quantum Minimum Finding (obtained from Grover search) with dynamic programming has proved particularly efficient to improve the worst-case complexity of several NP-hard optimization problems. Specifically, for these problems, the classical dynamic programming complexity (ignoring the polynomial factors) in O* (cn) can be reduced by a bounded-error hybrid quantum-classical algorithm to O* (cnquant) for cquant < c. In this paper, we extend the resulting hybrid dynamic programming algorithm to three examples of single-machine scheduling problems: minimizing the total weighted completion time with deadlines, minimizing the total weighted completion time with precedence constraints, and minimizing the total weighted tardiness. The extension relies on the inclusion of a pseudo-polynomial term in the state space of the dynamic programming as well as an additive term in the recurrence.
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 Õ(|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 Õ(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\mathcal PP and an instance III of P\mathcal PP, such a speedup can be expressed in terms of the average degree δδδ of the dependency digraph GP(I)G_{\mathcal{P}}(I)GP​(I) of III, determined by a recursive formulation of P\mathcal PP. The nodes of this graph are the subproblems of P\mathcal PP induced by III 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))∣δ)\tilde{O}(|V(G_{\mathcal{P}}(I))| \sqrtδ)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 nnn-vertex digraph with mmm edges that runs in O~(nnm)\tilde{O}(n\sqrt{nm})O~(nnm​) time, which improves the best known classical upper bound when m∈Ω(n1.4)m \in Ω(n^{1.4})m∈Ω(n1.4).
A single machine total weighted tardiness minimization (TWTM) problem in operational planning is considered. The problem is formulated as an NP-hard constrained combinatorial problem, which has no known deterministic polynomial complexity solution using classical computing. Based on efficient Grover's quantum search and Trugenberger's quantum optimization algorithms, a novel efficient quantum optimization algorithm is proposed to solve the NP-hard single machine TWTM problem, which makes the desired solution satisfying the searching constraints and showing the minimal TWT value be measured with the highest probability.
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∗(⌈c⌉42n)O^*(\lceil c \rceil^4 \sqrt{2^n})O∗(⌈c⌉42n​) on a quantum computer, where nnn is the number of vertices of the underlying graph and ⌈c⌉\lceil c \rceil⌈c⌉ is its maximum edge-weight. As another example, we show that the minimum set-cover problem can be solved in O(2npoly⁡(m,n))O(\sqrt{2^n} \operatorname{poly}(m, n))O(2n​poly(m,n)), where mmm is the number of sets used to cover a universe of size nnn. 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 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} G_𝒫(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 Õ(|V(G_𝒫(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 Õ(n√{nm}) time, which improves the best known classical upper bound when m ∈ Ω(n^{1.4}).
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 0n0^n0n to 1n1^n1n 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)O^*(1.817^n)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)O^*(1.817^n)O∗(1.817n), and graph bandwidth in time O∗(2.946n)O^*(2.946^n)O∗(2.946n). Then we use similar ideas to solve the travelling salesman problem and minimum set cover in time O∗(1.728n)O^*(1.728^n)O∗(1.728n).