Performance analysis of classical adiabatic annealing on Ising machines

本文通过连续延拓法分析了伊辛机上的经典绝热退火，并提出了一种混合策略，但结论指出，尽管具有理论动机并在特定问题上取得了微小改进，但该方法相比现有的更简单技术仍缺乏足够的实际优势。

要点

大局观：在崎岖的山脉中航行

想象一下，你正试图在一座巨大且雾气缭绕的山脉中寻找最低点。这就是计算机在尝试解决复杂优化问题（例如寻找最高效的送货路线或最佳的工厂调度方案）时所做的事情。在物理学世界中，这个“最低点”被称为基态 (ground state)，而这座山脉就是能量景观 (energy landscape)。

伊辛机 (Ising Machines) 是专门为解决这类问题而设计的特殊计算机。它们不使用标准的数字比特（0 和 1），而是使用“自旋”，你可以把它们想象成可以指向向上或向下的微型指南针。目标是让所有这些指南针都稳定在一个代表绝对最低能量的模式中（即最佳解决方案）。

然而，这些山脉充满了局部极小值 (local minima)——即那些看起来像是谷底、但实际上并不是的地方。如果计算机卡在其中一个微小的谷底，它会误以为自己找到了最佳答案，但其实并没有。

旧方法：“常规退火” (Regular Annealing)

为了帮助计算机逃离这些小谷底，科学家们使用了一种叫做常规退火 (Regular Annealing, RA) 的技术。你可以把它想象成徒步旅行者在慢慢调整他们的背包。

• 徒步者开始时负重很轻（指南针之间的相互作用很弱）。
• 随后，他们慢慢增加重量（增加相互作用）。
• 其核心思想是，通过缓慢移动，徒步者可以沿着坡度“滑动”，从而避免陷入错误的谷底。

这种方法效果不错，但研究人员想看看是否能做得更好。

新想法：“经典绝热退火” (Classical Adiabatic Annealing, CAA)

研究人员借鉴了一种受量子物理启发的名为绝热退火 (Adiabatic Annealing) 的技术。

• 类比： 想象你有一张简单平缓的小山地图（一个简单的问题）。你知道底部的确切位置。现在，你想把这座平缓的小山变成你实际需要解决的那个复杂且崎岖的山脉（一个难题）。
• 方法： 你从这座平缓的小山开始。慢慢地，你改变小山的形状，使其演变成复杂的山脉。如果你做得足够慢，徒步者（计算机）应该能始终沿着最低点的路径行进，最终到达复杂山脉的真正底部。

研究人员在经典伊辛机（非量子类）上尝试了这种方法。他们称之为经典绝热退火 (Classical Adiabatic Annealing, CAA)。

问题所在：“悬崖” (鞍点分叉/Saddle-Node Bifurcations)

当他们进行测试时，发现了一个重大障碍。随着他们缓慢地将平缓的小山演变成复杂的山脉，徒步者遵循的路径突然消失了。

• 隐喻： 想象徒步者正在一条狭窄的山脊上行走。随着地形的变化，山脊突然在悬崖处（即“鞍点分叉”）中断。徒步者从路径上跌落，掉进了一个随机且错误的谷底。
• 原因： 这是因为“相互作用强度”（指南针之间互相影响的程度）过高。当景观发生变化时，路径断裂了。

解决方案：“混合式经典绝热退火” (Hybrid Classical Adiabatic Annealing)

为了修复这个问题，研究人员发明了一种名为 Hybrid CAA 的两步策略。

第一步：“幽灵”行走（低相互作用）
首先，他们将相互作用强度降低到几乎为零。

• 为什么？ 当相互作用非常微弱时，“悬崖”就会消失。路径变得平滑且连续。徒步者可以从起点走到终点而不会跌落，尽管由于相互作用太弱，此时还无法定义真正的解，所以最终目的地还不完全正确。

第二步：“重载”行走（高相互作用）
一旦徒步者到达了路径的终点（目标山脉的形状），他们就会切换到第二阶段。

• 行动： 他们慢慢增加相互作用强度（把重量重新加回背包）。
• 结果： 因为他们已经非常接近正确的位置，所以现在可以“沉降”到山脉真正的最低点，而不会掉下悬崖。

效果如何？实验结果

研究人员在数千个问题上，将这种新的“混合”方法与旧的“常规”方法进行了对比测试。

1. 对于简单问题（无外场）：

   • 混合方法的运行速度略快于常规方法。
   • 代价： 它只快了那么一点点（约 1.6 倍）。研究人员得出结论，管理这个两步过程所带来的额外复杂度，并不值得这点微小的速度提升。这就像是为了省下 2 分钟车程而去买一个昂贵且复杂的 GPS 一样，并不划算。

2. 对于复杂问题（有外场）：

   • 最初，混合方法看起来表现出色，解决某些问题的速度比常规方法快了多达 100 倍。
   • 转折： 然而，他们意识到“常规”方法还有一个尚未使用的秘密武器：自旋符号法 (Spin Sign Method)。这是一种技巧，计算机通过这种方式忽略指南针的具体大小，只关注它的指向（向上或向下）。
   • 最终定论： 当他们将这个技巧应用到常规方法中时，常规方法追了上来。混合方法失去了优势。两种方法的表现几乎完全相同。

结论

论文总结道，虽然 Hybrid Classical Adiabatic Annealing 是一个聪明且在理论上成立的想法，有助于计算机避免陷入困境，但它并不具备显著的实际优势，无法超越现有的更简单的方法。

• 它需要更复杂的设置（需要调节更多的参数）。
• 它要求计算机能够实现全连接（即每个部分都能与其它所有部分连接），这在实际硬件构建中是非常困难的。
• 一旦你在简单方法中使用了最好的现有技巧，这个高级的新方法并不会胜出。

