Extrapolation method to optimize linear-ramp QAOA parameters: Evaluation of QAOA runtime scaling

本文提出了一种外推法来优化线性斜坡 QAOA 的两个参数，证明了该方法在处理高达 28 个量子比特的投资组合优化问题时，实现了优于经典算法的运行时复杂度扩展性。

要点

想象一下，你正在试图解决一个巨大且极其复杂的谜题。你拥有一个全新的高科技工具（量子计算机），它可能能比我们现有的最强人类大脑或超级计算机更快地解决这个谜题。但问题在于，要让这个工具发挥作用，你必须完美地调节它的旋钮。如果你把旋钮调错了，这个工具就毫无用处。

这篇论文介绍了一种聪明的捷径，让你无需从头开始进行繁琐的测试，就能完成这些旋钮的调节。

以下是他们旅程的简单拆解：

1. 问题所在：调节“量子收音机”

他们使用的工具被称为 QAOA（量子近似优化算法）。可以将 QAOA 想象成一台试图在大量杂音中寻找特定、清晰信号（即问题的最佳解）的收音机。

• 常规方法： 通常情况下，为了让信号变得清晰，你必须旋转数十个旋钮（参数）并进行反复测试。随着谜题规模的增大，旋钮的数量会呈爆炸式增长，调节过程会变得极其漫长。这就像试图手动调节一台拥有 100 个旋钮的收音机；你永远也调不完。
• 新思路（线性增量法/Linear-Ramp）： 研究人员发现了一种简化方法。他们意识到，不需要调整 100 个旋钮，实际上只需要调整两个主要设置（我们可以称之为“速度”和“方向”）以及一个“深度”设置（即聆听的时长）。这就是所谓的 Linear-Ramp 方法。这就像拥有一台只有音量旋钮和调频旋钮的收音机，使用起来要容易得多。

2. 解决方案：“小谜题”技巧（外推法）

即使只有两个旋钮，要找到一个巨大谜题（例如 28 片拼图）的完美设置仍然很难。你不能靠瞎猜。

作者提出了一个聪明的技巧：外推法（Extrapolation）。

• 类比： 想象你想知道一辆赛车在 100 英里长的赛道上会跑多快。与其直接开完全程 100 英里（这既耗时又费油），不如先在赛道的 4 英里、6 英里和 8 英里处驾驶赛车。你在这些路段测量速度。
• 预测： 然后，你通过连接这些速度点画出一条线，并将其延伸出去，从而预测赛车在完整的 经过 100 英里赛道时的表现。
• 在论文中： 他们将巨大的、困难的问题（高达 28 个“比特”或拼图碎片）分解成微小的、简单的版本（4、6、8 或 10 片）。他们找到了这些微型版本的完美旋钮设置。然后，他们利用数学方法将这些设置“拉伸”，以预测 28 片拼图这类大型问题的完美设置。

3. 测试：量子计算机能赢吗？

他们在四种不同类型的现实世界谜题上测试了这种方法：

1. 投资组合优化（Portfolio Optimization）： 选择最佳的股票组合，以实现利润最大化并使风险最小化。
2. 特征选择（Feature Selection）： 为机器学习模型挑选最重要的数据点。
3. 聚类（Clustering）： 将相似的物品分组（例如将红球和蓝球分类）。
4. 最大剪切问题（MaxCut）： 将一个网络分为两组，使得组间的连接尽可能强。

他们在模拟量子计算机（一个在超级计算机上运行的完美、无噪声的版本）上运行了这些谜题，并将寻找答案所需的时间与最好的经典（普通）计算机方法进行了对比。

4. 结果：在股市领域获胜，但并非全能

以下是他们的发现：

• 股市谜题（投资组合优化）： 这是见证奇迹的地方。与经典方法相比，使用这种“小谜题”预测技巧的量子方法随着问题规模的增大而变得更快。它展示了潜在的优势。这就像量子赛车随着赛道的延长，开始逐渐超越人类驾驶员。
• 其他谜题： 对于其他三种类型的问题（挑选数据、分组物品和划分网络），量子方法的表现实际上比经典方法慢，或者至少一样慢。虽然“预测技巧”奏效了，但在这些特定案例中，量子工具并没有击败人类的工具。

5. “通用”捷径

研究人员注意到，用于股市谜题的“完美”旋钮设置遵循一种简单的模式。他们意识到，甚至不需要为每一个新谜题都去计算设置。他们可以使用一个通用公式（一个适用于所有人的单一规则）。

• 当他们应用这个通用规则时，量子计算机在其他三个谜题上的表现显著提升，达到了与经典方法相当的水平，尽管并未超越。

核心结论

该论文声称：

1. 你可以通过先测试小规模问题，再通过数学手段预测剩余部分，来跳过为大型问题调试量子计算机那昂贵且缓慢的过程。
2. 这种方法效果良好，足以证明对于投资组合优化问题，量子计算机在处理超大规模问题时，可能最终会比经典计算机更快地解决问题。
3. 对于测试的其他问题，量子计算机目前还未取胜，但该方法使其具备了竞争力。

重要提示： 作者谨慎地指出，这是一个在完美计算机上的模拟。他们尚未证明这在真实的、带有噪声的量子硬件上也能奏效，也尚未解决规模超过 28 片的问题。但这种“从小到大”的预测技巧看起来是让量子计算机在未来发挥作用的一种极具前景的方法。

技术摘要

技术摘要：用于优化线性斜坡 QAOA 参数的外推法

