Methods for non-variational heuristic quantum optimisation

想象你正在试图在一片充满浓雾、遍布深谷和隐蔽坑洞的广袤山脉中寻找最低点。这就是计算机科学家所称的优化问题（optimization problem）：在数十亿种可能性中寻找绝对最佳的解决方案。

几十年来，在量子计算机上解决这类问题的主要策略一直是“变分（Variational）”方法。这就像一名学生试图通过学习一首歌，不断向老师寻求反馈、调整音高并反复尝试。这虽然可行，但速度很慢，且需要大量的反复沟通。

这篇论文介绍了一种不同的方法。与其不断地寻求反馈，作者提出了一种将**量子计算机作为“超级提议者（Super-Proposer）”**的方法。他们称之为“非变分（non-variational）”方法，因为它不依赖于那种缓慢的“老师-学生”循环。相反，它使用了一个混合系统：由经典计算机进行主要的竞速，但偶尔会请求量子计算机进行一次“魔法跳跃（magic jump）”到新的位置。

以下是他们想法的拆解，使用了简单的类比：

1. 问题所在：陷入局部陷阱

想象你是一名徒步旅行者（算法），正试图寻找最深的谷底（最佳解决方案）。

经典模拟退火（Simulated Annealing, SA）： 你从山顶出发，慢慢向下走。如果你掉进了一个小凹陷（局部最小值），你可能会被困在那里，因为你没有足够的能量爬出来去寻找真正的谷底。
并行回火（Parallel Tempering, PT）： 为了解决这个问题，你派出了一整个徒步小组。有些人是在炎热晴朗的日子里行走（高温），他们可以轻松跳过小山丘；另一些人在寒冷冰冻的日子里行走（低温），他们非常谨慎。每隔一段时间，徒步者们会交换位置。“热”的徒步者跳过了山丘后，会与被困住的“冷”徒步者交换位置，从而帮助整个团队逃脱陷阱。

2. 创新点：量子“魔法跳跃”

作者意识到，虽然“热”的徒步者擅长跳跃，但他们的跳跃距离仍然受到物理限制。他们提出用**量子提议（Quantum Proposal）**取代标准的“局部跳跃”（翻转一个开关）。

把量子计算机想象成一个传送器。它不再采取小步、谨慎的移动，而是观察地图，并建议你“传送”到山脉中另一个完全不同的、且极有可能是好地方的位置。

运作方式： 经典计算机说：“好吧，我现在在这个位置。”量子计算机运行一次快速计算（“实时演化”），然后说：“我认为你应该传送至那边那个特定的位置。”随后，经典计算机会检查那个位置是否理想，并决定是否接受这次跳跃。

3. 两种新方法

论文介绍了两种使用这个量子传送器的具体方式：

QeSA（量子增强模拟退火）： 这就像是一个人正在徒步，但现在他拥有了一个传送器。随着他逐渐降温（变得更加谨慎），传送器帮助他逃离那些普通徒步者会被困住的深坑。
QePT（量子增强并行回火）： 这是徒步小组。作者发现了一个非常有趣的现象：你不需要给每一个徒步者都配备传送器。
- 如果你只给处于底部（最冷、最谨慎）的徒步者配备传送器，整个团队的表现会好得多。
- 这是一个巨大的突破，因为量子计算机既昂贵又稀缺。你可以让“热”的徒步者留在普通的经典计算机上，而只为那些最有可能被困住的少数徒步者使用昂贵的量子传送器。

4. 他们的发现（结果）

作者通过模拟实验（计算机模型）在非常困难的、“玻璃态（glassy）”的问题（拥有数千个令人困惑的坑洞的山脉）上测试了这些想法。

发现： 量子增强方法找到最佳解决方案的速度比经典方法快得多。
效率： 他们展示了即使你只将量子计算机用于一小部分工作（比如仅用于底部底部的几名徒步者），也能获得巨大的速度提升。

5. 为什么这在未来很重要

论文认为，这与我们目前（或很快就会拥有）的技术完美契合。

抗噪性（Noise Resilience）： 今天的量子计算机是“多噪的”（会出错）。作者指出，这种方法天生对噪声具有鲁棒性。即使量子传送器变得有点模糊，它仍然能建议一个随机的位置，这总比什么都没有要好。
混合动力： 它不需要一台完美的、无误差的量子计算机。它只需要量子计算机完成一项特定工作（建议跳跃），而强大的经典超级计算机则承担其余的大部分重任。

总结

简而言之，这篇论文的观点是：“不要试图让整个量子计算机去做整项工作。相反，让经典计算机来跑这场比赛，并利用量子计算机在关键时刻提供一次强力的‘超级跳跃’，以帮助跑者逃离陷阱。我们证明了，即使只有少量的这些‘超级跳跃’，也能让整个团队更快地获胜。”

注：论文明确指出，这些是基于模拟实验的“原理验证（proof of principle）”结果。他们尚未在真实的量子硬件上运行这些方法，也没有声称这些方法能立即解决特定的现实工业问题。他们是在提出一种使用量子计算机的新思路。

技术摘要：非变分启发式量子优化方法

