Automorphism-Assisted QAOA: A Classical-Estimator Speedup for QAOA Simulation on Graphs with Non-Trivial Symmetry

技术摘要：自同构辅助 QAOA (AA-QAOA)

问题陈述
量子近似优化算法 (QAOA) 是解决 NP-困难组合优化问题（如无权 MaxCut 问题）的一种领先的混合量子-经典方法。在 QAOA 研究中，特别是在由于缺乏量子处理器 (QPU) 访问权限而依赖经典态矢量模拟器（statevector simulators）的研究组中，存在一个显著的瓶颈，即经典优化循环的计算成本。具体而言，在每一次优化迭代中，都必须计算问题哈密顿量 $H_C$ 的期望值。对于一个具有 $|E|$ 条边的图，标准态矢量估计器需要聚合 $|E|$ 项形式为 $\langle Z_i Z_j \rangle$ 的项。由于每一项都需要对态矢量的振幅进行一次 $O(2^n)$ 的遍历（其中 $n$ 为量子比特数），其聚合成本的壁时复杂度（wall-time cost）随每轮迭代呈 $O(|E| \cdot 2^n)$ 比例缩放。这种聚合成本往往会主导总体的模拟时间，尤其是在电路深度 ($p$) 较低且边数较多的图中。

方法论：自同构辅助 QAOA (AA-QAOA)
本文提出了 AA-QAOA，这是一种通过利用底层图的对称性来加速 QAOA 经典态矢量模拟的方法。其核心思想是：对于具有非平凡自同构群 $\text{Aut}(G)$ 的图，QAOA 拟设（ansatz）所制备的状态 $|\psi(\vec{\beta}, \vec{\gamma})\rangle$ 在 $\text{Aut}(G)$ 的作用下是不变的。

该方法流程如下：

1. 边轨道识别（Edge Orbit Identification）： 使用 Nauty 软件包计算图自同构群的生成元。这些生成元用于将边集 $E$ 划分为等价类（轨道），记作 $\tilde{S}_m$。在图的对称性下，同一轨道内的边在结构上是相同的。
2. 可观测量替换（Observable Substitution）： 该方法并不直接评估完整的代价哈密顿量 $H_C = \frac{1}{2} \sum_{(i,j) \in E} (1 - Z_i Z_j)$，而是将其替换为一个缩减后的可观测量 $H_{\text{red}}$。该缩减哈密顿量仅保留每个边轨道中的一个代表性 ZZ 项，并根据该轨道的大小进行加权：
   $$H_{\text{red}} = \frac{1}{2} \sum_{m=1}^{|O_E|} |\tilde{S}_m| (1 - Z_{i_m} Z_{j_m})$$
   其中 $|O_E|$ 是边轨道的数量。
3. 精确等价性（Exact Equivalence）： 作者证明了对于标准 QAOA 拟设所制备的 $\text{Aut}(G)$-不变状态，其期望值满足 $\langle H_{\text{red}} \rangle = \langle H_C \rangle$。因此，优化景观（optimization landscape）、最优变分参数 $(\vec{\beta}^*, \vec{\gamma}^*)$ 以及最终的近似比均保持不变。
4. 流水线实现（Pipeline Implementation）： QAOA 拟设电路使用完整的 $H_C$ 进行构建（以确保状态制备与标准 QAOA 完全一致）。然而，在经典优化循环期间，估计器使用仅包含 $|O_E|$ 项的 $H_{\text{red}}$ 来计算期望值。

核心贡献

• 经典聚合加速： 主要贡献在于降低了经典态矢量估计器的后处理聚合成本。聚合成本从每轮迭代的 $O(|E| \cdot 2^n)$ 降至 $O(|O_E| \cdot 2^n)$。加速因子由轨道比例 $|E|/|O_E|$ 决定。
• 与反向因果锥 (RCC) 的解耦： 本文明确区分了其机制与先前利用反向因果锥 (RCC) 来减少电路深度或量子比特跨度（qubit span）的工作。作者证明了 AA-QAOA 的加速与代表性 RCC 的量子比特跨度无关。即使单个代表性边的 RCC 跨越了所有量子比特（如完全图），加速效果依然存在，因为节省发生在经典项的求和过程中，而非量子电路的执行或状态演化过程。
• 精确性： 该方法提供的是一种精确替换，而非近似。针对 $H_{\text{red}}$ 的优化收敛于与针对 $H_C$ 优化完全相同的解。

结果
作者在不同层数 $p=1$ 和 $p=2$ 下，针对多种图族对 AA-QAOA 进行了基准测试：

• 树状结构图： 在高达 34 个顶点的二叉树和平衡树上，该方法实现了显著的壁时缩减。对于一个 34 顶点的二叉树，优化器时间从 $>3600$ 秒（完整哈密顿量）降至 $360.56$ 秒（缩减后），降幅超过 90%。峰值内存使用量也显著降低。
• 诊断控制实验： 为了隔离其作用机制，作者测试了：
  • 完全图 ($K_n$)： 尽管具有单个边轨道（$|O_E|=1$）且代表性 RCC 跨越了每一个量子比特，$K_{16}$ 仍显示出约 $8\times$ 的加速。这反驳了“加速依赖于减少 RCC 量子比特跨度”的假设。
  • 星形图： 一旦最小化了开销，其表现出的加速效果与轨道比例一致。
  • 随机 3-正则图： 对于具有平凡自同构群（$|O_E| \approx |E|$）的图，未观察到加速，这证实了收益严格取决于对称性。
• 架构无关性： 在 CPU 和 GPU 后端上的测试均确认，加速效果源于经典的聚合步骤，而非特定硬件加速器的产物。
• 近似比： 在所有测试实例中，$R_{\text{red}}$ 和 $R_{\text{full}}$ 在优化器方差范围内是完全一致的，验证了精确等价性的理论主张。

意义与适用范围
本文将 AA-QAOA 定位为经典态矢量模拟流水线的一种专门加速器，这类流水线是那些没有 QPU 访问权限的 QAOA 研究组的主要工具。

• 局限性： 作者明确指出 AA-QAOA 无法在量子处理器 (QPU) 上提供加速。在硬件上，无论测量何种可观测量，完整电路都会执行，且对对角线 ZZ 项的聚合是经典比特串上的一个平凡后处理步骤，并不会产生态矢量模拟中那种 $O(|E| \cdot 2^n)$ 的成本。
• 适用性： 该方法最适用于具有高对称性的结构化图（如树、环、完全图、超立方体），在这些图中，轨道比例 $|E|/|O_E|$ 较大。对于泛化的非对称图（如随机 3-正则图），其效果较弱，因为这类图的自同构群是平凡的。
• 开销： 预计算自同构（使用 Nauty）存在一定的成本，且该成本并未在报告的单次迭代时间中被摊销。然而，对于涉及多次优化迭代或参数扫描的典型 QAOA 研究，该预计算成本相对于累积的模拟节省而言是微不足道的。

总之，AA-QAOA 提供了一种严谨且精确的方法，通过利用图的对称性来减少代价期望值中项的数量，从而在不改变量子电路或解的质量的前提下，降低经典 QAOA 模拟的计算瓶颈。