问题陈述
量子近似优化算法（QAOA）是解决组合优化问题的领先候选方案，然而其标准的变分形式面临显著的可扩展性挑战。标准方法需要通过经典程序优化大量的电路参数（对于深度 $p$，有 $2p$ 个参数），这在计算上非常昂贵且容易陷入局部最小值。这种优化瓶颈阻碍了展示潜在量子运行时间优势的进程。虽然固定调度方案（如线性斜坡 QAOA，即 LR-QAOA）将参数空间减少到仅有的两个自由参数（$\Delta\gamma, \Delta\beta$）以及深度 $p$，但为大规模问题规模（$N$）寻找这些参数的最优值仍然是一项非平凡的任务。

方法论
作者提出了一种通过从较小子问题的优化中进行外推，来确定大规模问题规模下适用 LR-QAOA 参数的方法。该方法由三个主要部分组成：

1. 问题建模： 将四种组合优化问题表述为二次无约束二进制优化（QUBO）问题：投资组合优化、特征选择、聚类（使用 Moons 和 Blobs 数据集）以及加权 MaxCut。
2. 经典基准测试： 评估了经典求解器（CPLEX、Gurobi、Goemans-Williamson 以及 MQLib/Burer2002）的运行时间缩放情况。由于 MQLib/Burer2002 启发式算法具有较低的绝对运行时间和一致的缩放行为，且避免了商业求解器中存在的优化界限开销，因此被选为主要的经典基准。
3. LR-QAOA 与外推方案：
   • 线性斜坡算符（Linear-Ramp Ansatz）： 参数不再通过变分优化确定，而是从一个线性算符中采样：$\gamma_j = \Delta\gamma x_j$ 且 $\beta_j = \Delta\beta(1-x_j)$，其中 $x_j$ 是一个线性斜坡变量。
   • 子问题优化： 对于目标问题规模 $N$（最高达 28 个量子比特），生成较小规模（$\tilde{N} \in \{4, 6, 8, 10\}$）的随机子实例。在这些小规模实例上进行网格搜索，以找到最优的 $\Delta\gamma$ 和 $\Delta\beta$。
   • 拟合与外推： 使用多元偏高斯函数（multivariate skew Gaussian function）对 $\tilde{N}$ 下找到的最优参数进行拟合，以定位高概率区域的中心。随后，假设在对数-对数尺度上（$\log(\text{参数})$ 对 $\log(N)$）存在线性关系，将这些中心外推至目标规模 $N$。
   • 深度优化： 通过优化 QAOA 深度 $p$ 来最小化总量子运行时间，该时间定义为电路深度与寻找最优解所需的样本数中位数之积（$D = d \cdot N_{shots}$）。
   • 通用缩放律： 为了提高稳定性并减少离群值，作者基于外推数据导出了“通用”参数缩放律（$f(N) = a \cdot N^b$），并将这些固定的法则应用于给定问题类的所有实例，而非针对每个实例进行单独优化。

关键结果
研究在无噪声量子模拟器上，评估了在问题规模高达 $N=28$ 时，量子运行时间缩放（以总深度 $D$ 表示）相对于经典缩放的情况。

• 投资组合优化： 使用外推参数的 LR-QAOA 展示了缩放指数 $\alpha \approx 0.219$（其中 $D \propto 2^{\alpha N}$），这明显低于经典基准（MQLib/Burer2002）的 $\alpha_{cl} \approx 0.323$。这表明存在潜在的量子缩放优势。
• 特征选择、聚类和 MaxCut： 最初，这些问题的量子缩放指数高于其对应的经典基准。然而，在应用了从外推数据中导出的“通用”参数缩放后，量子缩放得到了显著改善。
  • 对于特征选择和 MaxCut，量子缩放达到了与经典基准相当的水平（分别为 $\alpha \approx 0.202$ 对 $0.197$以及$\alpha \approx 0.163$对$0.156$）。
  • 对于聚类（Moons），经典基准（$\alpha_{cl} \approx 0.051$）仍然优于量子方法（$\alpha \approx 0.163$）。
• 稳定性： 使用通用参数显著减少了当参数针对每个实例单独确定时所观察到的极端离群值（即具有极大深度的实例）的出现。
• 概率行为： 对于投资组合优化和 MaxCut，测量到最优解的概率（$P_{opt}$）保持不变或略有增加，而电路深度呈代数级缩放。这表明对于这些特定问题类，可能存在多项式级运行时间的潜力。

意义与主张
本文声称提出了一种无需在大型电路上进行昂贵变分优化的可扩展方法，用于确定 LR-QAOA 参数。通过利用从小规模子问题进行的外推，作者证明了：

1. 运行时间优势： 与经典启发式算法相比，在投资组合优化中观察到了量子缩放优势。
2. 可扩展性： 外推法允许基于极小规模系统（$N \le 10$）的模拟来高效估计较大系统（$N=28$）的参数。
3. 通用法则： 参数（$\Delta\gamma, \Delta\beta, p$）代数缩放律的识别表明，这些参数可以独立于特定问题实例进行确定，从而提高了算法的鲁棒性。

作者谨慎地总结道，虽然其结果表明对于特定实例可能存在多项式时间解（由恒定的 $P_{opt}$ 和代数级深度缩放所指示），但仍需进一步的工作来在更大的问题规模（$N > 28$）以及容错量子硬件上验证这些发现。他们强调，其工作旨在解决在假设参数可以被高效找到的前提下，LR-QAOA 的一般潜力，而非解决参数优化成本本身作为运行时间组成部分的问题。