  We present a quantum algorithm to solve dynamic programming problems with
convex value functions. For linear discrete-time systems with a $d$-dimensional
state space of size $N$, the proposed algorithm outputs a quantum-mechanical
representation of the value function in time $O(T
\gamma^{dT}\mathrm{polylog}(N,(T/\varepsilon)^{d}))$, where $\varepsilon$ is
the accuracy of the solution, $T$ is the time horizon, and $\gamma$ is a
problem-specific parameter depending on the condition numbers of the cost
functions. This allows us to evaluate the value function at any fixed state in
time $O(T \gamma^{dT}\sqrt{N}\,\mathrm{polylog}(N,(T/\varepsilon)^{d}))$, and
the corresponding optimal action can be recovered by solving a convex program.
The class of optimization problems to which our algorithm can be applied
includes provably hard stochastic dynamic programs. Finally, we show that the
algorithm obtains a quadratic speedup (up to polylogarithmic factors) compared
to the classical Bellman approach on some dynamic programs with continuous
state space that have $\gamma=1$.
