⚛️ 量子物理

Analog quantum approximate optimization algorithm for solving the weighted MaxCut problem on three-dimensional single-atom Rydberg array

本文从理论上证明，在三维里德堡原子阵列上实现的模拟量子近似优化算法，通过结合离散量子退火与图神经网络热启动初始化的组合优化策略，即使在现实的误差模型下，也能在求解加权最大割问题时优于经典的 Goemans-Williamson 算法。

原作者： Junxi Chen, I. I. Beterov

发布于 2026-11-11

📖 1 分钟阅读🧠 深度阅读

原作者： Junxi Chen, I. I. Beterov

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

在计算领域，有些问题是极其难以解决的。它们属于被称为 NP-hard 的一类问题，在这种问题中，寻找完美答案的难度会随着问题规模的增长而呈指数级上升，甚至对于最强大的超级计算机来说，其耗时也可能超过宇宙的年龄。其中一个谜题便是加权最大割问题（weighted maximum cut problem）。想象一个由点和线连接的网络，每条线都有一个特定的数值。目标是将这些点分为两组，使得连接这两组的线的总价值尽可能高。这项任务不仅仅是一个数学上的好奇心；它支撑着诸如设计高效芯片、组织数据聚类以及规划网络基础设施等现实世界的挑战。由于寻找完美解非常困难，科学家们依赖于被称为近似算法的巧妙捷径。几十年来，由 Goemans 和 Williamson 开发的一种经典方法一直是行业金标准，它保证了所获解至少能达到完美答案的 87.8%。

最近，一个新兴领域正试图利用量子力学的奇异法则来应对这些难题。传统的量子计算机通常通过串联一系列精确的逻辑门来尝试解决问题，而量子计算机使用不再仅仅是零或一的标准比特，而是可以同时存在于多种状态叠加中的量子比特。一种极具前景的方法是量子近似优化算法（QAOA）。虽然传统的量子计算机通常尝试通过一系列逻辑门来解决问题，但一种更新颖的“模拟”版本允许量子系统在激光脉冲的影响下自然演化。本文探讨了这种模拟方法的一种特定且高级的版本，该方法使用在真空中被捕获的三维原子网格。这些原子被激发到一种被称为里德堡态（Rydberg state）的高能态，在此状态下，它们彼此之间会产生强烈的相互作用。研究人员想要观察这种物理设置是否能比目前最好的经典方法更好地解决加权最大割问题，以及在面对现实世界设备中固有的噪声和误差时，如何使其可靠地运行。

研究人员首先通过设计一个包含二十个随机网络（每个网络包含十二个点）的模拟实验开始了工作。他们将这些网络映射到一个三维原子物理网格上，通过在三维空间中排列原子，使得任意两个原子之间的距离决定了它们相互作用的强度。通过精心布置原子，他们将问题的特定数值直接编码进粒子间的物理作用力中。如果问题中的两个点需要强连接，对应的原子就会被放置得较近；如果需要弱连接，则放得较远。这种方法使他们无需额外的“辅助”原子或复杂的技巧，而是依靠系统的自然物理特性来解决问题。随后，他们通过一系列激光脉冲引导量子系统，测试了两种不同的策略以引导系统走向最优解。

第一种策略被称为“冷启动”（cold start），它从所有原子处于中性状态开始，并让系统通过一系列步骤进行演化。研究人员发现，系统所走的路径至关重要。如果他们只是简单地让计算机优化器逐层选择最佳设置而不加引导，系统就会陷入一条看起来在初期表现良好、但随着过程推进却无法持续改进的路径。这条路径导致的解仅为完美答案的 77% 左右。然而，通过添加一个简单的物理约束——限制某些激光脉冲持续的时间长度——他们迫使系统走上了另一条路径。这条新路径的行为类似于一种缓慢、细致的冷却过程，即退火（annealing）。在这条路径上，随着他们增加更多的层数，解的质量不断提高，最终达到了 95.9% 的得分，在大多数测试案例中超越了经典的黄金标准。

第二种策略被称为“热启动”（warm start），它试图给量子系统一个领先优势。在激光脉冲开始之前，研究人员使用了一种名为图神经网络（graph neural network）的特定人工智能程序，来猜测一个良好的初始排列。然后，他们准备了与这一猜测相匹配的原子状态。这种方法效果很好，但前提是初始猜测必须是正确的。当神经网络的猜测正确时，量子系统能非常迅速地将其精炼为近乎完美的解。然而，当神经网络的猜测错误时，量子系统往往会卡在那个错误的答案附近，无法找到真正的最优解。这揭示了一个关键洞察：两种策略在不同情况下会失效。冷启动方法在物理原子排列不完美时表现挣扎，而热启动方法则在人工智能提供的初始猜测较差时表现挣扎。

