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, 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 Õ(|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•0 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•13 citations

Grandchildren-Weight-Balanced Binary Search Trees

Caroppo, Susanna, Giordano Da Lozzo, Di Battista, Giuseppe +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•0 citations

A quantum speedup algorithm for TSP based on quantum dynamic programming with very few qubits

Bai Xujun, Yun, Shang

The Traveling Salesman Problem (TSP) is a classical NP-hard problem that plays a crucial role in combinatorial optimization. In this paper, we are interested in the quantum search framework for the TSP because it has robust theoretical guarantees. However, we need to first search for all Hamiltonian cycles from a very large solution space, which greatly weakens the advantage of quantum search algorithms. To address this issue, one can first prepare a superposition state of all feasible solutions, and then amplify the amplitude of the optimal solution from it. We propose a quantum algorithm to generate the uniform superposition state of all N-length Hamiltonian cycles as an initial state within polynomial gate complexity based on pure quantum dynamic programming with very few ancillary qubits, which achieves exponential acceleration compared to the previous initial state preparation algorithm. As a result, we realized the theoretical minimum query complexity of quantum search algorithms for a general TSP. Compared to some algorithms that theoretically have lower query complexities but lack practical implementation solutions, our algorithm has feasible circuit implementation. Our work provides a meaningful research case on how to fully utilize the structures of specific problems to unleash the acceleration capability of the quantum search algorithms.

arXiv:2502.08853•Feb 12, 2025•0 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}).
The Traveling Salesman Problem (TSP) is a classical NP-hard problem that plays a crucial role in combinatorial optimization. In this paper, we are interested in the quantum search framework for the TSP because it has robust theoretical guarantees. However, we need to first search for all Hamiltonian cycles from a very large solution space, which greatly weakens the advantage of quantum search algorithms. To address this issue, one can first prepare a superposition state of all feasible solutions, and then amplify the amplitude of the optimal solution from it. We propose a quantum algorithm to generate the uniform superposition state of all N-length Hamiltonian cycles as an initial state within polynomial gate complexity based on pure quantum dynamic programming with very few ancillary qubits, which achieves exponential acceleration compared to the previous initial state preparation algorithm. As a result, we realized the theoretical minimum query complexity of quantum search algorithms for a general TSP. Compared to some algorithms that theoretically have lower query complexities but lack practical implementation solutions, our algorithm has feasible circuit implementation. Our work provides a meaningful research case on how to fully utilize the structures of specific problems to unleash the acceleration capability of the quantum search algorithms.