量子科技中心_量科网

“背包强盗问题”（BwK）是一个结合了随机整数规划与在线学习要素的基础模型。经典BwK算法在时间跨度T下，可实现与问题无关的𝒪(√T)遗憾界和与问题相关的𝒪(log T)遗憾界。该研究团队首次探索了量子计算框架下的BwK模型，其中奖励与资源消耗均可通过量子预言机获取。研究建立了量子BwK算法在两类遗憾界上的理论保证：在问题无关场景中，量子方法能将经典遗憾界提升(1+B/OPT_LP)倍（B为BwK预算约束，OPT_LP表示BwK线性规划松弛的最优值）；在问题相关场景中，研究人员通过开发基于非精确量子线性规划求解器的算法，实现了问题相关参数上的二次改进，并在问题维度复杂度上获得相对于经典算法的多项式加速。相较于此前量子多臂老虎机算法的研究，该工作首次引入资源约束机制，为运筹学领域提供了新的量子解决方案。