量子科技中心_量科网

精准覆盖问题是一种具有广泛应用的NP完全问题。研究表明，虽然对该问题应用量子近似优化算法（QAOA）可通过增加电路深度提升解的质量，但会限制算法在含噪声中等规模量子设备上的适用性。为在浅层深度下提高解的质量，该研究团队提出一种量子辅助递归算法（QARA）来求解精准覆盖问题。该算法通过经典剪枝与量子剪枝交替执行来解决问题：经典剪枝是可重复执行的预处理步骤用于简化问题；当经典剪枝无法促进问题简化时，则调用量子剪枝——此时QARA从QAOA输出态中提取信息，识别出具有最强选择偏好的子集，并基于团队定制的问题归约规则进行剪枝。此外，QARA采用了局部验证与回滚机制来辅助判断量子简化的有效性。在量子剪枝后，若剩余子集与元素集非空，则对简化后的问题再次执行经典剪枝。该交替过程循环执行直至原问题完全解决。在数值模拟中，研究人员在140个规模为8至20的子集实例上评估了单层深度QARA的性能，结果表明该算法找到精确解的概率比QAOA和递归QAOA均高出约60%，凸显了其高效性。