Quantum Speedups for Dynamic Programming on n-Dimensional Lattice Graphs

DOI10.4230/LIPICS.MFCS.2021.50MaRDI QIDQ6168468zbMATH OpenOpenAlexFDO

Authors Adam Glos, Martins Kokainis, Ryuhei Mori, Jevgēnijs Vihrovs

Publication date 8 August 2023

Full work available at URL https://arxiv.org/abs/2104.14384

zbMATH Keywords

dynamic programminglattice graphsquantum query complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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,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 $widetildeTheta((D+1{)}^n)$, we show a quantum algorithm with complexity $widetildeO(T_D^n)$, where $T_D<D+1$. The first few values of $T_D$ are $T_{1}approx1.817$, $T_{2}approx2.660$, $T_{3}approx3.529$, $T_{4}approx4.421$, $T_{5}approx5.332$. We also prove that $T_{D}geqfracD+1mathrme$, 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 $extpoly(n{)}^{logn}{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 $extpoly(m,n{)}^{logn}{T}_D^n$.

Recommendations

• Quantum speedups for exponential-time dynamic programming algorithms
• Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
• Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
• Quantum algorithm for dynamic programming approach for DAGs and applications
• MAPPING, PROGRAMMABILITY AND SCALABILITY OF PROBLEMS FOR QUANTUM SPEED-UP
• Estimating quantum speedups for lattice sieves
• SOFSEM 2004: Theory and Practice of Computer Science
• Quantum Query Complexity of Some Graph Problems
• Automata, Languages and Programming
• Quantum speedup for the minimum Steiner tree problem

Cited in

(10)

• Quantum lattice enumeration and tweaking discrete pruning
• Fast quantum subroutines for the simplex method
• Quantum algorithms for variants of average-case lattice problems via filtering
• A dynamic programming approach for distributing quantum circuits by bipartite graphs
• Estimating quantum speedups for lattice sieves
• Quantum time complexity and algorithms for pattern matching on labeled graphs
• Classification and transformations of quantum circuit decompositions for permutation operations
• Dynamic programming in economics on a quantum annealer
• Quantum algorithms for one-sided crossing minimization
• Quantum speedups for polynomial-time dynamic programming algorithms

This page was built for publication: Quantum Speedups for Dynamic Programming on n-Dimensional Lattice Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6168468)