← 最新论文
⚛️ 量子物理

Recursive Quantum Alternating Operator Ansatz

本文通过识别在变量消除下封闭的更广泛问题类,并构建高效的保持可行性的混合器,将递归量子近似优化算法扩展到受限组合问题,从而实现了针对背包问题等任务的递归优化,其表现优于非递归和基于惩罚项的方法。

原作者: Lennart Binkowski, Stuart Flannigan

发布于 2026-11-16
📖 1 分钟阅读🧠 深度阅读

原作者: Lennart Binkowski, Stuart Flannigan

原始论文采用 CC BY 4.0 许可(http://creativecommons.org/licenses/by/4.0/)。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性,请参阅原始论文。 阅读完整免责声明

在探索解决世界上最棘手难题的过程中,科学家们转向了一种新型机器:量子计算机。与我们口袋里那些以简单的零和一作为信息流进行处理的设备不同,这些机器利用奇特的物理定律,同时保持多种可能性处于叠加态。这使得它们能够同时探索广阔的解空间,为那些经典计算机需要数千年才能破解的问题提供了一条潜在的捷径。在这些机器最受期待的工具中,有一种被称为“量子近似优化算法”(Quantum Approximate Optimization Algorithm)的算法。可以将其想象为一种引导式搜索:计算机准备一个量子态,测量它与问题的契合程度,然后调整其设置,以接近最佳答案。然而,现实世界中的问题很少是自由漫游的;它们受限于严格的规则或约束。一辆送货卡车的载重不能超过其引擎的承受能力,而一个社交网络中的朋友关系也不能包含两个拒绝交谈的人。当这些规则变得难以处理时,标准的搜索方法往往会失败,要么迷失在无数不可能的解中,要么需要使用笨拙的变通方法来削弱其效能。

一组研究人员现在开发出了一种让这些量子搜索变得更聪明、更有纪律的方法,专门针对带有硬性规则的问题。他们采用了现有的名为“递归量子近似优化算法”(Recursive Quantum Approximate Optimization Algorithm)的策略,该策略通过将一个大问题反复分解为更小、更简单的版本来解决问题。过去,这种方法在处理没有规则的问题时表现良好,但在面对约束时却会陷入困境。每当算法试图通过固定一个变量来简化问题时,复杂的规则网就会扭曲成一种新的、无法识别的形状,导致计算机的工具无法再对其进行处理。研究人员意识到,为了让搜索保持在轨道上,他们不能再试图强行将每个简化后的问题都塞回原来的框架中。相反,他们构建了一个更宽泛的新框架,接受这些变化的形状作为过程中的自然步骤。

他们发现的核心在于一套新的指令,允许量子计算机在这些变化的景观中航行,而绝不会踏出有效解的领域之外。他们设计了一个系统,在每一次简化的步骤中,计算机都会准备一个保证有效的全新起点,并使用一套特殊的移动方式,仅在有效选项之间进行切换。这确保了计算机永远不会浪费时间去探索不可能的情景。研究人员在两种困难的问题类型上测试了这种方法:一个是背包问题(涉及选择物品以最大化价值且不超过重量限制),另一个是图划分问题的变体(其中节点必须被分为权重相等的两组)。在他们的模拟实验中(这些实验在经典计算机上运行,以完美模拟量子行为),这种新方法始终优于旧技术。它找到了比标准非递归方法更好的解,并且远超那些试图通过添加惩罚项来处理规则的方法,因为后者往往会让计算机在有效与无效答案的混合中感到困惑。

这项工作的特别之处在于它如何处理问题分解时不可避免的变化。当算法固定一个变量或合并两个变量时,约束的数学结构也会发生变化。例如,一个关于总物品数量的简单规则可能会转化为一个关于加权和的更复杂的规则。以往的方法试图将这些新规则强行套回旧格式,这往往会导致失败。而新方法则识别出了一类更广泛的、无论问题如何简化都能保持稳定的规则。他们创建了一个动态程序——一个与量子过程同步运行的经典计算过程——来绘制每一步简化后问题的有效移动路径。这张地图告诉量子计算机如何从一个有效解移动到另一个有效解而不破坏规则,同时也识别出哪些变量已经被强制设定为特定值,从而让计算机忽略它们,将力量集中在剩余的未知量上。

研究人员证明,该方法对于包括背包问题以及涉及等式和不等式的各种约束,都能高效运作。他们表明,只要规则涉及的数值不是天文数字,计算机就能快速生成这些地图。然而,他们也划定了一条明确的界限:如果规则变得过于复杂或数值过大,寻找有效起点的任务对于任何高效计算机来说都将变得不可能,这是由这些问题的本质属性所决定的。他们的模拟实验涉及了多达二十四个变量的问题,结果显示,将这种对规则的严格遵守与递归分解策略相结合,可以产生更优的结果。新方法不仅找到了更高质量的解,而且通过将量子态完全聚焦在可行域内,避免了陷入惩罚制方法中常见的无效解漂移现象。

这项工作代表了我们在如何利用量子硬件解决受约束问题方面的思维转变。研究人员不再将约束视为需要用惩罚项来修补的麻烦,而是将其融入了算法运动的织理之中。通过接受问题在简化过程中会改变形状这一事实,并构建能够适应这些新形状的工具,他们为寻找最优解开辟了一条更稳健的路径。结果表明,对于规则严格且搜索空间巨大的问题,这种递归式、具备约束感知能力的算法提供了明显的优势。尽管模拟是在无噪声的完美环境下进行的,但这种改进在不同问题类型和规模上的连贯性,指向了该方法真实的强大之处。它为未来的量子算法如何应对物流、调度和资源分配等充满规则约束的复杂挑战提供了一个蓝图,将现实世界的刚性约束转化为指引而非障碍。

您所在领域的论文太多了?

获取与您研究关键词匹配的最新论文每日摘要——附技术摘要,使用您的语言。

试用 Digest →