⚛️ 量子物理

Whither quantum advantage? New classical lower bounds for Max-Cut on large-girth 3-regular graphs

本文表明，一种经典的局部算法——变分迭代旋转算法（VIRAL）在为大圈长 3-正则图建立新的 Max-Cut 分数下界方面，表现优于量子近似优化算法（QAOA），从而将渐近下界从 0.912 提高到了 0.9127，并对量子计算在这一特定领域的优势前景提出了挑战。

原作者： Flaviano Morone, Shivang Rawat, Dries Sels

发布于 2026-10-14

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Flaviano Morone, Shivang Rawat, Dries Sels

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

在计算机科学的广袤领域中，存在着一类如此复杂的难题，以至于即使使用最强大的超级计算机，也几乎无法为大型系统找到完美解。其中一个挑战便是“最大割”（maximum cut）问题。想象一个由点和线连接的网络，其中每个点都恰好与另外三个点相连。目标是将这些点分为两组，使得跨越两组之间的连线数量尽可能多。虽然寻找绝对最佳的分组在数学上是一场噩梦，但研究人员非常感兴趣的是，不同的方法在这些网络上的表现究竟如何，特别是在这些网络被设计为避免出现小环路的情况下。这种被称为“大圈长”（large-girth）图的特定类型网络，成为了计算极限的试验场。几十年来，人们一直在探讨量子计算机（利用物理学的奇特规律来处理信息）是否能在这一特定领域比依赖标准逻辑和二进制开关的经典计算机做得更好。

一支研究团队现在向一种普遍的希望提出了挑战，即认为量子计算机在这一特定领域拥有决定性优势。通过改进一种使用简单局部规则进行决策的经典方法，他们证明了对于这些无环网络，传统的算法在特定深度下可以超越领先的量子方法。这项研究聚焦于一种名为“变分迭代旋转算法”（Variational Iterative Rotation Algorithm，简称 VIRAL）的特定算法。与试图通过复杂的概率波同时探索多种可能性的量子方法不同，VIRAL 为网络中的每个点分配一个方向，然后根据其相邻点的影响来旋转这些方向。这个过程分层进行，每一层都允许点根据邻居的新位置做出反应。研究人员在一个理论上的树状结构模型上测试了这种方法，该模型代表了具有大圈长特征网络的局部视图，这种条件迫使算法必须完全依赖局部信息，而不受远处连接的影响。

调查结果精确且令人惊讶。研究人员在代表此类无环网络中任何一点的理论树结构上运行了他们的经典算法。他们将算法推到了三十二层的深度，这比之前的测试有了显著提升。在从 p=4 到 p=32 的每一个偶数深度测试中，该经典方法产生的结果都优于量子近似优化算法（QAOA），而后者一直是这些图上量子性能的标准。具体而言，经典算法保证能够切出比量子方法更高比例的连接线，并且随着层级复杂度的增加，这种差距也在扩大。在测试的最深层，该经典方法实现了约 91.27% 的成功率，这一数字超过了此类网络之前的最佳保证。这一发现表明，对于这类特定问题，量子优势——即量子计算机能做经典计算机做不到的事情这一观点——在这些特定深度下并不存在，至少不像之前所认为的那样。

这项工作的意义在于它排除了什么，正如它证明了什么一样。曾几何时，人们认为一旦复杂度达到一定阈值，量子算法就会在这些特定网络中占据明显领先地位。这项新研究明确推翻了这种观点，针对的是在偶数深度高达 p=32 的三连通网络情况。研究人员不仅是暗示经典方法具有竞争力，他们还提供了严密的数学界限，证明在从 p=4 开始的每一个偶数深度，经典方法都严格优于量子方法。他们计算出，其结果是统计偶然性的概率小于千万分之一。此外，他们表明这种经典方法不仅是一个理论上的奇思妙想，而且是一个建设性的方法，这意味着它提供了一个标准的计算机可以遵循的清晰、逐步的配方，从而在随网络规模线性增长的时间内实现这些结果。

这一发现重塑了人们对量子计算机何时能提供优势的理解。研究表明，赋予量子计算机力量的复杂量子涨落并不总是必要的资源。在这种特定情境下，由简单的经典种子（本质上是算法的随机起始点）提供的随机性，就足以驱动系统达到比量子方法更好的解。研究人员发现，随着层数的增加，经典算法的表现持续提升，不断缩小与这些网络理论最大可能值之间的差距。虽然局部算法所能达到的确切极限仍未知，但新数据将已知的下界推向了前所未有的高度，提高了被视为经典计算可能性的底线。这项工作提醒我们，在追求计算霸权的竞赛中，最复杂的工具并不总是最有效的；有时，一个经过精心调优的经典策略可以比最先进的量子机械更胜一筹。

技术摘要：量子优势何在？针对大圈长 3-正则图 Max-Cut 问题的新型经典下界

问题定义
本文旨在解决确定 $M_g$ 的问题，即在任何圈长（girth）为 $g$ 的 3-正则图中，能够保证切分的最大边数比例。 $M_g$ 定义为所有圈长至少为 $g$ 的 3-正则图中最大切分比例的下确界。虽然渐近极限 $\lim_{g\to\infty} M_g$ 已知处于一个狭窄的区间内（ $0.912 \le \lim M_g \le 0.92386$ ），但精确的下界仍未知。

