Quantum Superposition over Near Optimal Seeds for Maximum Independent Set on Dense Graphs
本文提出了一种量子变分算法，该算法利用近优种子（near-optimal seeds）的均匀叠加以及基于干涉的后选择技术，来解决高达400个节点的稠密图上的最大独立集问题，在以往方法失效的困难实例上，其表现显著优于标准的变分量子特征值求解器（VQE）和经典启发式算法。
原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
在计算机科学领域，存在一类被称为组合优化的问题，其目标是从海量的选项中找到最佳的排列方式。其中最著名的便是最大独立集（Maximum Independent Set）问题。想象一下在一个派对上的情况：人群中有些人互相认识，而有些人则互不相识。挑战在于，要邀请尽可能多的人进入一个私人房间，但前提是房间里的任何两人都不能互相认识。如果两个人认识，他们就不能同时被邀请。虽然对于规模较小的群体来说这听起来很简单，但随着人数增加，可能的组合数量会呈爆炸式增长，以至于即使是最强大的超级计算机，在面对几百人的群体时，也难以找到绝对完美的答案。这种难度使该问题成为了测试新计算技术的标准，尤其是量子计算机，它们利用量子力学的奇特规则来同时探索多种可能性。
IBM 研究院的一个研究小组开发了一种新方法来解决这类问题，特别是在处理“稠密图”（即几乎每个人都几乎认识所有人）的情况下。在这些拥挤的场景中，传统的搜索方法往往会陷入“局部陷阱”——它们能找到一个不错的解，却因为通往最优解的路径需要一系列看似无法通过逐一改变来实现的协调变化，从而错失了完美的答案。研究人员发现，通过使用量子计算机将多个“近乎完美”的解保持在叠加态（一种计算机同时考虑多种选项的状态）中，他们可以突破这些陷阱。他们的这项工作在包含多达 400 个节点的图上进行了测试，证明了这种方法可以找到最大的非相邻顶点集合，解决了令标准方法束手无策的实例。至关重要的是，他们展示了这一成功依赖于量子计算机并行探索解空间的能力，而非仅仅是改进单个起始点。
研究人员首先承认了量子计算机在处理此类问题时的一种特定弱点。标准方法通常从“白纸”开始，要求量子机器从头开始搜索整个可能性宇宙。对于稠密图而言，正确答案是如此罕见，以至于就像在沙滩上寻找一颗特定的沙粒；从白纸开始意味着计算机几乎没有任何机会偶然发现它。相反，团队决定给予一个“领先优势”。他们利用经典计算机找到了几个高质量但并非完美的解。这些解就是他们搜索的“种子”。随后，他们将这些种子编码进量子计算机中，不是一个接一个地编码，而是同时进行，创造了一个均匀叠加态。在这种状态下，量子计算机实际上是在同时将所有这些近乎最优的解置于其“脑海”之中，并将它们视为一个单一且复杂的起始点。
为了确保搜索不偏离轨道，该团队使用了一种特殊的量子电路，旨在保持“激发”计数。用该问题的语言来说，这意味着电路被严格禁止改变被邀请人数的总数。如果初始种子包含 14 个人，那么量子演化只能在这些人中进行重新排列，即通过交换一位宾客来替换另一位，但绝不能意外地邀请第 15 个人，也不能减少到 13 个人。这一约束至关重要。它让搜索聚焦在最有希望的解空间区域，防止计算机浪费时间去探索不可能或明显劣质的配置。通过固定受邀人数，电路可以在 14 人的不同组合之间进行精细的区分，寻找最接近完美答案的具体排列方式。
团队在几个困难的图上测试了这一流程，其中包括一个具有 180 个节点、其完美解涉及 15 人的挑战性实例。当他们尝试使用单个种子来解决该问题时，系统始终卡在 14 人处，无法找到通往 15 人的路径。然而，当他们使用四个不同的 14 人种子构成的叠加态时，系统实现了突破。量子计算机通过在同一套规则下共同演化这四个种子，找到了一个任何单个种子都无法独立达到的配置。最后一步是由经典计算机接收量子输出，并进行快速且智能的检查，以确认该群体是否可以扩展到 15 人。这种混合方法成功找回了经过验证的 15 人最大值，而这是单纯的经典后处理或标准的量子方法都无法单独实现的。
为了理解为什么这行得通，研究人员进行了一系列检查，以排除其他解释。他们测试了如果仅给出一个种子，经典后处理是否能找到答案，结果发现每次都失败了。他们还测试了量子电路结构本身是否是“神奇配方”，并在单个种子运行程序，结果同样卡住了。唯一的逃脱局部陷阱的方法，就是让量子计算机同时对所有种子进行优化。这证实了其力量源自并行搜索：量子计算机找到了一个能够同时改进四个起始点的参数集，有效地导航了一条对任何单一起始点而言都不可见的路径。
研究人员还探讨了叠加态中的不同分支是否可以通过相互干涉来放大最佳答案——这是一种量子波结合以增强信号的现象。他们在设计中加入了一层专门的操作来产生这种干涉，并测量了结果。虽然他们可以检测到量子交叉项的存在，但在目前的模拟中，这种效应很微弱。研究人员指出，若要使这种干涉效果更强大，不同的解需要在结构上非常相似，或者量子电路需要更深。他们发现，目前能模拟的电路深度受限于纠缠的复杂性，这表明未来需要拥有更多量子比特和更高稳定性的硬件才能充分利用这种干涉效应。
团队在真实的量子硬件上验证了他们的发现，在处理较小规模的图时，他们在配备 156 个量子比特的 IBM 处理器上运行了算法。即便面对当前设备固有的噪声和误差，该方法仍成功找回了 64、99 和 125 个节点图的最优解。这证明了该流程足够鲁棒，可以在真实设备上运行，而不只是在完美的模拟环境中。对于像 400 节点这样的大型图，由于问题规模超过了当前量子硬件的能力，团队依赖于高保真度模拟。在这些模拟中，他们发现增加量子电路的深度可以让他们找到更大的独立集，在完美答案为 27 的图中达到了 25。这表明随着量子计算机变得更加强大，这种方法将持续扩展。
这项工作凸显了量子算法设计思路的一种转变。与其试图从零开始寻找答案，最高效的策略可能是利用经典计算机寻找良好的起始点，然后利用量子计算机在这些点之间进行探索。研究人员展示了通过结合两者的优势——利用经典启发式算法寻找种子，以及利用量子叠加态在它们之间进行探索——可以解决此前无法触及的问题。虽然他们并未声称已经解决了所有可能图的最大独立集问题，但他们展示了一条清晰且可重复的路径，用于解决最难的稠密图实例，为未来的量子计算机如何应对复杂的组合挑战提供了蓝图。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。