量子科技中心_量科网

在该工作中，研究团队设计了两种场景下超越经典算法效率的量子算法，用于求解时变有限阶段马尔可夫决策过程（MDPs）：（1）在精确动态设定下（即智能体完全掌握环境动态的转移概率），该团队证明所提出的“量子价值迭代算法QVI-1”在动作空间维度（A）上相比经典价值迭代算法能实现二次加速，从而更高效计算出最优策略（π*）与最优V值函数（V0*）。进一步提出的“QVI-2”算法在获取近优策略和V值函数时，还能在状态空间维度（S）上实现额外加速。这两种算法的量子查询复杂度均被证明可突破经典下界限制，尤其在S和A的依赖关系上表现显著。（2）在生成模型设定下（允许量子叠加态访问环境样本），该团队证实“QVI-3”和“QVI-4”算法在动作空间维度（A）、估计误差（ε）和时间跨度（H）等参数上，其样本复杂度均优于当前最优经典算法。更重要的是，研究通过量子下界证明：在时间跨度恒定的假设下，这两种算法在忽略对数因子时具有渐进最优性。