Efficient Estimation of Reduced QAOA Expressibility on Acyclic Graphs

技术摘要：高效估计无环图上缩减 QAOA 表达能力的算法

问题陈述
量子近似优化算法（QAOA）是用于解决诸如 MaxCut 等组合优化问题的领先变分量子算法。然而，QAOA 的表达能力和可训练性从根本上受其电路的动力学李代数（Dynamical Lie Algebra, DLA）支配，该代数表征了希尔伯特空间中可达到的变换。虽然“丰富”的 DLA 意味着能够制备任意状态（最大表达能力），但直接构建 DLA 在计算上是极其困难的，其规模通常随量子比特数呈指数级增长。

在应用对称性约化（Symmetry Reduction）时，一个关键挑战在于：在经典层面，固定单个变量的值（例如，将某个顶点分配到 MaxCut 切割的一侧）会减少问题规模，且不改变优化景观。然而，在量子力学层面，这种约化会修改哈密顿量生成元，从而可能剧烈改变缩减后的 DLA 结构。不同的固定顶点选择可能导致在经典上等价的问题，但在量子电路层面具有截然不同的动力学能力（例如，使 DLA 维度从指数级增长变为多项式级增长）。本文探讨的核心问题是：给定特定的对称性约化（固定顶点 $v$），我们能否在不进行显式构建的情况下，高效地确定所得缩减 DLA 的结构？

方法论
作者提出了一种针对无环图（树）的多项式时间经典算法，该算法能直接从图拓扑结构推断缩减 DLA 的性质。该方法依赖于先前研究 [38] 中建立的结构性结果，这些结果将图结构与特定泡利算符和属于 DLA 的成员身份联系起来。

该算法分为两个主要阶段：

1. 划分（Partitioning）： 给定一棵树 $\Gamma = (V, E)$ 和一个固定的参考顶点 $v$，算法通过广度优先搜索（BFS）对剩余顶点 $V \setminus \{v\}$ 进行划分。划分依据两个图论不变量：

   • 距离 $v$ 的最短路径距离。
   • 从 $v$ 到每个目标顶点路径上遇到的顶点度数的奇偶序列。
     具有相同距离和度数奇偶特征的顶点被归为同一个等价类。根据底层理论，任何此类类别的泡利-X 算符之和都属于缩减后的 DLA。

2. 细化（Refinement）： 算法迭代地细化此划分。如果一个划分类包含单个顶点（单元素集），算法则证明该顶点的单个生成元 $iX_w$ 属于该 DLA。随后，该单元素顶点将被用作新的源点，执行新的 BFS 并生成新的划分。新划分通过“最粗公细化”（通过词典排序高效计算）与当前划分合并。此过程重复进行，直到不再发现新的单元素集或不再发生进一步细化为止。

核心贡献

• 多项式时间估计： 作者引入了一种复杂度为 $O(|V|^2)$ 的算法，用于确定树的缩减 DLA 结构，避免了直接构建李代数的指数级成本。
• 表达能力认证：
  • 全分辨率（Full Resolution）： 如果算法成功将所有顶点划分为单元素集，则证明缩减 DLA 等于“自由” DLA ($g^v_{\Gamma, std} = g^v_{\Gamma, free}$)，这意味着缩减后的拟设（Ansatz）具有最大表达能力。
  • 部分分辨率（Partial Resolution）： 即使未能实现完全分离，算法也能识别出属于 DLA 的单个 $iX_w$ 生成元的顶点子集。这使得推导 DLA 维度的严格下界以及识别可控量子子系统成为可能。
• 对称性感知设计： 本研究表明，对称性约化的选择（即固定哪个顶点）不仅仅是一个经典的预处理步骤，更是一个关键的设计参数，它决定了电路生成的量子动力学能力。

结果
作者在 1,000 个包含多达 1,000 个顶点的随机树上验证了该算法。

• 可扩展性： 该算法成功处理了直接构建 DLA 无法实现的图规模。
• 有效性： 平均而言，算法识别出的单元素类涵盖了约 64% 的顶点。相对于图自同构所允许的理论最大分裂程度，该算法实现了约 96% 的单元素集识别率。
• 启示： 尽管在更大的图中完全顶点分离变得不再频繁，但该经典程序始终能解析出相当比例的底层量子动力学，从而提供显著的结构性见解。

意义
本文主张扩大经典预处理在混合量子算法中的作用。与其仅在选择电路架构后使用经典计算来优化参数，这项工作展示了如何将经典结构分析应用于电路执行之前，以诊断候选量子表示的动力学能力。通过高效估计缩减后的 DLA，研究人员可以基于图结构和所选的对称性约化，评估可控性、表达能力以及潜在的可训练性问题（如梯度消失/贫瘠高原问题）。这为变分量子算法的“对称性感知设计”建立了框架，即利用经典图属性来选择并表征电路所生成的量子动力学。