Glos, Adam ;
Kokainis, Martins ;
Mori, Ryuhei ;
Vihrovs, Jevgēnijs
Quantum Speedups for Dynamic Programming on nDimensional Lattice Graphs
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}
}
18.08.2021
Keywords: 

Quantum query complexity, Dynamic programming, Lattice graphs 
Seminar: 

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

Issue date: 

2021 
Date of publication: 

18.08.2021 