Quantum speedups for dynamic programming on $n$-dimensional 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 $n$-dimensional lattice graph $Q(D,n)$ with vertices in $\{0,1,\dots ,D{\}}^n$. 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^n$ to $D^n$. While the classical query complexity is $\tilde{\Theta }((D+1{)}^n)$, we show a quantum algorithm with complexity $\tilde{O}(T_D^n)$, where $T_D<D+1$. The first few values of $T_D$ are $T_1\approx 1.817$, $T_2\approx 2.660$, $T_3\approx 3.529$, $T_4\approx 4.421$, $T_5\approx 5.332$. We also prove that $T_D \geq \frac{D+1}{\mathrm e}$,thusforgeneral$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 complexity $\text{poly}(n{)}^{\log n}{T}_D^n$, 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{)}^n)$, the time complexity of our quantum algorithm is $\text{poly}(m,n{)}^{\log n}{T}_D^n$.