问题陈述
优化是科学和工业应用的核心，然而对于组合问题，经典的精确算法往往需要指数级时间，因此必须使用启发式求解器。虽然变分量子算法 (VQA) 和量子退火 (QA) 在当前的抗噪声量子优化研究中占据主导地位，但它们面临着收敛性、电路深度和硬件要求的挑战。此外，许多现有的量子方法依赖于尚未实现的容错技术或特定的硬件架构。因此，需要一种替代性的、非变分量子启发式方法，能够通过混合量子-经典框架利用近期的量子设备 (NISQ)，特别是针对具有“玻璃态”性质（例如 Sherrington-Kirkpatrick 模型）的代价函数，这类函数会导致经典的马尔可夫链蒙特卡洛 (MCMC) 方法因能量壁垒而出现热化缓慢的问题。

方法论
作者提出了一类新型的量子优化启发式算法，该算法通过基于实时演化的量子子程序取代了经典 MCMC 算法中的局部提议步骤。这种方法完全避开了变分框架。

核心机制 (QeMCMC)： 其基础是量子增强型马尔可夫链蒙特卡洛 (QeMCMC)。该算法不再使用经典的局部提议（例如翻转单个自旋），而是将量子计算机初始化在计算基态 $|s\rangle$ ，应用幺正演化 $U = e^{-iHt}$ ，然后测量结果以获得新的构型 $s'$ 。
- 哈密顿量 $H$ 被构建为驱动项（与绝热量子计算相关，旨在迫使能量能级间发生扩散）和特定问题的伊辛哈密顿量之和。
- 超参数 $\gamma$ （混合）和 $t$ （演化时间）从特定范围内进行采样。
- 这种设计旨在生成具有小能量差 ( $\Delta f$ ) 和大汉明距离 ( $\Delta H$ ) 的提议，从而比经典的局部提议更有效地促进非局部移动，以逃离局部极小值。
提出的算法：
- 量子增强模拟退火 (QeSA)： 通过将经典局部提议替换为量子提议机制，并遵循对数冷却计划，来扩展经典的模拟退火 (SA)。
- 量子增强并行回火 (QePT)： 扩展了并行回火 (PT) 方法。并行回火通过在多个不同温度的马尔可夫链中并行运行并进行周期性的构型交换来实现。在 QePT 中，作者提出了一个混合方法，其中仅对一部分链（特别是那些热化最困难的低温度链）进行量子增强，而高温度链则保持为经典形式。

主要贡献

算法提议： 引入了 QeSA 和 QePT，作为非变分、混合量子-经典的优化启发式算法。
混合架构： 展示了并非必须进行全量子增强；在并行回火设置中仅增强“瓶颈”处的低温链即可产生显著优势，这使得该方法在当前的 HPC-QC（高性能计算-量子计算）集成中更具可行性。
原理验证数值实验： 作者提供了基于 Sherrington-Kirkpatrick (SK) 自旋玻璃实例 ( $n \leq 10$ ) 的模拟数值结果，以验证这些算法相对于经典基准的收敛特性。

结果

收敛行为： 在模拟中，经典 SA 经常陷入局部极小值，表现出成功概率的高方差。相比之下，QeSA 展示了更一致的达到全局极小值的能力，其成功概率随步数稳步增加。
计算量： 作者将“计算量” ( $N_p$ $N_{p}$ ) 定义为链长度与找到特定概率下的基态所需的重复次数之积。
- 对于 QeSA，通过优化链长度可以发现，与测试的问题规模下的经典 SA 相比，量子方法可以用显著更低的计算量达到目标成功概率。
- 对于 QePT，结果表明，仅对最低温度链（例如 4 个副本中的 2 个）进行量子增强，就能提供优于全经典 PT 的实质性改进，并接近全量子增强系统的性能。这表明存在良好的资源与性能权衡。
扩展性： 作者观察到，对于平均情况下的自旋玻璃实例，可能存在潜在的扩展优势（假设最高达四次方），但由于经典模拟的局限性以及缺乏真实硬件测试，他们明确表示并未量化确定性的量子加速。

意义与声明
本文将这些方法定位为解决大规模优化问题的可扩展且具有竞争力的路径，可利用近期的量子设备。

鲁棒性： 这些算法被声称具有内在的抗噪声鲁棒性。在完全去极化噪声的极限下，量子提议会退化为均匀采样，这仍然是一个有效的 MCMC 步骤，而不像变分方法可能会导致无法收敛。
并行性： 该方法支持量子与经典资源之间的并行执行，仅需通过经典通信进行副本交换，这与当前的 HPC 架构高度契合。
声明的审慎性： 作者明确指出这些是启发式方法，对于最坏情况下的加速不存在解析保证。他们承认量子提议的性能在分析上尚不明确了解，且观察到的优势目前是基于模拟硬件的原理验证数值结果。他们表示，这些方法的真实潜力及其扩展性，只能在通过更紧密的量子-经典集成并在真实量子硬件上进行测试后才能得到验证。这项工作旨在为未来的研究和实验验证提供动力，而非提供确定性的解决方案。

1. 问题所在：陷入局部陷阱

2. 创新点：量子“魔法跳跃”

3. 两种新方法

4. 他们的发现（结果）

5. 为什么这在未来很重要

总结

类似论文