Quantum annealing inspired algorithms for the NISQ Era

✨

这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

Each language version is independently generated for its own context, not a direct translation.

想象一下，你正试图在一片广阔而迷雾笼罩的山脉中找到最低点。这正是计算机在解决复杂优化问题时所做的事情：它们在数百万种可能性中寻找“最佳”解。

在量子计算领域，有一种著名的策略称为量子退火（Quantum Annealing, QA）。这就像一位从山顶出发、缓慢而极其缓慢地向下行走的徒步者。如果走得足够慢，他们就能保证找到绝对最低的山谷（即完美解）。然而，在当今的“NISQ 时代”（含噪声中等规模量子时代），我们的量子计算机就像双腿颤抖、能量有限的徒步者。它们无法在不疲惫、不犯错或迷失于迷雾中的情况下走完漫长而缓慢的旅程。

本文探讨了三种新方法，旨在帮助这些“步履蹒跚”的量子徒步者在无需完美漫长旅程的情况下找到山谷底部。

1. “捷径”徒步者：近似量子退火（Approximate Quantum Annealing, AQA）

第一种方法，AQA，就像是告诉徒步者：“你不必走那条缓慢而完美的路径。可以迈更大的步子，但尽量保持在主道上。”

核心思想：在完美模拟中，你迈的是极小的步子。而在 AQA 中，研究人员让计算机迈出更大、更“近似”的步子。
发现：他们找到了一个“金发姑娘区”（恰到好处区间）。如果步子太小，计算机耗时过长甚至崩溃；如果步子太大，徒步者就会完全跳出主道。但在中间地带，徒步者可以迈更大的步子，更快完成旅程，同时仍能抵达正确的山谷。
结果：这使得计算机能够以更少的资源（更少的“能量”和时间）解决问题，同时仍能获得良好的答案。

2. GPS 的“智能起点”：量子近似优化算法（Quantum Approximate Optimization Algorithm, QAOA）

第二种方法，QAOA，是一种流行的算法，其作用类似于寻找最佳路线的 GPS。然而，GPS 的好坏取决于其起点。如果你让它从森林中的随机位置开始，它可能会被困在一个小凹陷处（局部极小值），误以为已找到谷底，尽管附近还有更深的山谷。

问题：通常，QAOA 从随机猜测开始，这就像在随机灌木丛中开始徒步。
解决方案：研究人员意识到，可以利用 AQA 的“捷径”为 QAOA 提供一个热启动。他们不再随机起步，而是先利用 AQA 的“捷径”让徒步者接近正确区域。
结果：一旦徒步者已接近正确的山谷，GPS（QAOA）就能轻松微调路径，找到绝对最低点。这比从头开始要有效得多。

3. “阶梯”向导：演化哈密顿量量子优化（Evolving Hamiltonian Quantum Optimization, EHQO）

第三种方法，EHQO，是最具结构化的方法。想象一下，山脉陡峭到无法直接向下行走。此时，EHQO 会建造一座阶梯。

工作原理：算法不再试图一步从山顶跳到山底，而是将旅程分解为许多小步骤。
1. 它先找到第一个小山坡的底部。
2. 将该位置作为起点，寻找下一个小山坡的底部。
3. 如此一步步重复，直至抵达最终目的地。
优势：这防止了徒步者迷路。通过解决一系列简单的小问题，计算机构建出一张“地图”，引导其走向最终、最困难的解。
代价：爬完所有阶梯需要更多时间，但比起试图直接跳下山，这种方法要可靠得多。

全局视角：他们的发现

研究人员在具有不同变量数量（如 8、12 或高达 18 个）的难题（称为 2-SAT 问题）上测试了这些想法。

“捷径”（AQA） 效果良好，但存在局限；如果问题变得过大，成功率会迅速下降。
“智能起点”（QAOA） 优于随机猜测，但随着问题规模变得巨大，它仍会陷入困境。
“阶梯”（EHQO） 是赢家。通过以受控的小步骤进行旅程，即使问题变大，它仍能保持较高的成功率。它不仅找到了解，而且比其他方法更一致地找到了更好的解。

总结：该论文指出，虽然我们还无法建造完美且缓慢运行的量子计算机，但我们可以运用巧妙的技巧——采取智能捷径、从良好的地图出发、以及攀登由小问题构成的阶梯——使当前不完美的量子计算机在解决难题方面表现得更加出色。

Each language version is independently generated for its own context, not a direct translation.

以下是 Rijul Sachdeva 等人撰写的论文《NISQ 时代的量子退火启发式算法》的详细技术总结。

1. 问题陈述

优化问题在科学与工程中处于核心地位，但随着规模扩大，它们往往变得计算上不可行。**量子退火（QA）**是一种基于绝热定理的有前途的方法，其中系统从简单的初始哈密顿量（ $H_I$ ）演化到问题哈密顿量（ $H_P$ ），以寻找基态（最优解）。

然而，当前的**含噪声中等规模量子（NISQ）**时代带来了重大挑战：

硬件限制： 当前的量子处理器受到噪声、有限的相干时间和连接性约束的影响。
电路深度： 忠实地实现 QA 需要较长的演化时间和深层量子电路（通过 Suzuki-Trotter 分解），由于误差累积，这在当前的 NISQ 设备上目前是不可行的。
变分挑战： 像量子近似优化算法（QAOA）这样的变分算法存在“ barren plateaus（ barren 高原）”、梯度消失以及对初始参数选择的敏感性，通常导致次优的局部极小值。

