2026-08-17T15:51:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14490 2024-03-06T10:54:09Z ddc:004 open_access

Quantum Speedups for Dynamic Programming on n-Dimensional Lattice Graphs Glos, Adam Kokainis, Martins Mori, Ryuhei Vihrovs, Jevgēnijs Quantum query complexity Dynamic programming Lattice graphs 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,…,D}ⁿ. 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ⁿ to Dⁿ. While the classical query complexity is Θ̃((D+1)ⁿ), we show a quantum algorithm with complexity Õ(T_Dⁿ), where T_D < D+1. The first few values of T_D are T₁ ≈ 1.817, T₂ ≈ 2.660, T₃ ≈ 3.529, T₄ ≈ 4.421, T₅ ≈ 5.332. We also prove that T_D ≥ (D+1)/e (here, e ≈ 2.718 is the Euler’s number), 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 and space complexity poly(n)^{log n} T_Dⁿ in the QRAM model, 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)ⁿ), the time complexity of our quantum algorithm is poly(m,n)^{log n} T_Dⁿ. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Adam Glos and Martins Kokainis and Ryuhei Mori and Jevgēnijs Vihrovs 2021 Is Part Of LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2021.50 urn:nbn:de:0030-drops-144901 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.50 eng https://creativecommons.org/licenses/by/4.0/legalcode