Adaptive Differential Evolution and Multistart Search for Noisy QAOA Optimization

技术摘要：针对噪声 QAOA 优化的自适应差分进化与多起点搜索

问题陈述
量子近似优化算法（QAOA）是一种用于组合优化的混合变分方法，然而其在实际应用中常受到经典训练瓶颈的限制。这些瓶颈包括非凸能量景观中的多盆地现象、微小的近优捕获区域，以及由噪声中规模量子（NISQ）设备上有限采样测量引入的统计不确定性。尽管已有多种优化器（如 SPSA、CMA-ES）被提出用于变分量子算法，但其性能高度依赖于特定的噪声模型、电路结构和优化协议。目前仍缺乏系统性的理解，来阐明景观结构、观测噪声以及“搜索质量”（访问一个好点）与“选择质量”（从噪声数据中选出最好的点）之间的区别如何共同决定 QAOA 的优化器性能。

方法论
作者在四个不同的成本哈密顿量族（固定系统规模 $N=12$，QAOA 深度 $p=3, D=6$）上，对十种经典优化器进行了基准测试。这些哈密顿量族涵盖了不同的相互作用局部性和图几何结构：

1. 3-正则 Max-Cut： 一个稀疏、均匀的二局部基准模型。
2. 2D Edwards–Anderson (EA)： 一个具有双模耦合的稀疏几何自旋玻璃模型。
3. 稀疏 3-自旋玻璃： 一个基于随机超图的稀疏高阶相互作用模型。
4. Sherrington–Kirkpatrick (SK)： 一个密集的全连接相互作用模型。

研究在三种条件下评估了优化器：

• 精确目标（Exact Objectives）： 确定性态矢量模拟。
• 低噪声（Low-Noise）： 加性高斯噪声（$\sigma \approx 0.0055$），模拟高采样数（$S_{eff}=8192$）的测量。
• 高噪声（High-Noise）： 加性高斯噪声（$\sigma \approx 0.044$），模拟低采样数（$S_{eff}=128$）的测量。

测试的优化器：
测试面板包括梯度下降局部搜索（BFGS）、多起点变体（MS-BFGS、MS-CMA-ES）、随机逼近（SPSA）、协方差自适应（CMA-ES）、集群方法（iSOMA），以及几种源自 CEC 竞赛的自适应差分进化（DE）变体（SciPy-DE、iL-SHADE、L-SRTDE、jSO-lite）。

性能指标：
研究明确区分了：

• 预言机指标 ($\epsilon_{oracle}$)： 搜索过程中访问到的最佳精确目标值（衡量搜索能力）。
• 选择指标 ($\epsilon_{selected}$)： 仅基于噪声观测所选出的精确目标值（衡量选择能力）。

实验在 10,000 和 30,000 次函数评估（FE）预算下进行，共进行 25 次独立运行。一项补充鲁棒性检查评估了五种领先方法在每个哈密顿量族三个实例上的表现，且结构感知扩展测试了蒙特卡洛树搜索（MCTS）和跨深度策略。

关键结果

1. 精确目标：

   • 多起点局部方法（MS-BFGS 和 MS-CMA-ES）占据主导地位，在 30,000 次 FE 时在所有模型上均达到了数值参考精度。
   • 自适应 DE 方法（jSO-lite、iL-SHADE、L-SRTDE）具有竞争力，但在无噪声状态下，其收敛速度通常比多起点局部搜索更缓慢。

2. 噪声反馈（低噪声与高噪声）：

   • 机制转变： 在噪声条件下，自适应种群方法（特别是自适应 DE 变体）变得更具竞争力。
   • 实例依赖性： “最佳”优化器高度取决于特定的哈密顿量实例和噪声水平。
     • 低噪声： iL-SHADE 在 Max-Cut 和 SK 上领先；jSO-lite 在 EA 上领先；L-SRTDE 在 EA 和稀疏 3-自旋玻璃上领先。
     • 高噪声： iL-SHADE 是最强的短预算搜索方法；L-SRTDE 在长预算下的自旋玻璃景观中表现优异。
   • 搜索与选择差距： 在高噪声下，最佳访问点与基于噪声历史选出的点之间出现了显著差距。例如，在 Max-噪声下的 Max-Cut 问题中，最佳访问点的中值误差（jSO-lite）为 0.0222，而选定点的误差为 0.0536。
   • 选择策略： MS-CMA-ES 在高噪声下往往能获得最佳的“选定”排名，这并非因为它找到了更好的点，而是因为其选择机制相比其他方法对噪声更具鲁棒性。

3. 鲁棒性与结构：

   • 实例敏感性： 当将基准测试扩展到每个哈密顿量族的三个实例时，特定自适应 DE 变体的排名（例如 jSO-lite 与 L-SRTDE 谁更优）发生了显著变化，表明即使在同一哈密顿量族内，也不存在通用的最优自适应 DE 变体。
   • 结构感知搜索： 补充研究表明，QAOA 特有的策略（如跨深度限制和连续盆地细化）比单纯使用 MCTS 选择在这些条件下更为有效。
   • 回顾性验证： 为最终候选者保留一小部分测量预算进行重新评估，可以提高所有方法的选定解质量。

意义与主张
本文主张，QAOA 的优化器选择不能由单一的通用胜出者来决定。相反，性能是以下因素的共同函数：

1. 景观结构： 能量景观的复杂程度（如盆地多样性、条件数）决定了局部多起点法或全局种群法哪种更有效。
2. 观测噪声： 噪声水平从根本上改变了排名，使自适应种群方法相对于局部梯度下降法更具优势。
3. 最终点识别： 找到一个好解（搜索）与从噪声数据中识别出该解（选择）之间的区别至关重要；一个能找到最佳点的算法，未必是能在高噪声下成功选出该点的算法。

作者得出结论，虽然自适应 DE 变体（特别是 jSO-lite、iL-SHADE 和 L-SRTDE）在噪声环境下表现强劲，但其优越性是依赖于具体实例的。该研究强调，有必要进行考虑特定噪声模型、景观几何形状以及与应用相关的特定指标（搜索 vs. 选择）的仔细基准测试。