一种变分的节省量子比特的 MaxCut 启发式算法

为什么小型量子芯片对大难题很重要

许多现实任务——从布置计算机电路到模拟材料——归结为将一个网络分成两组，同时尽可能多地切断组间连接。这个问题称为 MaxCut，对传统计算机来说是出了名的困难。本文介绍了一种新的量子启发方法，能够用少量量子比特（qubit）处理出人意料的大型网络，为测试和改进量子与经典优化工具提供了一种新途径。

把网络切成两个有用的部分

MaxCut 提出了一个听起来很简单的问题：如果有一组点（节点）由线（边）连接，你应该怎样为每个节点着色，比如蓝色或白色，以便尽可能多的边连接不同颜色的节点？这个最优分割在电路设计和统计物理等领域很有价值，但当网络很大时很难准确求解。一个被广泛使用的经典方法是 Goemans–Williamson（GW）算法，它对问题做了巧妙的松弛，能保证找到的割至少约为最优值的 88%。量子计算承诺提供新的攻关手段，但当前设备噪声多且规模受限，难以运行大型深度电路。

仅用少量量子比特解决大图

标准量子方法如量子近似优化算法（QAOA）通常需要每个网络节点对应一个量子比特，因此一个 1000 节点的图需要 1000 个量子比特——远超当今设备。新方法称为节省量子比特的 MaxCut（QEMC），颠覆了这一规模关系：它只需大约节点数的对数个比特，这意味着 11 个量子比特就能编码超过 2000 个节点的信息。QEMC 不将每个量子比特绑定到单个节点，而是把整个量子态作为紧凑的寻址空间，让不同节点对应这个小寄存器的不同基态。这种量子比特节约使电路保持浅层，更易在噪声硬件上运行，同时仍能表示非常大的图。

用概率而非固定态为节点着色

关键创新在于 QEMC 如何编码每个节点的“颜色”。它不是在单一量子态中强制每个节点恰好为蓝或白，而是让每个节点的颜色通过测量时被观测到的概率来推断。若某基态出现概率低，则将该节点视为一种颜色；出现概率高则视为另一种颜色。一个阈值将两种情形分开。这意味着许多不同的量子态本质上对应相同的图划分。QEMC 惩罚函数的构建鼓励相连的节点落入概率阈值的两侧，从而倾向于增加跨两种颜色组的边数，进而改善割的质量。

在真实与模拟设备上测试性能

作者在两方面测试了 QEMC：真实量子处理器和对量子电路的经典模拟。在最多 32 个节点（仅用 2 到 5 个量子比特）的规则小图上，运行在 IBM 超导硬件上的 QEMC 找到的割与穷举搜索出的最优解匹配或接近，明显优于随机猜测和早期基于 QAOA 的量子研究。在无噪声的模拟中，QEMC 对这些小图持续能达到超过 97% 的最优割。对于更大的图，这种编码的威力更加明显：对最多 2048 个节点的 9-正则图的经典模拟表明，QEMC 在平均值和最好割上仍比 GW 优出几个百分点，在不同密度的 128 节点随机图上也观察到类似优势。

速度、局限与量子启发的前景

尽管取得了成功，QEMC 目前还没有给出形式上的量子加速证明。因为它只使用约 log N 个量子比特，所以其电路的经典模拟大致随节点数线性扩展，评估代价函数所需时间随边数增长。经验研究表明，达到 GW 水平性能的总体时间约随图规模呈二次增长，但对于许多问题仍在实际可及范围内。这意味着 QEMC 在当前形式下更像是一个强大的量子启发式算法，而不是量子优越性的证明。

这项工作对未来的意义

对非专业读者而言，主要信息是：如果我们设计与设备优势相匹配的算法，小而有噪声的量子设备仍然可以在科学上有用。通过将节点颜色编码为灵活的概率范围而非僵硬的比特值，QEMC 使用极少量的量子比特来处理非常大的网络问题，并自然容忍硬件噪声。该方法为测试量子优化算法设立了新基准，同时也产生了基于相同思想的实用经典算法。更广泛地说，它展示了如何通过重新思考信息的编码方式——而不是仅仅制造更大的机器——为解决困难的计算问题开辟有希望的路径。

引用: Tene-Cohen, Y., Kelman, T., Lev, O. et al. A Variational Qubit-Efficient MaxCut Heuristic Algorithm. npj Quantum Inf 12, 50 (2026). https://doi.org/10.1038/s41534-026-01186-2

关键词: MaxCut, 量子优化, 变分算法, 图划分, 量子启发计算