⚛️ 量子物理

QASPA-MaxCut on Unweighted Graphs: Edge Encoding and QAOA Restarts

本文介绍了 QASPA-MaxCut，这是一种通过受控 $R_y$ 旋转来编码图边的移相电路，并通过在各种无权图上的精确模拟证明，其带有经典选择阶段的固定角度方法，即使在后者利用多次经典重启的情况下，也优于一阶 QAOA。

原作者： Dmytro Sapozhnyk

发布于 2026-11-05

📖 1 分钟阅读🧠 深度阅读

原作者： Dmytro Sapozhnyk

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

在计算科学那片寂静的角落里，科学家们正试图构建能够以不同方式思考的机器，而其中一个持久的挑战被称为 Max-Cut（最大剪切）问题。想象一下，一场派对上的一群人需要被分成两个独立的房间。目标是进行安排，使得两个房间之间的友谊数量达到最大，而不是房间内部的友谊。这个听起来简单的任务，随着人数的增加会变得异常困难，因为可能性的排列组合数量爆炸式增长，其速度超过了人类大脑所能计算的极限。几十年来，经典计算机一直是解决此类问题的最佳工具，但研究人员现在正在测试一种新型机器：量子计算机。这些设备利用亚原子世界的奇异规则来同时探索多种可能性。然而，这些早期的量子机器仍然非常脆弱且容易出错，因此科学家在要求它们解决问题时必须非常谨慎。他们不仅需要知道量子机器是否能找到一个好的答案，还需要知道达到那个答案需要付出多少努力，以及这种努力与我们目前使用的可靠计算机相比是否值得。

Dmytro Sapozhnyk 最近的一项研究通过比较两种向小型量子计算机询问如何解决 Max-Cut 问题的方法，来探讨这个问题。第一种方法是广为人知的 QAOA，它就像一个试图在浓雾弥漫的景观中寻找最高峰的徒步旅行者。徒步者迈出一步，检查高度，然后根据信息调整路径。这个过程需要大量的尝试和错误，计算机需要反复运行相同的计算，每次都从一个略微不同的猜测开始，希望能偶然发现最佳解决方案。第二种方法是作者开发并命名为 QASPA 的方法，它采取了不同的途径。它不是让徒步者在雾中徘徊，而是构建了一条特定的路径，这条路径旨在直接通往高耸的山峰。它使用一套固定的指令，这些指令不会改变，依靠问题本身的结构来引导量子机器。

研究人员在一些小型、无权重的图（本质上是点与点之间连接的地图）上测试了这两种方法。他们模拟了一个包含八个点的量子计算机的行为，这个规模足够小，可以在标准计算机上进行完美计算，从而使他们能够在没有任何噪声或误差干扰的情况下，精确观察量子机器的行为。他们以有限的尝试预算运行了“徒步者”方法 QAOA。他们从仅有一次猜测开始，并逐渐增加到十次尝试，记录每次尝试时答案是如何变得更好的。他们还仅运行了一次固定的路径方法 QASPA，使用的是一套单一且不变的指令。结果显示，这两种方法的表现存在明显差异。“徒步者”方法 QAOA 确实随着尝试次数的增加而有所改进，在寻找最佳排列的过程中缓慢攀升。然而，即使在十次尝试之后，其平均表现仍然低于新方法 QASPA 的单次固定运行结果。

QASPA 方法脱颖而出之处不在于它每次都能找到绝对完美的答案，而在于它将最好的答案放在了最可能的候选名单的最顶端。当研究人员查看 QASPA 生成的四个最可能的计算结果时，他们发现最佳的排列方式几乎总是出现在其中。事实上，对于许多测试案例，最佳排列就是那个最可能的单一结果。这意味着如果用户只需从前几个建议中挑选出最好的选项，就能获得一个极佳的结果，而无需像另一种方法那样进行复杂且耗时的搜索。研究还检查了当计算机被迫进行有限次数的测量时（模拟真实物理机的约束条件），这一结果是否依然成立。即便存在这些限制，这种固定路径的方法依然保持稳定和可靠，持续提供高质量的候选方案。

研究人员谨慎地指出，这些发现来自对极小系统的模拟，尚未证明该方法在更大的现实世界问题或真实的量子硬件上也会表现得更好。他们并未声称已经解决了所有情况下的 Max-Cut 问题，也没有暗示他们的方法是让经典计算机过时的“万灵药”。相反，他们提供了一个受控的对比，表明在这些特定的、小型实例中，将问题的结构直接嵌入到量子指令中，比依赖重复搜索过程更为高效。这项研究表明，通过设计尊重问题特定形状的量子电路，我们或许能够以更少的努力获得更好的结果，即使是在当今并不完美的机器上也是如此。这一洞察为未来的研究提供了一个新方向，指向了一种可以减少对不断调优的依赖，而更多专注于试图解决的问题之内在几何结构的量子算法构建方式。

技术摘要：针对无权图的 QASPA-MaxCut

