Near-Optimal Parameter Tuning of Level-1 QAOA for Ising Models

技术摘要：Ising 模型中 Level-1 QAOA 的近最优参数调优

问题陈述
量子近似优化算法（QAOA）是一种混合量子-经典算法，旨在通过将解编码为哈密顿量的基态来解决组合优化问题，例如二次无约束二值优化（QUBO）。虽然增加电路深度（$p$）在理论上可以提高解的质量，但在实际应用中，受限于噪声中规模量子（NISQ）设备的门噪声、连通性限制和态制备误差，实现通常被限制在浅层深度（$p=1$，即 QAOA1）。

QAOA1 的一个关键瓶颈在于其两个变分参数 $\gamma$ 和 $\beta$ 的优化。尽管维度很低，但代价函数景观（cost landscape）具有高度振荡性，且其振荡速率随问题规模、密度和权重变化性的增加而上升。传统观点认为，粗略的网格搜索结合局部最小化足以解决问题；然而，本研究表明，由于景观畸变和混叠现象，此类方法往往无法捕捉到真正的全局最优解，从而导致次优的参数估计。此外，现有的启发式参数初始化方法往往缺乏性能保证，或者依赖于特定的图结构（如无权正则图），无法推广到复杂的、带权重的现实世界实例。

方法论
作者提出了一种严谨的、与问题无关的策略，用于在多项式时间内优化 Ising 模型（QUBO 的量子等价形式）的 QAOA1 参数。该方法通过四个主要的理论和算法步骤进行：

1. 傅里叶分析与采样需求：
   论文将 QAOA1 的期望值建模为一个部分傅里叶级数。通过推导期望值的闭式表达式（定理 1 和推论 1），作者从解析上确定了代价函数沿 $\gamma$ 维度的最大频率（$\omega_{\max}$）。该频率取决于特定问题实例的耦合强度（$J_{uv}$）和外部场（$h_i$）。通过应用 Nyquist-Shannon 采样定理，他们确定了准确重建代价函数景观而不产生畸变所需的最小采样分辨率（$\Delta\gamma$）。这解决了粗略网格搜索中的欠采样问题。

2. 降维：
   一个关键的理论贡献是将针对 $(\gamma, \beta)$ 的二维优化问题简化为针对 $\gamma$ 的一维搜索。

• 对于没有外部场的 Ising 模型，最优的 $\beta^*$ 被解析地表示为 $\gamma$ 的函数（定理 5）。
• 对于带有外部场的模型，通过求解由一阶最优性条件导出的四次多项式来找到最优的 $\beta^*$（定理 6）。
  这种转换使得算法可以在执行 $\gamma$ 线搜索的同时计算每个点对应的最优 $\beta^*$，从而显著降低了计算复杂度。

3. 优化算法：
   为了寻找所得一元函数的全局最优解，作者采用了基于区间分析（Green 算法）的细分算法（算法 1）。该方法能够高效地估计三角多项式的最大模，从而确保识别出近最优的 $\gamma^*$，而无需进行穷举式的网格搜索。

4. 最优解的集中性：
   论文严格证明了对于大型、稠密、正则图，全局最优解 $\gamma^* \in \mathbb{R}^+$ 会非常接近于零并与第一个局部最优解重合（定理 7）。对有限规模图的经验分析证实，“对抗性”实例（即第一个局部最优解不同于全局最优解的情况）较为罕见，主要出现在小型稀疏图中。这一洞察允许进一步简化：可以直接使用在 $\gamma \approx 0$ 附近初始化的梯度下降法，只要步长遵循基于最大频率推导出的采样界限即可。

关键结果
所提出的策略通过递归 QAOA（RQAOA）进行了验证，RQAOA 是一种将 QAOA1 作为子程序进行递归减小问题规模的方法。作者在具有不同边概率和权重分布的大型、稠密、带权 Erdős-Rényi 图（128 和 256 个顶点）上对该方法进行了基准测试。

• 无外部场： 所提出的方法（具有近最优参数的 RQAOA1）在所有测试实例中均一致优于粗略优化的 RQAOA1 和经典半正定规划（SDP）。相比之下，粗略优化的 RQAOA1 通常无法超越 SDP。
• 有外部场： 作者观察到标准 RQAOA1 在带有场的模型上表现不一致。为了解决这一问题，他们引入了“Iter-QAOA”，这是一种使用简化迭代舍入程序的变体。当结合所提出的参数调优策略时，Iter-QAOA 在不同图密度下均能一致优于 SDP 和标准 RQAOA1 变体，展现了鲁棒性。
• 对抗性实例： 经验测试表明，对于节点数 $n > 14$ 的图，遇到对抗性图（即第一个局部最优解不是全局最优解）的概率稳定在约 1%，这验证了在大多数实际情况下使用零附近梯度下降策略的有效性。

意义与主张
本文声称解决了在任意 QUBO 问题上高效寻找 QAOA1 全局近最优参数的挑战。该工作的意义在于：

• 严谨的保证： 不同于以往的启发式方法，该方法提供了具有可证明近最优性的多项式时间算法，适用于不随系统规模呈指数级增长的可通约权重。
• 问题无关性： 该策略不依赖于关于图对称性、结构或权重分布的假设，因此适用于通用的带权 Ising 模型。
• 实际效率： 通过减少搜索空间并利用 $\beta^*$ 的解析解，该方法避免了高分辨率二维网格搜索在计算上的不可行性，同时也避开了粗略采样的陷阱。
• 性能提升： 结果表明，通过适当的参数调优，浅层深度量子算法（QAOA1）可以在稠密、带权实例上超越最先进的经典启发式算法（SDP），凸显了参数优化在变分量子算法中的关键作用。

作者总结道，他们的方法有效地解决了 QAOA1 的参数调优瓶颈，使得在当前及近期的量子硬件上实现更可靠、更高质量的组合优化问题近似成为可能。