简而言之： 这个新方法是一个优秀的科学发现，有助于我们理解这些机器的工作原理，但对于解决当今现实世界的问题，原本那些更简单的旧方法同样好用，而且更容易使用。

技术摘要

技术摘要：经典绝热退火在伊辛机上的性能分析

问题陈述
伊辛机（Ising Machines, IMs）是旨在解决组合优化问题（COPs）的启发式求解器，其原理是将问题映射到伊辛模型上，目标是寻找相互作用二元自旋的低能构型。尽管存在多种不同的伊辛机实现方式，但在这些系统中导航复杂的能量景观以避免局部极小值仍然是一个重大挑战。经典绝热退火（Classical Adiabatic Annealing, CAA）被提出作为一种改进此类导航的启发式方法，通过将系统的哈密顿量从易于求解的初始状态逐渐转化为目标问题哈密顿量来实现。然而，CAA 在经典模拟伊辛机上的有效性尚未得到系统性的基准测试，其所谓的成功很大程度上是基于与量子绝热退火的类比，而非严谨的经典分析。本研究旨在分析 CAA 的性能，识别其内在局限性，并提出一种优化策略。

方法论
作者研究了经典模拟伊辛机上的 CAA，其中自旋由连续变量 $s_i \in \mathbb{R}$ 表示，并根据涉及线性增益 ($\alpha$)、相互作用强度 ($\beta$) 和噪声的微分方程进行演化。研究采用了两种主要的分析工具：

1. 延拓分析（Continuation Analysis）： 使用 auto-07p 软件包，作者追踪系统不动点随插值参数 $F$（用于混合初始耦合矩阵与目标耦合矩阵）从 0 到 1 变化的过程。这使得他们能够可视化基态的轨迹并识别分叉现象。
2. 数值模拟： 作者对伊辛机动力学进行了随机模拟（通过对包含高斯噪声的演化方程进行积分），以评估性能指标：成功率（Success Rate, SR）和达到目标时间（Time-to-Target, TTT）。

研究对比了两种策略：

• 常规退火（Regular Annealing, RA）： 一种标准方法，在运行过程中逐渐增加耦合强度 $\beta$ 或线性增益 $\alpha$。
• 混合经典绝热退火（Hybrid Classical Adiabatic Annealing, Hybrid CAA）： 一种提出的两阶段过程。首先，在最小耦合强度 $\beta_{min}$ 下执行 CAA 以避免鞍节点分叉（Saddle-Node Bifurcations, SNs）。随后，应用常规退火来增加 $\beta$，直到不动点正确映射到二元伊辛哈密顿量的极小值。

基准测试使用了来自 BiqMac 和 GSET 库的 MaxCut 实例（多达 800 个自旋），以及包含外部场的 Beasley 实例（多达 250 个自旋）。

主要贡献与结果

• 识别鞍节点分叉（SNs）： 延拓分析表明，标准的 CAA 轨迹经常遇到 SNs。随着插值参数 $F$ 的增加，稳定的不动点分支可能会终止于一个 SN，迫使系统跳转到另一个可能无法导向基态的分支。
• 耦合强度 ($\beta$) 的作用： 作者证明，降低 $\beta$ 可以消除 SNs，从而允许系统追踪稳定分支直至 $F=1$。然而，对于 MaxCut 问题，$\beta$ 不能无限小，因为存在一个临界阈值，低于该阈值系统会坍缩至零态（原点）。此外，在较小的 $\beta$ 下，不动点并不一定对应于二元哈密顿量的极小值。
• Hybrid CAA 策略： 为了解决避免 SNs 与确保最终状态代表有效解之间的权衡，作者提出了 Hybrid CAA 方法。该方法包括在最低可能的 $\beta$（略高于临界阈值）下运行 CAA 以到达目标不动点，随后通过 RA 增加 $\beta$ 以稳定解。
• 基准测试性能：
  • MaxCut 实例： Hybrid CAA 方法始终优于标准的 RA，根据噪声水平的不同，实现了约 1.6 倍至 3 倍的平均加速。然而，这种提升被描述为“适度的”，且优化额外参数（$v_F$，即绝热速度）所带来的复杂性也被指出。
  • Beasley 实例（含外部场）： 与标准 RA 相比，Hybrid CAA 显示出更显著的 TTT 降低（高达两个数量级）。然而，当对两种方法都应用“自旋符号法”（即在耦合项中用自旋符号代替自旋振幅）时，Hybrid CAA 的性能优势基本消失，两种方法的表现相当。
• 问题分类： 研究根据延拓路径是否遇到 SNs，将实例分为“绝热易”（adiabatic easy）或“绝热难”（adiabatic hard）。研究发现，相比于标准 RA，Hybrid CAA 使更多的实例变为“绝热易”，尽管并非全部。

意义与主张
论文得出结论，虽然 Hybrid CAA 策略在理论上有其动机且偶尔有效，但它并不提供足够的实际优势来抵消其相对于更简单的现有技术（如常规退火）所增加的复杂性。

作者认为：

1. 对于 MaxCut 问题，性能增益是边际性的，并且在应用自旋符号法处理 Beasley 问题时会消失。
2. 该方法带来了硬件挑战，例如初始化期间需要全连接性，以及需要在每个时间步长更新耦合矩阵。
3. 优化额外超参数（$v_F$）的必要性抵消了其潜在收益。

最终，这项工作提供了对经典绝热退火的严谨延拓分析，阐明了为什么由于分叉的存在，它经常无法达到基态，但也得出结论认为，与现有的成熟退火方法相比，所提出的混合优化目前并不代表一种更优越的实际解决方案。