问题陈述
本文探讨了量子近似优化算法（QAOA）在含噪声中等规模量子（NISQ）时代的性能瓶颈。虽然 QAOA 是组合优化（特别是 Max-Cut 问题）的一种经典的变分方法，但其报告的性能高度依赖于对变分参数的经典外层循环优化。在实际应用中，有限的门深度、噪声以及重复评估电路的计算成本限制了寻找最优参数的能力。作者旨在通过将标准的一层深度 QAOA 与一种新的电路构造——QASPA-MaxCut 进行对比，来隔离经典搜索预算的影响。QASPA-MaxCut 通过将图结构直接嵌入到电路算符（ansatz）中，以减少对参数调优的依赖。

方法论
本研究引入了 QASPA-MaxCut，这是一种针对无权图设计的移相电路（shift-phase circuit）。与标准 QAOA 交替使用全局问题幺正算符（ $e^{-i\gamma H_C}$ ）和全局横向场混合器（ $e^{-i\beta \sum X_i}$ ）不同，QASP 采用局部于边的受控旋转来取代全局混合器。

电路构造： QASPA 算符以哈达玛层（Hadamard layer）开始以创建均匀叠加态。对于图中的每条边 $(i, j)$ ，应用一个特定的模块： $CX_{i,j} R_y^{(j)}(\theta_{ij}) CX_{i,j}$ 。
边编码： 在无权情况下，旋转角 $\theta_{ij}$ 被全局固定为 $\alpha = \pi/4$ 。该模块在代数上作用于 $\exp(-i \frac{\alpha}{2} Z_i Y_j)$ ，它是在特定的边对之间重新分配“切割”与“未切割”配置之间的振幅，而非应用一个对角相位。
实验方案：
- 图：研究使用小规模实例（ $n=8$ 个顶点）进行精确态矢量模拟。图包括连接骨干增强的随机图（具有额外的边概率 $p_{edge} \in \{0.1, 0.3, 0.5, 0.7\}$ ）和 19 个手工指定的自定义拓扑结构。
- QAOA 基准： 使用局部 Nelder-Mead 优化器对一层深度 QAOA 电路进行优化。性能通过“ $k$ -中最佳”（best-of- $k$ ）曲线进行衡量，其中 $k$ 代表独立随机重启的次数（范围从 1 到 10）。
- QASPA 评估： QASPA 使用固定角度 $\alpha = \pi/4$ 运行，无需外层循环搜索。报告的得分是经典选择率：即算法选择输出概率最高的四个比特串，根据 Max-Cut 目标函数进行评估，并报告这四个中找到的最佳切割。
- 读出： 对于自定义拓扑结构，使用自适应采样预算（ $N_{shots} = \lceil 0.03047 \cdot 2^n + 1016.2 \rceil$ ）进行有限采样读出检查，以验证在采样噪声下的稳定性。

核心贡献

代数推导： 本文提供了 QASPA 边模块的精确双比特代数推导，展示了 $CX-R_y-CX$ 序列如何重新分配振幅，从而有效地将边结构嵌入到混合步骤中。
工作示例： 提供了一个完整的、可追溯的四顶点无权图数学与数值演练过程，详细说明了边调度、状态演化和输出概率，以验证该构造。
受控对比： 本研究建立了一个可重复的实验框架，将固定角度、嵌入结构的电路（QASPA）与具有透明经典搜索预算的变分基准（QAOA）进行对比。这隔离了“重启效应”，以确定为了竞争过固定角度方法需要多少经典优化。

结果

候选质量： 在测试的小规模实例中，固定角度的 QASPA 态将最优（或近优）的 Max-Cut 解置于前四个最高概率的比特串中。因此，QASPA 的经典选择率极高，在各组图中范围在 0.955 至 1.000 之间。
QAOA 敏感性： 一层深度的 QAOA 性能对经典重启次数高度敏感。虽然期望近似比随重启次数增加而提高（例如，对于稀疏图从 ~0.71 升至 ~0.79），但在测试的 10 次重启预算内，其表现始终低于 QASPA 的选择得分。
稳定性： 在自定义拓扑结构上的有限采样读出检查显示，在规定的采样预算下，QASPA 选择得分保持稳定（均值为 1.000，标准差为零），证实了这些特定实例下候选选择规则的鲁棒性。
边顺序敏感性： 研究指出，由于非对易的边模块，QASPA 并非顺序无关的。然而，在测试中对边顺序进行随机排列得到的组均值与规范固定顺序的值接近，表明其在小规模测试中具有一定的韧性。

意义与主张
本文提出了适度且受控的主张，而非断言渐近优越性或硬件统治地位。主要发现是：对于小型无权图，固定的角度 QASPA 电路可以在无需昂贵的外层循环参数搜索的情况下，生成包含高质量 Max-Cut 解的候选集。相比之下，标准的单层 QAOA 需要显著的经典优化预算（多次重启）才能接近类似的性能水平，即使如此，在报告的均值中也无法超越 QASPA 的选择得分。

作者将此视为一种证明，即通过将实例结构直接嵌入到电路算符中（通过局部于边的混合），可以减轻对经典参数调优的负担。这项工作作为理解在浅层深度下电路结构与经典搜索预算之间权衡的基础。本文明确避免了关于向更大规模 $n$ 扩展、处理加权图或在噪声硬件上表现的行为的断言，并将这些识别为在得出面向硬件的结论之前必要的后续步骤。

类似论文