为了兼顾两者的优点，研究人员将这两种方法合并为一个组合方案（portfolio）。对于每个问题，他们同时运行冷启动和热启动版本，并简单地选择更好的结果。在完美的无噪声模拟中，这种组合策略在二十个测试案例中的十九个中都优于经典黄金标准。然而，当针对现有的量子处理器 Aquila 进行现实误差模型测试时，结果发生了变化。在这种充满噪声的环境中，运行长序列带来的优势消失了。那种在模拟中表现出色的深度退火路径变得过于脆弱，随着序列变长，系统无法维持其质量。在这些噪声条件下，表现最好的方案是短促的热启动方法，它仅需几个步骤和极短的激光脉冲。然而，即使是这个短序列版本，在噪声模拟中也未能击败经典黄金标准；它仅在 16% 的尝试中得到了最优切分，不到单次 Goemans–William way 舍入法的一半。

研究结论指出，尽管模拟量子方法在超越经典算法方面具有巨大潜力，但实现这一潜力的道路并非坦途。那些提供最高理论性能的深度退火类序列，目前对于现有硬件中的误差过于敏感。目前最有效的即时策略似乎是混合型方案：利用简短且智能的初始猜测来引导系统，或者并行运行多种策略并选取胜者。研究人员发现，要使深度高性能序列变得可行，量子处理器的误差率需要降低大约一个数量级。在此之前，使用这些机器最实际的方法是结合不同的策略，利用短序列的速度和多策略并行运作的力量，来应对复杂难题的景观。

技术摘要：基于 3D 里德堡原子阵列的加权 MaxCut 模拟量子近似优化算法

问题陈述
本研究针对加权最大割（Weighted MaxCut）问题，这是一个基础性的 NP-难组合优化问题，在 VLSI 设计、数据聚类和网络基础设施等领域有广泛应用。该问题涉及将图 $G=(V, E, w)$ 的顶点划分为两个不相交的集合，以最大化连接这两个集合的边权重之和。作者专注于使用三维（3D）独立捕获的里德堡原子阵列，通过模拟量子近似优化算法（QAOA）的模拟实现来解决这一问题。不同于以往通常依赖平面晶格或辅助“小部件”（gadget）构造来嵌入任意图的方法，本研究利用里德堡原子阵列天然的 3D 几何结构来直接编码边权重。

方法论
所提出的方案利用了由 $N=12$ 个超冷 $^{87}$ Rb 原子组成的 3D 阵列，这些原子被激发至里德堡态（ $|70S_{1/2}\rangle$ ）。该系统受随时间变化的哈密顿量控制，其中范德华相互作用（ $V_{ij} \propto 1/r_{ij}^6$ ）提供了可编程的双体伊辛耦合（Ising couplings）。

图嵌入： 作者将加权 MaxCut 问题直接映射到物理系统中。通过将原子放置在特定的距离 $r_{ij}$ 处，从而编码边权重 $w_{ij}$ ，使得相互作用能 $V_{ij}/4$ 与期望的权重相对应。非相邻原子也会发生相互作用，但这些“非边”耦合被视为系统动力学的一部分而非被消除。
哈密顿量与脉冲序列： 系统在随时间变化的哈密顿量 $H(t) = \sum_i \frac{\Omega_i(t)}{2}(e^{i\phi}|g\rangle\langle r| + h.c.) - \sum_i \Delta_i(t) n_i + \sum_{i<j} V_{ij} n_i n_j$ $H (t) = \sum_{i} \frac{Ω _{i} ( t )}{2} (e^{i ϕ} ∣ g ⟩ ⟨ r ∣ + h . c .) - \sum_{i} Δ_{i} (t) n_{i} + \sum_{i < j} V_{ij} n_{i} n_{j}$ 下演化。
- 准备阶段： 全局脉冲准备初始态（对于冷启动为 $|+\rangle^{\otimes N}$ ，对于热启动为特定的乘积态）。
- 代价段（Cost Segments）： 驱动关闭（ $\Omega=0$ ）的阶段，在代价哈密顿量 $H_C$ 下演化（利用基于位点相关失谐 $\Delta_i$ 的伊辛模型来抵消由范德华相互作用产生的单点项）。
- 混合段（Mixer Segments）： 全局驱动或位点解析驱动激活的阶段，提供横向场分量。
优化策略： 研究比较了两种优化脉冲参数（持续时间 $\gamma_k$ 和 $\beta_k$ ）的方法：

