  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.
