Quantum speedups for dynamic programming on n-dimensional lattice graphs
share
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,…,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 Θ((D+1)^n), we show a quantum algorithm with complexity O(T_D^n), where T_D < D+1. The first few values of T_D are T_1 ≈ 1.817, T_2 ≈ 2.660, T_3 ≈ 3.529, T_4 ≈ 4.421, T_5 ≈ 5.332. We also prove that T_D ≥D+1/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 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 poly(m,n)^log n T_D^n.
READ FULL TEXT