*   **冷启动（Cold Start）：** 从均匀叠加态  $|+\rangle^{\otimes N}$  开始初始化。
*   **热启动（Warm Start）：** 使用基于图神经网络（GNN）预测的顶点边际概率生成的乘积态进行初始化。这需要位点解析的拉比频率和特定的失谐偏移，以确保初始态是混合算符的本征态。

模拟与验证： 作者使用 Krylov 传播法（Arnoldi）和一个量子轨迹求解器来模拟系统，以模拟“Aquila”中性原子量子处理器。该误差模型包括准静态激光噪声、原子位置波动、退相干、自发衰减以及检测误差。

主要结果
研究评估了 20 个随机生成的具有 12 个顶点的 3-正则图。

优化景观（Optimization Landscapes）： 作者在优化景观中识别出两个截然不同的分支。标准的逐层优化器往往会陷入“非绝热分支”（Basin B），在该分支中，近似比（ $R_a$ ）饱和在 0.77 左右。通过施加限制代价段持续时间的物理约束（ $\gamma_k \leq 1 \mu s$ ），优化器会被引导至“退火分支”（Basin A）。在该分支上， $R_a$ 随深度 $p$ 单调增加，在 $p=20$ 时达到 $0.959$。
与经典算法的比较：
- 在无噪声机制下，经过优化的退火分支（ $p \geq 16$ ）在期望割值方面优于 Goemans-Williamson (GW) 舍入算法。
- 然而，GNN 热启动协议在统计上与 GW 算法不可区分（例如，在 $p=10$ 时，平均差值为 $-0.006 $，且$ P=0.76$）。
- 一种组合策略（Portfolio Strategy）——即针对每个实例在冷启动退火分支和热启动协议之间选择较优结果——实现了平均 $R_a$ 为 $0.966 $，在 20 个实例中有 19 个实例超过了 GW。然而，该组合相对于 GW 的平均差值在统计上并不显著（$ P=0.45$），且该组合并不显著优于 GNN 自身的舍入结果。GNN 舍入作为一个强大的经典参考，在期望值方面通常优于量子协议，特别是在网络初始猜测接近最优的实例中。
- GNN 热启动在网络初始猜测接近最优时非常有效，但在 GNN 预测较差时会失效（集中在次优的字符串上）。相反，冷启动退火分支对 GNN 的失败具有鲁棒性，但需要更深的电路。
噪声分析： 在使用 Aquila 处理器的现实误差模型进行模拟时：
- 深层电路的优势随之减弱：退火分支的最优深度从 $p=20$ 降至 $p=5$ 。
- 浅层深度的热启动协议（ $p=3$ ）成为最稳健的单一协议，优于带噪声的退火分支。
- 至关重要的是，组合策略的价值随着噪声水平的增加而丧失。当噪声缩放因子 $\lambda \geq 1$ （代表当前硬件能力）时，热启动在每个实例上都是较优的成员，实际上使组合策略退化为仅剩热启动。只有在显著较低的噪声水平（ $\lambda \approx 0.1$ ）下，组合策略才能保留其互补价值。
采样统计： 虽然期望值有所提高，但在小深度下，单次测量得到精确最优割的概率（ $P_{opt}$ ）仍低于重复进行 GW 舍入。然而，在特定机制下，量子协议显示出在较少采样次数内找到高质量割的潜力，优于经典的采样方式。

意义与主张
本文谦逊地声称展示了基于里德堡原子的模拟 QAOA 在处理加权 MaxCut 时，无需使用基于小部件嵌入的开销。其主要贡献在于：

直接 3D 嵌入： 证明了 3 维原子阵列可以通过调节原子间距来直接编码任意加权图，从而避免了对辅助比特的需求。
景观分析： 识别出在深度 $p=1$ 时选择局部最优解的“贪婪”选择可能会导致次优的全局表现（非绝向分支），而通过简单的物理约束限制脉冲持续时间可以将优化器引导至更优的、类绝热的轨迹。
混合策略： 展示了将用于热启动的经典启发式方法（GNN）与量子退火分支相结合，可以创建一个在无噪声极限下比其中任何一种方法都更稳健的组合，有效地覆盖了各自的弱点。然而，这种优势是依赖于低噪声水平的；在当前硬件噪声下，组合策略会坍缩为热启动协议。
噪声韧性： 提供了一个现实的评估，即虽然当前的硬件噪声限制了深层电路的优势和组合策略的效用，但浅层深度的热启动协议仍能在期望值方面优于经典基准，前提是管理好误差率。

作者总结道，虽然目前的噪声水平阻碍了实现深层退火分支和组合策略的全部潜力，但在无噪声极限下观察到的性能以及热启动协议的稳健性，表明随着硬件保真度的提高，这是一条可行的路径。

类似论文