  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,\ldots,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 $\widetilde{\Theta}((D+1)^n)$, we show a quantum algorithm
with complexity $\widetilde 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}$, 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 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$.
