量子科技中心_量科网

该研究团队提出了一种量子动态编程框架，使得大量经典动态编程算法能够直接拓展至量子领域。相应的量子动态编程算法在保持与经典算法相同空间复杂度的同时，实现了计算加速。针对组合问题P及其实例I，这种加速效果可通过依赖有向图GP(I)的平均出度δ来表征——该图节点由实例I产生的子问题构成，弧线则表征子问题间的递归依赖关系。特别地，该框架能以O˜(|V(GP(I))|√δ)时间复杂度求解问题。以贝尔曼-福特算法为例，研究人员实现了计算单源点加权有向图最短路径的量子版本：对于含n个顶点和m条边的图，其时间复杂度为O˜(n√nm)，当边数m∈Ω(n^1.4)时优于现有经典算法最优上界。