Abstract
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 ndimensional 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 saddlepoint 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ⁿ.
BibTeX  Entry
@InProceedings{glos_et_al:LIPIcs.MFCS.2021.50,
author = {Glos, Adam and Kokainis, Martins and Mori, Ryuhei and Vihrovs, Jevg\={e}nijs},
title = {{Quantum Speedups for Dynamic Programming on nDimensional Lattice Graphs}},
booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
pages = {50:150:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772013},
ISSN = {18688969},
year = {2021},
volume = {202},
editor = {Bonchi, Filippo and Puglisi, Simon J.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14490},
URN = {urn:nbn:de:0030drops144901},
doi = {10.4230/LIPIcs.MFCS.2021.50},
annote = {Keywords: Quantum query complexity, Dynamic programming, Lattice graphs}
}
Keywords: 

Quantum query complexity, Dynamic programming, Lattice graphs 
Collection: 

46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) 
Issue Date: 

2021 
Date of publication: 

18.08.2021 