2025-11-16T05:46:11.952557

Provable avoidance of barren plateaus for the Quantum Approximate Optimization Algorithm with Grover mixers

Tsvelikhovskiy, Nuyten, Bakalov

We analyze the dynamical Lie algebras (DLAs) associated with the Grover-mixer variant of the Quantum Approximate Optimization Algorithm (GM-QAOA). When the initial state is the uniform superposition of computational basis states, we show that the corresponding DLA is isomorphic to $\mathfrak{su}(d) \oplus \mathfrak{u}(1)\oplus \mathfrak{u}(1)$, where $d$ denotes the number of distinct values of the objective function. We also establish an analogous result for other choices of initial states and Grover-type mixers. Furthermore, we prove that the DLA of GM-QAOA has the largest possible commutant among all QAOA variants initialized with the same state, corresponding physically to the maximal set of conserved quantities. We derive an explicit formula for the variance of the GM-QAOA loss function in terms of the objective function values, and we show that for a broad class of optimization problems, GM-QAOA with sufficiently many layers avoids barren plateaus.

academic

Provable avoidance of barren plateaus for the Quantum Approximate Optimization Algorithm with Grover mixers

基本信息

论文ID: 2509.10424
标题: Provable avoidance of barren plateaus for the Quantum Approximate Optimization Algorithm with Grover mixers
作者: Boris Tsvelikhovskiy (UC Riverside), Matthew Nuyten (NC State), Bojko N. Bakalov (NC State)
分类: quant-ph
发表时间: 2025年10月13日 (arXiv预印本)
论文链接: https://arxiv.org/abs/2509.10424

摘要

本文分析了Grover混合器变体的量子近似优化算法(GM-QAOA)相关的动态李代数(DLAs)。当初始状态是计算基态的均匀叠加时，作者证明相应的DLA同构于 $\mathfrak{su}(d) \oplus \mathfrak{u}(1)\oplus \mathfrak{u}(1)$ ，其中 $d$ 表示目标函数的不同值数量。文章还建立了其他初始状态和Grover型混合器的类似结果，证明GM-QAOA的DLA在所有相同初始状态的QAOA变体中具有最大的交换子，对应于最大的守恒量集合。作者推导出GM-QAOA损失函数方差的显式公式，并证明对于广泛的优化问题类别，具有足够多层的GM-QAOA能够避免贫瘠高原现象。

研究背景与动机

核心问题

贫瘠高原问题：变分量子算法(VQAs)面临的根本挑战是贫瘠高原现象，即损失函数的方差随系统规模呈指数级减小，导致梯度几乎消失，使得经典训练方法失效。
混合器选择的重要性：传统QAOA使用标准X混合器，但这种选择往往无法利用问题的特定结构，限制了算法性能。
理论分析的缺失：尽管提出了多种QAOA变体，但对其动态李代数的结构性质缺乏深入理解，特别是GM-QAOA的理论分析相对薄弱。

研究意义

实用价值：为近期量子设备上的量子优化提供理论指导
理论贡献：建立动态李代数与算法性能之间的联系
方法创新：通过李代数框架分析变分量子算法的可训练性

核心贡献

完整表征GM-QAOA的动态李代数：证明当初始状态为均匀叠加时，DLA同构于 $\mathfrak{su}(d) \oplus \mathfrak{u}(1)\oplus \mathfrak{u}(1)$
希尔伯特空间分解：给出DLA作用下希尔伯特空间的不可约分解，识别算法的表达能力
最大交换子性质：证明GM-QAOA在相同初始状态的所有QAOA变体中具有最大交换子，对应最大守恒量集合
贫瘠高原避免的严格证明：为广泛的s-局域优化问题提供损失函数方差的显式下界，证明GM-QAOA避免贫瘠高原
多个优化问题的应用：在MaxCut、SAT、Max-k-VertexCover、TSP等问题上验证理论结果

方法详解

任务定义

研究GM-QAOA的动态李代数结构，其中：

输入：n量子比特上的离散优化问题，目标函数 $F: B^n \to \mathbb{R}$
混合器：Grover混合器 $G_M = |\xi\rangle\langle\xi|$ ，其中 $|\xi\rangle$ 是初始状态
目标：分析相应DLA的结构并证明避免贫瘠高原

核心理论框架

1. 希尔伯特空间分解

