2019/06/05 by Pooya Ronagh, Ronagh, Pooya
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Optimization and Control (math.OC) #Optimization and Search Problems #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.1906.02229
openalex publication_date 2019/06/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We discuss the problem of finite-horizon dynamic programming (DP) on a quantum computer. We introduce a query model for studying quantum and classical algorithms for solving DP problems, and provide example oracle constructions for the travelling salesperson problem, the minimum set-cover problem, and the edit distance problem. We formulate open questions regarding quadratic quantum speedups for DP and discuss their implications. We then prove lower bounds for the query complexity of quantum algorithms and classical randomized algorithms for DP, and show that no greater-than-quadratic speedup can be achieved for solving DP problems.