Quantum speedups for exponential-time dynamic programming algorithms

DOI10.1137/1.9781611975482.107MaRDI QIDQ5236291zbMATH OpenOpenAlexFDO

Authors Kaspars Balodis, Jānis Iraids, Martins Kokainis, Krišjānis Prūsis, Jevgēnijs Vihrovs, Andris Ambainis

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Dynamic programming (90C39)

Abstract: In this paper we study quantum algorithms for NP-complete problems whose best classical algorithm is an exponential time application of dynamic programming. We introduce the path in the hypercube problem that models many of these dynamic programming algorithms. In this problem we are asked whether there is a path from $0^n$ to $1^n$ in a given subgraph of the Boolean hypercube, where the edges are all directed from smaller to larger Hamming weight. We give a quantum algorithm that solves path in the hypercube in time $O^{\ast }(1.817^n)$. The technique combines Grover's search with computing a partial dynamic programming table. We use this approach to solve a variety of vertex ordering problems on graphs in the same time $O^{\ast }(1.817^n)$, and graph bandwidth in time $O^{\ast }(2.946^n)$. Then we use similar ideas to solve the travelling salesman problem and minimum set cover in time $O^{\ast }(1.728^n)$.

Recommendations

• Solving NP-Complete Problems with Quantum Search
• A Quantum Algorithm for Finding a Hamilton Circuit
• A panoply of quantum algorithms
• Exponential algorithmic speedup by a quantum walk
• On quantum algorithm for exptime problem

Cited in

(27)

• Fast quantum subroutines for the simplex method
• Quantum algorithm for dynamic programming approach for DAGs. Applications for Zhegalkin polynomial evaluation and some problems on DAGs
• Estimating quantum speedups for lattice sieves
• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• On quantum algorithm for exptime problem
• scientific article; zbMATH DE number 1775388 (Why is no real title available?)
• Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
• Exponential-time quantum algorithms for graph coloring problems
• Exponential-time quantum algorithms for graph coloring problems
• An introduction to variational quantum algorithms for combinatorial optimization problems
• Quantum bounds for 2D-grid and Dyck language
• Quantum Speedups for Dynamic Programming on n-Dimensional Lattice Graphs
• Quantum complexity for vector domination problem
• Mind the gap: achieving a super-Grover quantum speedup by jumping to the end
• Representing polynomial of \textsc{St-Connectivity}
• Classification and transformations of quantum circuit decompositions for permutation operations
• Dynamic programming in economics on a quantum annealer
• Quantum algorithms for graph coloring and other partitioning, covering, and packing problems
• Quantum algorithms for one-sided crossing minimization
• Quantum algorithms for one-sided crossing minimization
• A quantum speedup algorithm for TSP based on quantum dynamic programming with very few qubits
• Classical and quantum algorithms for variants of subset-sum via dynamic programming
• Moderate exponential-time quantum dynamic programming across the subsets for scheduling problems
• Quantum algorithm for finding the optimal variable ordering for binary decision diagrams
• An introduction to variational quantum algorithms for combinatorial optimization problems
• Parameterized quantum query algorithms for graph problems
• Quantum speedups for polynomial-time dynamic programming algorithms

This page was built for publication: Quantum speedups for exponential-time dynamic programming algorithms

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