根据目标函数的水平集分解希尔伯特空间： $W = W_{\lambda_1} \oplus W_{\lambda_2} \oplus \cdots \oplus W_{\lambda_r}$

其中 $W_{\lambda_j}$ 是目标函数值为 $\lambda_j$ 的计算基态张成的子空间。

进一步细化分解为： $W = \tilde{W} \oplus W_0$

其中：

$W_0 = \bigoplus_{j=1}^d \mathbb{C}|\xi_j\rangle$ ：初始状态的非零分量张成的子空间
$\tilde{W} = (W_0)^{\perp}$ ：与 $W_0$ 正交的子空间

2. 动态李代数的结构定理

定理III.1：GM-QAOA的动态李代数 $g_\xi := \langle iG_M, iH_P\rangle_{\text{Lie}}$ 满足：

$g_\xi \cong \begin{cases} \mathfrak{su}(d) \oplus \mathfrak{u}(1) \oplus \mathfrak{u}(1), & \text{if } d < 2^n \\ \mathfrak{su}(d) \oplus \mathfrak{u}(1), & \text{if } d = 2^n \end{cases}$

其中 $d$ 是初始状态 $|\xi\rangle$ 在不同目标函数值子空间上的非零分量数。

3. 表示论分解

定理III.4：作为 $g_\xi$ 的表示，希尔伯特空间分解为： $W = W_0 \oplus \mathbb{C}^{\oplus(2^n-d)}$

其中 $W_0$ 是不可约的 $d$ 维表示，其余为1维表示的直和。

技术创新点

李代数方法的系统应用：首次完整分析GM-QAOA的动态李代数结构
交换子最大性：证明GM-QAOA在保持守恒量方面的优越性
方差下界的显式公式：建立损失函数方差与目标函数结构的直接联系

实验设置

理论验证的数值实验

数据集

图类型：Erdős-Rényi随机图
规模：3-10个顶点（受仿真成本限制）
问题实例：MaxCut问题

评价指标

损失函数方差： $\text{Var}_{\beta,\gamma}[\ell_{\beta,\gamma}(\rho,\hat{H}_P)]$
理论下界验证：与析下界 $\frac{1}{3n^4}$ 的比较

实现细节

仿真器：PennyLane状态向量仿真器
参数采样：每个图采样100个参数对 $(\beta,\gamma)$
深度范围： $p = 1$ 到 $30$ 层
Grover混合器实现：通过式(10)的门序列实现

实验结果

主要结果

1. 方差行为验证

观察：损失函数方差在小深度时快速增长，随后趋于稳定
理论符合性：数值结果始终高于理论下界 $\frac{1}{3n^4}$
深度依赖性：方差随深度增加而增大并稳定，支持深度电路避免贫瘠高原的理论

2. 不同图结构的DLA维数比较

图类型	GM-QAOA维数	标准QAOA维数
路径图(n顶点)	$n^2 + 1$	$n^2$
环图(n顶点)	$(\lfloor n/2 \rfloor + 1)^2 + 1$	$3n - 1$
完全图	$(\lfloor n/2 \rfloor + 1)^2 + 1$	$O(n^3)$
房子图	26	248

理论应用实例

MaxCut问题

方差下界： $\text{Var}_{\beta,\gamma}[\ell_{\beta,\gamma}(\rho,\hat{H}_P)] \geq \frac{1}{3n^4}$

加权MaxCut问题

方差下界： $\text{Var}_{\beta,\gamma}[\ell_{\beta,\gamma}(\rho,\hat{H}_P)] \geq \frac{1}{3w_{\max}^2 n^4}$

其他优化问题

m-SAT： $\text{Var} \geq \frac{(m!)^2}{12n^{2m}}$
Max-k-VertexCover： $\text{Var} \geq \frac{1}{12n^4}$
TSP： $\text{Var} \geq \frac{1}{3w_{\max}^2 k^8}$

结论与讨论

主要结论

结构定理：GM-QAOA的DLA具有简洁的 $\mathfrak{su}(d) \oplus \mathfrak{u}(1)^{\oplus 2}$ 结构
贫瘠高原避免：对于s-局域问题，GM-QAOA在足够深度下避免贫瘠高原
守恒量最大化：GM-QAOA在相同初始状态的QAOA变体中保持最多守恒量