{"ID":2899677,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.00823","arxiv_id":"2507.00823","title":"Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms","abstract":"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})$.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2507.00823","url_pdf":"https://arxiv.org/pdf/2507.00823v1","authors":"[\"Susanna Caroppo\",\"Giordano Da Lozzo\",\"Giuseppe Di Battista\",\"Michael T. Goodrich\",\"Martin Nöllenburg\"]","published":"2025-07-01T14:55:18Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.DS\"]","methods":"[\"Large Language Model\"]","has_code":false}