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.
翻译:我们在量子计算机上讨论量子计算机的有限等离子动态编程问题。 我们引入了用于研究量子算法和经典算法以解决DP问题的查询模式, 并为流动销售人员问题、 最小集覆盖问题和编辑距离问题提供示例神器结构。 我们为 DP 提出有关四面体量子加速的开放问题, 并讨论其影响。 然后, 我们证明量子算法和典型的DP 随机算法的查询复杂性的下限, 并表明在解决DP 问题时, 无法实现比二次体化更快的速度 。