论文标题
用于凸的动态编程的量子加速
Quantum speedups for convex dynamic programming
论文作者
论文摘要
我们提出了一种量子算法来解决具有凸价值函数的动态编程问题。对于具有$ d $维的线性离散时间系统尺寸$ n $的状态空间，提出的算法输出了值函数的量子力机械表示，以时间$ o（tγ^{dt} \ mathrm {polylog} $ t $是时间范围，$γ$是特定于问题的参数，具体取决于成本功能的条件编号。这使我们能够在任何固定状态下在任何固定状态$ o（tγ^{dt} \ sqrt {n} \，\ mathrm {polylog}（n，（n，（t/\ varepsilon）^{d}））$，并且可以通过求解一个conve a Conve a Conve a可以恢复相应的最佳动作。可以应用我们的算法的优化问题类别包括可证明硬的随机动态程序。最后，我们表明该算法获得了二次加速度（限于聚类因素），与某些具有$γ= 1 $的连续状态空间的动态程序上的经典贝尔曼方法相比。
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 γ^{dT}\mathrm{polylog}(N,(T/\varepsilon)^{d}))$, where $\varepsilon$ is the accuracy of the solution, $T$ is the time horizon, and $γ$ 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 γ^{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 $γ=1$.
