  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$ (the $D=1$ case corresponds to the
hypercube and replicates the result of Ambainis et al.).
  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$.
