# Quantum Speedups for Exponential-Time Dynamic Programming Algorithms

arXiv: https://arxiv.org/abs/1807.05209 · HTML: https://mlsanity.com/paper/1807.05209/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2018.

## Built on by (most cited first, 6 of 6)

- [A Survey on Quantum Reinforcement Learning](https://mlsanity.com/paper/2211.03464/) (2022)
- [Quantum Algorithms for Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.08451/) (2021)
- [From Quantum Graph Computing to Quantum Graph Learning: A Survey](https://mlsanity.com/paper/2202.09506/) (2022)
- [Comprehensive characterization of three-qubit Grover search algorithm on IBM's 127-qubit superconducting quantum computers](https://mlsanity.com/paper/2406.16018/) (2024)
- [Quantum-Enhanced Forecasting: Leveraging Quantum Gramian Angular Field and CNNs for Stock Return Predictions](https://mlsanity.com/paper/2310.07427/) (2023)
- [Quantum Algorithm for the Shortest Superstring Problem](https://mlsanity.com/paper/2112.13319/) (2021)

## Abstract (arXiv)

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 0n to 1n 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^*(1.817n). 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^*(1.817n), and graph bandwidth in time O^*(2.946n). Then we use similar ideas to solve the travelling salesman problem and minimum set cover in time O^*(1.728n).