本研究的一个核心动机是比较经典局部算法与量子近似优化算法（QAOA）的表现。此前的研究表明，对于圈长 $g \ge 16$ 的 3-正则图，深度为 $p$ 的 QAOA 在可证明的保证下优于已知的最佳经典局部算法。这暗示了在适中圈长下，局部算法可能存在潜在的“量子优势”。本文研究了当应用更强大的经典局部算法到相同的理论设定时，这种优势是否依然存在。

方法论
作者在与大圈长图相关的特定几何结构上评估了变分迭代旋转算法（VIRAL），这是一种经典局部算法。

算法框架： VIRAL 为每个顶点分配一个经典的单位向量（自旋）。在 $p$ 层迭代中，这些自旋根据由邻居 $z$ 分量导出的局部场进行同步更新。其更新规则为：
$s_i(n+1) = R_x(\beta_n) R_z(\gamma_n h_i(n)) s_i(n)$
其中 $h_i(n) = \sum_{j \in \partial i} s^z_j(n)$ 。过程通过随机“种子” $\epsilon_i \in \{-1, +1\}$ 进行初始化以打破对称性，这对于在正则图上产生非平凡切分至关重要。在 $p$ 层之后，通过对自旋进行阈值处理来确定切分划分。
局部邻域分析： 作者利用了这样一个性质：在圈长 $g \ge 2p+2$ 的图中，任意一条边的半径为 $p$ 的邻域都是一个有限树（具体而言，是由两个连接的顶点组成的结构，每个顶点都根植于一个深度为 $p$ 的完全二叉树）。由于该算法是局部的，因此一条边被切分的概率仅取决于该树内的随机种子。
推导界限： 作者并未在有限的随机图上运行 VIRAL（因为随机图包含会使严格下界失效的短圈），而是直接在上述深度为 $p$ 的树上计算期望切分比例。根据 $M_g$ 的定义，如果一个局部算法在树上实现了切分比例 $c$ ，那么它能保证在任何圈长 $g \ge 2p+2$ 的 3-正则图中实现至少为 $c$ 的切分比例。因此， $M_g \ge c_{\text{VIRAL}}(p)$ 。
计算与统计： VIRAL 的参数是在随机 3-正则图上预训练得到的（如文献 [15] 所述），并保持固定。作者通过在每个偶数深度 $p \le 32$ 的树上采样 $10^7$ 个独立的种子配置来估计 $c_{\text{VIRAL}}(p)$ 。对于 $p=2$ 的情况，通过枚举所有 $2^{14}$ 种配置进行了精确计算。统计下界（ $L$ ）是在 99.99999% 的置信水平下计算的。

主要结果
本研究产生的 $M_g$ 严格下界超越了以往的记录：

优于 QAOA： 对于每一个偶数深度 $p \ge 4$ ，VIRAL 树值 $c_{\text{VIRAL}}(p)$ 均超过了文献 [4] 中报告的对应 QAOA 界限。提升幅度在 0.005 到 0.011 之间。
优于经典向量算法： 在所有 $p \ge 4$ 的深度下，VIRAL 也优于 Thompson、Parekh 和 Marwaha (TPM) [8] 的显式向量算法。
扩展了圈长范围： 研究结果将已知改进下界的圈长范围从 $g=36$ （此前 QAOA 结果的极限）扩展到了 $g=66$ 。
新的渐近下界： 在 $g=66$ （对应 $p=32$ ）时，作者在 99.99999% 的置信水平下获得了 $M_{66} \ge 0.91271$ 的严格下界。这使得已知的渐近下界 $\lim_{g\to\infty} M_g$ 从 0.912 提升至 0.9127。
收敛行为： 在 $p=32$ 时，性能增量（ $c_{\text{VIRAL}}(p) - c_{\text{VIRAL}}(p-2)$ ）仍在递减，表明尚未达到极限 $p \to \infty$ ，但算法正在向理论上限 0.92386 收敛。

意义与主张
本文声称，在针对 3-正则图 Max-Cut 问题的适中圈长下，QAOA 相对于经典局部算法表现出的所谓“量子优势”，实际上是之前用于对比的特定经典算法的产物。通过采用 VIRAL——一种利用随机种子来模拟半经典近似中量子动力学固有噪声的经典算法——作者证明了在相关的树结构上，经典方法在每个深度 $p \ge 4$ 时都能超越 QAOA。

作者得出结论，对于 3-正则图的 Max-Cut 特例，量子涨落（如 QAOA 所利用的）并不比由随机种子驱动的经典动力学提供更多的资源优势。当经典基准得到优化时，此前研究中观察到的“量子优势”便消失了。这项工作确立了在这种特定情形下优势并不存在，尽管作者指出，对于更高度数或 $k \ge 3$ （Max- $k$ -Cut）的情况是否成立仍是一个开放性问题。这些结果具有建设性，提供了一种相对于边数呈线性时间复杂度的算法来实现这些界限。

技术摘要：量子优势何在？针对大圈长 3-正则图 Max-Cut 问题的新型经典下界

类似论文