Quantum speedups for dynamic programming on $n$-dimensional lattice graphs

Understand

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$.