本文旨在通过开发受 QA 启发的混合算法来弥合这一差距，这些算法在近似量子退火优势的同时，降低了电路深度并提高了对 NISQ 硬件的鲁棒性。

2. 方法论

作者提出并分析了三种不同的算法，它们都利用离散化的退火 ansatz，但在参数化和优化策略上有所不同：

A. 近似量子退火（AQA）

概念： AQA 放宽了对忠实 QA 轨迹的严格要求。它将时间步长（ $\tau$ ）和层数（ $p$ ）视为可调参数，而非固定的物理常数。
机制： AQA 不严格遵循无穷小步长的绝热路径，而是搜索一种机制，其中较大的 $\tau$ （较少的步数）与特定的 $p$ 结合，仍能产生高成功概率。
目标： 识别“有效”的退火参数，以显著降低电路深度的同时重现类 QA 行为。

B. 带有“热启动”的量子近似优化算法（QAOA）

概念： QAOA 使用具有变分参数（ $\beta_j, \gamma_j$ ）的分层电路 ansatz，并通过经典方法进行优化。
创新： 本文研究了将 AQA 中发现的最优参数作为 QAOA 的“热启动”（初始化）。
假设： 使用源自类 QA 轨迹的参数初始化 QAOA，可以将搜索空间限制在低能子空间中，与随机初始化相比，简化了优化景观。

C. 演化哈密顿量量子优化（EHQO）

概念： 一种多步变分方案，通过一系列中间哈密顿量明确引导优化过程。
机制：
1. 定义 $N_s$ 个中间哈密顿量： $H(s_j) = (1-s_j)H_I + s_j H_P$ 。
2. 对 $H(s_1)$ 进行变分优化以找到最优参数。
3. 将所得参数作为 $H(s_2)$ 优化的初始化，依此类推，直到达到 $H_P$ 。
目标： 创建通往解的“平滑”路径，通过利用哈密顿量演化的连续性，防止优化器陷入局部极小值。

3. 主要贡献

AQA 机制的识别： 作者证明了 AQA 在不同的机制下运行。他们识别出一个中间机制（其中 $\tau$ 既不太小也不太大），在该机制下，电路偏离了严格的 QA 动力学，但仍能以较浅的电路实现高成功概率，使其成为 NISQ 设备的理想选择。
AQA 作为 QAOA 的热启动： 该研究证明，源自 AQA 的参数可作为 QAOA 的优越初始化。这种“知情”初始化显著优于随机初始化，特别是在较大的问题规模下，因为它引导优化器走向低能子空间。
EHQO 的开发： EHQO 的引入提供了一个结构化的、逐步的变分框架。它通过将问题分解为更小、更易管理的步骤，有效地缓解了直接优化的困难，充当了对最优初始参数的系统性搜索。
在硬实例上的基准测试： 这些算法在硬 2-SAT 实例（8 到 18 个变量）的集合上经过了严格测试，这类问题已知对经典求解器和变分量子算法具有挑战性。

4. 结果

AQA 性能：
- 参数扫描显示，对于 $\tau < 0.4$ ，电路忠实地重现了 QA 动力学。
- 对于 $0.4 \leq \tau \leq 0.9$ ，电路实现了“有效”的 QA 哈密顿量，以较低的深度（较少的层数）实现了高成功概率。
- 对于 $\tau > 0.9$ ，与 QA 的联系断裂，性能下降。
带有 AQA 初始化的 QAOA：
- 当使用 AQA 参数初始化时，QAOA 在 8 变量问题上实现了接近 1 的成功概率，并且在 12 变量问题上，与随机初始化相比，成功率显著提高。
- 这证实了源自 AQA 的状态被限制在低能子空间中，简化了经典优化器的任务。
EHQO 性能：
- 在平均成功概率方面，EHQO 始终优于 AQA 和 QAOA（随机启动）。
- 扩展性分析： 在 8–18 量子比特的 2-SAT 实例上：
  - AQA： 成功概率呈指数衰减，缩放指数为 -0.319。
  - QAOA（AQA 初始化）： 显示出与 AQA 相似的指数衰减。
  - EHQO： 显示出最佳的扩展性，指数为 -0.283，表明随着问题规模增加，成功概率的衰减速度较慢。
- 瓶颈： 分析确定了“反交叉”区域（靠近 QA 哈密顿量的临界点）为潜在瓶颈，在该区域基态发生突变，导致 EHQO 轨迹暂时偏离。然而，逐步方法使算法能够在后续步骤中恢复。

5. 意义与结论

本文确立了将退火启发的结构纳入变分量子算法是 NISQ 时代的一种可行策略。

实用性： 通过放宽严格的绝热要求（AQA）并使用逐步演化（EHQO），这些方法降低了电路深度和对噪声的敏感性，使其更适合当前的硬件。
优化景观： 结果强调初始参数的选择至关重要。源自物理原理（如 QA 轨迹）的“热启动”可以极大地改善变分算法的收敛性。
未来展望： 虽然该研究是启发式的且仅限于小规模问题，但它为将量子退火概念整合到混合量子 - 经典工作流中提供了路线图。特别是 EHQO 框架，提供了一种灵活、与 ansatz 无关的方法，可适应各种硬件约束和问题类型。

总之，作者证明，人们无需等待容错量子计算机即可利用量子退火的力量；相反，通过将其原理适应于变分算法，可以在近期设备上实现显著的性能提升。