2026-09-17T02:19:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24245 2026-09-05T18:39:33Z ddc:004 open_access

Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms Caroppo, Susanna Da Lozzo, Giordano Di Battista, Giuseppe Goodrich, Michael T. Nöllenburg, Martin Dynamic Programming Quantum Algorithms Quantum Random Access Memory 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}). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Susanna Caroppo and Giordano Da Lozzo and Giuseppe Di Battista and Michael T. Goodrich and Martin Nöllenburg 2025 Is Part Of LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.14 urn:nbn:de:0030-drops-242454 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.14 eng https://creativecommons.org/licenses/by/4.0/legalcode