# QAOA 算法详解：量子近似优化算法

QAOA（Quantum Approximate Optimization Algorithm，量子近似优化算法）由 Edward Farhi、Jeffrey Goldstone 和 Sam Gutmann 于 2014 年提出，是针对组合优化问题设计的变分量子算法。它在 NISQ（Noisy Intermediate-Scale Quantum，近期含噪中等规模量子）设备上具有实际可行性，并且是少数在理论上可以严格刻画其近似能力的量子算法之一。

## 问题背景：组合优化

许多重要的计算问题可以表述为组合优化：给定定义在 $n$ 位比特串上的成本函数 $C(\mathbf{z})$，我们要找

$$\mathbf{z}^* = \arg\max_{\mathbf{z} \in \{0,1\}^n} C(\mathbf{z}).$$

典型的例子包括：

- MaxCut：把图的顶点分成两组，使两端分属不同组的边（"被切断的边"）尽可能多；
- Max-SAT：给定布尔公式，找到满足最多子句的变量赋值；
- 旅行商问题（Traveling Salesman Problem, TSP）：找到访问所有城市的最短回路；
- 图着色、背包问题、调度问题等。

这些问题大多是 NP-Hard：经典精确算法在最坏情形下需要指数时间，而经典近似算法的近似比存在理论限制（例如 MaxCut 在唯一博弈猜想下的 0.878 上限对应 Goemans-Williamson 算法）。

QAOA 的目标是：用 $p$ 层量子电路（$p$ 为小整数），以多项式资源找到质量可随 $p$ 提升的近似解。

## 核心思想：交替演化

QAOA 把优化问题编码为两个哈密顿量，通过交替演化来搜索最优解。

第一个是问题哈密顿量（problem Hamiltonian）$H_C$，它把目标函数编码为对角矩阵：

$$H_C = \sum_{\mathbf{z}} C(\mathbf{z})\, |\mathbf{z}\rangle\langle\mathbf{z}|,$$

即 $H_C|\mathbf{z}\rangle = C(\mathbf{z})|\mathbf{z}\rangle$。对于 MaxCut 这类问题，$H_C$ 还可以等价地写成泡利算符 $Z_i Z_j$ 的和（下一节我们从 $C(\mathbf{z})$ 出发完整推导这一形式）。

第二个是混合哈密顿量（mixer Hamiltonian）$H_B$，它驱动量子态在计算基之间跃迁：

$$H_B = \sum_{i=1}^{n} X_i.$$

需要注意一个细节：$|+\rangle^{\otimes n}$ 是 $\sum_i X_i$ 的最高本征态（本征值 $+n$），而不是基态。为了与绝热演化的叙述一致，本教程把混合哈密顿量取为 $H_B = -\sum_i X_i$，此时 $|+\rangle^{\otimes n}$ 是 $H_B$ 的基态（本征值 $-n$）。两种约定只差替换 $\beta \to -\beta$，得到的能量期望完全相同。

**$p$ 层 QAOA 态**定义为

$$|\vec{\gamma}, \vec{\beta}\rangle = \prod_{l=1}^{p} \Big[ e^{-i\beta_l H_B}\cdot e^{-i\gamma_l H_C} \Big]\cdot |+\rangle^{\otimes n},$$

其中参数向量 $\vec{\gamma} = (\gamma_1, \ldots, \gamma_p)$、$\vec{\beta} = (\beta_1, \ldots, \beta_p)$ 待优化。矩阵乘积从右向左作用，因此最右边的 $e^{-i\gamma_1 H_C}$ 最先执行。

这一结构的直觉是：$e^{-i\gamma H_C}$ 在计算基上施加依赖于成本值的相位——$C(\mathbf{z})$ 越大的分量相位转得越多，相当于"标记好解"；$e^{-i\beta H_B}$ 把各计算基分量混合起来，让好解的相位模式转化为振幅上的增强。交替施加两类算符，好解的振幅逐层干涉增强，这与 Grover 振幅放大有相似的机制，但每层的"转动量"由可调参数控制。

## 算法步骤详解

### 第一步：问题编码——从比特串到 $Z_i Z_j$

我们以 MaxCut 为例，完整推导从目标函数到泡利哈密顿量的每一步。

给定图 $G = (V, E)$，赋值是每个顶点上的比特 $b_i \in \{0, 1\}$。一条边 $(i,j)\in E$ 被切断，当且仅当 $b_i \neq b_j$。我们引入自旋变量 $s_i \in \{+1, -1\}$，约定 $b_i = \frac{1 - s_i}{2}$（即 $b_i = 0 \leftrightarrow s_i = +1$，$b_i = 1 \leftrightarrow s_i = -1$）。对每条边，切断指示符有两种等价写法：

$$\mathbb{1}[b_i \neq b_j] = b_i + b_j - 2\,b_i b_j = \frac{1 - s_i s_j}{2}.$$

我们验证一下：右边的第一式，当 $(b_i, b_j) = (0,0)$ 或 $(1,1)$ 时取 $0$，当 $(0,1)$ 或 $(1,0)$ 时取 $1$；第二式中，$b_i = b_j$ 时 $s_is_j = +1$、取值为 $0$，$b_i \neq b_j$ 时 $s_is_j = -1$、取值为 $1$。再把 $b_i = (1-s_i)/2$ 代入第一式：

$$\frac{1-s_i}{2} + \frac{1-s_j}{2} - 2\cdot\frac{(1-s_i)(1-s_j)}{4} = \frac{2 - s_i - s_j}{2} - \frac{1 - s_i - s_j + s_is_j}{2} = \frac{1 - s_is_j}{2},$$

两个表达式确实一致。MaxCut 的目标函数是所有边的切断指示符之和：

$$C(\mathbf{b}) = \sum_{(i,j)\in E} \frac{1 - s_i s_j}{2}.$$

现在把经典变量提升为算符。计算基 $|\mathbf{b}\rangle = |b_1 b_2 \cdots b_n\rangle$ 满足 $Z_i|\mathbf{b}\rangle = (1 - 2b_i)|\mathbf{b}\rangle = s_i|\mathbf{b}\rangle$（由 $Z|0\rangle = +|0\rangle$、$Z|1\rangle = -|1\rangle$ 直接得到）。因此 $Z_i$ 正是自旋变量 $s_i$ 对应的算符，而 $Z_iZ_j$ 对基矢的本征值就是 $s_is_j$。把逐边求和中的 $s_i s_j$ 替换为 $Z_iZ_j$，得到量子化的成本哈密顿量

$$H_C = \sum_{(i,j)\in E} \frac{1 - Z_i Z_j}{2} = \frac{|E|}{2}\,I - \frac{1}{2}\sum_{(i,j)\in E} Z_i Z_j.$$

它是对角的，且 $H_C|\mathbf{b}\rangle = C(\mathbf{b})|\mathbf{b}\rangle$：每条边贡献一个 $-\frac{1}{2}Z_iZ_j$ 项加上常数 $\frac{1}{2}$，一一对应。

对一般的 QUBO（Quadratic Unconstrained Binary Optimization，二次无约束二值优化）问题，同样的推导逐项展开即可。设

$$C(\mathbf{b}) = \sum_{i} Q_{ii}\, b_i + \sum_{i<j} Q_{ij}\, b_i b_j.$$

把 $b_i$ 提升为算符 $(I - Z_i)/2$，二次项用恒等式展开：

$$b_i b_j \;\to\; \frac{(I - Z_i)(I - Z_j)}{4} = \frac{1}{4}\big(I - Z_i - Z_j + Z_iZ_j\big).$$

代入并按 $I$、$Z_i$、$Z_iZ_j$ 归类系数，得到 Ising 形式

$$H_C = c_0\, I + \sum_i h_i\, Z_i + \sum_{i<j} J_{ij}\, Z_i Z_j,$$

其中

$$c_0 = \frac{1}{2}\sum_i Q_{ii} + \frac{1}{4}\sum_{i<j} Q_{ij}, \qquad h_i = -\frac{Q_{ii}}{2} - \frac{1}{4}\sum_{j>i} Q_{ij} - \frac{1}{4}\sum_{j<i} Q_{ji}, \qquad J_{ij} = \frac{Q_{ij}}{4}.$$

我们用 MaxCut 核对一遍这组系数：MaxCut 的 QUBO 形式是 $C = \sum_{(i,j)\in E}(b_i + b_j - 2b_ib_j)$，即 $Q_{ii} = \deg(i)$（每个顶点从其邻边各贡献一个 $b_i$）、$Q_{ij} = -2$（对每条边）。代入上式：

$$h_i = -\frac{\deg(i)}{2} - \frac{1}{4}\sum_{j\sim i}(-2) = -\frac{\deg(i)}{2} + \frac{\deg(i)}{2} = 0, \qquad J_{ij} = \frac{-2}{4} = -\frac{1}{2},$$

$$c_0 = \frac{1}{2}\sum_i \deg(i) + \frac{1}{4}\sum_{(i,j)\in E}(-2) = |E| - \frac{|E|}{2} = \frac{|E|}{2},$$

于是 $H_C = \frac{|E|}{2}I - \frac{1}{2}\sum_{(i,j)\in E}Z_iZ_j$，与逐边推导完全一致。这也解释了为什么 MaxCut 的 QAOA 哈密顿量没有单比特（场）项：无向图的切断数在同构翻转下不变。

### 第二步：构造 QAOA 电路

初始态取 $|s\rangle = |+\rangle^{\otimes n} = H^{\otimes n}|0\rangle^{\otimes n}$，即混合哈密顿量的基态（按 $H_B = -\sum_i X_i$ 的约定）。

$p$ 层电路的第 $l$ 层依次施加问题层和混合层。因为 $H_C$ 的各项（以及 $H_B$ 的各项）分别互相内对易，指数可以直接拆开：

1. 问题层 $e^{-i\gamma_l H_C} = e^{-i\gamma_l c_0}\cdot \prod_{(i,j)\in E} e^{-i\gamma_l J_{ij} Z_iZ_j}\cdot \prod_i e^{-i\gamma_l h_i Z_i}$（全局相位 $e^{-i\gamma_l c_0}$ 可丢弃）；
2. 混合层 $e^{-i\beta_l H_B} = \prod_i e^{+i\beta_l X_i}$（按 $H_B = -\sum X_i$ 的约定）。

逐门实现需要以下两个门综合恒等式。

第一个恒等式把两比特 $ZZ$ 旋转化归为单比特 $R_z$ 加两个 CNOT。记 $R_z(\phi) = e^{-i\phi Z/2}$，我们断言

$$e^{-i\phi\, Z_i Z_j/2} = \mathrm{CNOT}_{i\to j}\,\big(I_i \otimes R_{z,j}(\phi)\big)\,\mathrm{CNOT}_{i\to j}.$$

**证明**分两步。第一步，我们证明共轭恒等式 $\mathrm{CNOT}_{i\to j}\, Z_j\, \mathrm{CNOT}_{i\to j} = Z_iZ_j$。对任意基矢 $|b_ib_j\rangle$，$\mathrm{CNOT}$ 把它映为 $|b_i, b_j \oplus b_i\rangle$，于是

$$\mathrm{CNOT}\, Z_j\, \mathrm{CNOT}\,|b_ib_j\rangle = \mathrm{CNOT}\, Z_j |b_i, b_j\oplus b_i\rangle = (-1)^{b_j \oplus b_i}\,\mathrm{CNOT}|b_i, b_j\oplus b_i\rangle = (-1)^{b_i\oplus b_j}|b_ib_j\rangle = Z_iZ_j|b_ib_j\rangle,$$

其中最后一步用了 $(-1)^{b_i + b_j} = (-1)^{b_i \oplus b_j}$（因为 $(-1)^{2b} = 1$）。第二步，共轭与幂运算可交换：$\mathrm{CNOT}\, A^m\, \mathrm{CNOT} = (\mathrm{CNOT}\, A\, \mathrm{CNOT})^m$（由 $(\mathrm{CNOT}\,A\,\mathrm{CNOT})(\mathrm{CNOT}\,B\,\mathrm{CNOT}) = \mathrm{CNOT}\,AB\,\mathrm{CNOT}$ 逐次拼接即得），再对指数级数逐项共轭，得 $\mathrm{CNOT}\, e^{-i\phi Z_j/2}\,\mathrm{CNOT} = e^{-i\phi\, \mathrm{CNOT}Z_j\mathrm{CNOT}/2} = e^{-i\phi Z_iZ_j/2}$。证毕。

因此 MaxCut 问题层的每条边需要 2 个 CNOT 加 1 个 $R_z$；按 $H_C = \sum_{(i,j)}\frac{1 - Z_iZ_j}{2}$ 的写法，每条边的因子是 $e^{-i\gamma/2}\cdot e^{+i\gamma Z_iZ_j/2}$，对应上式取 $\phi = -\gamma$，即一个角度为 $-\gamma$ 的 $R_z$（角度记号的约定务必与文献对照：若把边因子写成 $e^{-i\theta Z_iZ_j}$ 而非 $e^{-i\theta Z_iZ_j/2}$，则 $R_z$ 的角度是 $2\theta$——本教程统一采用 $e^{-i\theta G/2}$ 的约定）。

第二个恒等式关于混合层：$e^{+i\beta X} = R_x(-2\beta)$（由 $R_x(\phi) := e^{-i\phi X/2}$，取 $\phi = -2\beta$），即每量子比特一个 $R_x(-2\beta)$ 门。同理，问题层中的场项 $e^{-i\gamma h_i Z_i} = R_z(2\gamma h_i)$。

于是 $p$ 层 QAOA 的总门数为 $O(p\cdot(|E| + n))$。

### 第三步：参数优化

我们选择参数 $(\vec{\gamma}, \vec{\beta})$ 使期望成本最大：

$$\text{maximize}\quad F(\vec{\gamma}, \vec{\beta}) = \langle\vec{\gamma}, \vec{\beta}|\, H_C\, |\vec{\gamma}, \vec{\beta}\rangle.$$

可选的优化方法包括：

- 梯度方法：$\partial F/\partial\gamma_l$、$\partial F/\partial\beta_l$ 可以用参数平移规则精确计算——$e^{-i\gamma_l H_C}$ 与 $e^{-i\beta_l H_B}$ 的生成本征值谱不限于两个值，严格的两项公式一般不适用，但可以把层拆成逐边的 $e^{-i\gamma J_{ij}Z_iZ_j/2}$（生成元 $Z_iZ_j$ 谱为 $\{\pm1\}$）再对每个门分别应用 $\frac{\partial E}{\partial\theta} = \frac{1}{2}[E(\theta+\frac{\pi}{2}) - E(\theta-\frac{\pi}{2})]$，最后按链式法则相加（共享参数的处理见[第 2 章附录：参数平移法则](../ch02-quantum-nn/parameter-shift-appendix.md)）；
- COBYLA 等无梯度优化器：每次只需能量估计值，实现简单，是最常见的默认选择；
- 利用对称性缩减搜索区间：$\beta \to \beta + \frac{\pi}{2}$ 对任意对角 $H_C$ 都是严格对称——$e^{-i(\beta+\pi/2)H_B}$ 与 $e^{-i\beta H_B}$ 只差一个全局相位与全局翻转 $X^{\otimes n}$（由 $e^{i(\pi/2)X} = iX$ 逐比特相乘得到），而 $X^{\otimes n}$ 与任何对角算符对易、且保持 $|+\rangle^{\otimes n}$ 不变，故 $F$ 不变。$\gamma \to \gamma + \pi$ 的对称则要求所有顶点度数奇偶性一致：此时 $e^{-i\pi H_C} = \prod_{(i,j)\in E} Z_iZ_j = \prod_i Z_i^{\deg(i)}$ 是恒等或全局翻转，同样不改变 $F$（3 正则图、环图都满足）。

### 第四步：测量与经典后处理

参数优化到 $(\vec{\gamma}^*, \vec{\beta}^*)$ 后，我们制备 $|\vec{\gamma}^*, \vec{\beta}^*\rangle$ 并在计算基上测量 $N$ 次，得到比特串样本 $\{\mathbf{z}^{(1)}, \ldots, \mathbf{z}^{(N)}\}$。经典后处理分四步：

1. 统计每个比特串的出现次数 $n_{\mathbf{z}}$（$\sum_{\mathbf{z}} n_{\mathbf{z}} = N$）；
2. 对每条边 $(i,j)$，估计 $\widehat{\langle Z_iZ_j\rangle} = \frac{1}{N}\sum_{\mathbf{z}} n_{\mathbf{z}}\, (-1)^{z_i \oplus z_j}$，其中 $z_i$ 是样本第 $i$ 位比特（由 $Z_iZ_j|\mathbf{z}\rangle = (-1)^{z_i + z_j}|\mathbf{z}\rangle = (-1)^{z_i\oplus z_j}|\mathbf{z}\rangle$）；
3. 组装能量估计 $\widehat{F} = \sum_{(i,j)\in E} \frac{1 - \widehat{\langle Z_iZ_j\rangle}}{2}$；
4. 输出样本中 $C(\mathbf{z})$ 最大的比特串作为候选解。

后处理公式与"直接平均"是同一件事：把第 2、3 步合并，

$$\widehat{F} = \frac{1}{N}\sum_{\mathbf{z}} n_{\mathbf{z}} \sum_{(i,j)\in E}\frac{1 - (-1)^{z_i\oplus z_j}}{2} = \frac{1}{N}\sum_{\mathbf{z}} n_{\mathbf{z}}\, C(\mathbf{z}),$$

即 $\widehat{F}$ 恰是样本成本的平均值；而第 4 步的"样本最优"总是不小于样本平均值。期望值 $F(\vec{\gamma}^*,\vec{\beta}^*)$ 刻画的是**平均解质量**，采样后的 best-of-$N$ 则进一步利用分布的高位尾部。

一个可以手工算透的数值核对（也验证了后处理公式）：三角形图 $K_3$ 在 $p = 1$ 的最优参数处（下一节我们推导出 $\gamma^* = \frac{1}{2}\arccos\frac{1}{3} \approx 0.6155$、$\beta^* = \frac{\gamma^*}{2} + \frac{\pi}{2} \approx 1.8786$），末态在 $6$ 个切断数为 $2$ 的最优串（$|001\rangle, |010\rangle, |100\rangle, |011\rangle, |101\rangle, |110\rangle$）上均匀分布（各 $\frac16$），在 $|000\rangle$、$|111\rangle$ 上振幅为零。设 $N = 12$ 次测量中这 $6$ 个串各出现 $2$ 次。以边 $(0,1)$ 为例：$|001\rangle$ 与 $|110\rangle$ 两端相同（贡献 $+1$），其余 $4$ 个串两端不同（贡献 $-1$），于是

$$\widehat{\langle Z_0Z_1\rangle} = \frac{2\cdot(+1) + 2\cdot(-1)\cdot 4 + 2\cdot(+1)}{12} = \frac{2 - 8 + 2}{12} = -\frac{1}{3},$$

三条边对称相同，故 $\widehat{F} = 3\cdot\frac{1-(-1/3)}{2} = 3\cdot\frac{4/3}{2} = 2$。另一方面每个样本的 $C(\mathbf{z}) = 2$，样本平均也是 $2$。两条路径一致，且都等于 $K_3$ 的最优值。

## 理论分析

### 近似比

对一个具体的图实例，$p$ 层 QAOA 的（最优参数下的）表现用近似比（approximation ratio）衡量：

$$r_p = \frac{\max_{\vec{\gamma},\vec{\beta}} F_p(\vec{\gamma}, \vec{\beta})}{C_{\max}},$$

其中 $C_{\max}$ 是全局最优值。研究更关心对所有实例取下界后的最坏情形保证。

**定理（Farhi et al., 2014）** 对所有 3 正则图（每个顶点度数恰为 $3$ 的图）上的 MaxCut，$p = 1$ 层 QAOA 的最坏情形近似比为 $r_1 = 0.6924$。

作为对比，经典 Goemans-Williamson 半定规划算法的近似比为 $0.8786$，因此 $p = 1$ 的 QAOA 尚不如经典算法。但 QAOA 的近似比随 $p$ 单调不减（参数空间嵌套：更深的层可以把浅层的参数复制并把多余的转角设为零），并且有如下极限定理。

**定理（Farhi et al., 2014）** 当 $p \to \infty$ 时，最优参数下的 QAOA 达到全局最优：$\lim_{p\to\infty} \max_{\vec\gamma,\vec\beta} F_p = C_{\max}$，即 $r_p \to 1$。

### 从绝热演化到 QAOA：离散化推导

$p \to \infty$ 的收敛定理来自 QAOA 与绝热量子计算的联系，我们把推导完整写出来。

绝热演化从容易制备的基态出发，缓慢插值到问题哈密顿量。取（沿用 $H_B = -\sum_i X_i$ 的约定，其基态为 $|+\rangle^{\otimes n}$）

$$H(s) = (1 - s)\, H_B + s\, H_C, \qquad s: 0 \to 1,$$

系统按薛定谔方程演化 $i\frac{d}{dt}|\psi(t)\rangle = H(s(t))|\psi(t)\rangle$。绝热定理指出：若演化总时间 $T$ 相对最小谱隙足够大（经验形式为 $T \gtrsim \max_s \|\partial_s H\| / g_{\min}^2$，其中 $g_{\min}$ 是 $H(s)$ 的最小瞬时能隙；更严格的界含 $g_{\min}^3$ 因子），末态以高保真度落在 $H_C$ 的基态上——也就是成本最小的解上。

QAOA 是这条路径的一阶 Trotter 离散化。把时间区间 $[0, T]$ 等分为 $p$ 段，每段长度 $\Delta t = T/p$，并把日程近似为分段常数：第 $l$ 段内 $s \equiv s_l$。第 $l$ 段的演化子为

$$U_l = e^{-i\Delta t\, H(s_l)} = e^{-i\Delta t\,(1-s_l) H_B - i\Delta t\, s_l H_C}.$$

对两个不对易项之和的指数用一阶 Trotter 分解 $e^{A+B} = e^A e^B + O(\|[A,B]\|)$（其误差界即 VQE 一篇引用的 $\|e^{A+B} - e^Ae^B\| \le \frac{1}{2}\|[A,B]\|e^{\|A\|+\|B\|}$），这里 $A = -i\Delta t(1-s_l)H_B$、$B = -i\Delta t\, s_l H_C$，且 $[A, B] = -\Delta t^2 (1-s_l)s_l\, [H_B, H_C]$，于是

$$U_l = e^{-i\beta_l H_B}\cdot e^{-i\gamma_l H_C} + O(\Delta t^3), \qquad \beta_l := (1 - s_l)\Delta t, \quad \gamma_l := s_l\,\Delta t.$$

把 $p$ 段乘起来（最早的段在矩阵乘积最右侧），得到的正是 QAOA 态，总 Trotter 误差为 $O(p\cdot\Delta t^3) = O(T^3/p^2)$：当 $p$ 增大（$\Delta t$ 减小）时，任何绝热日程的离散化误差都趋于零。

现在可以证明收敛定理的思路：对任意固定 $T$ 与日程，离散化绝热演化对应的 QAOA 参数 $(\vec{\gamma}, \vec{\beta})$ 是 $2p$ 维参数空间中的一个点，因此

$$\max_{\vec{\gamma},\vec{\beta}} F_p(\vec{\gamma},\vec{\beta}) \;\ge\; F\big(\text{离散化绝热演化的末态}\big) \;\xrightarrow[p \to \infty]{}\; F\big(\text{连续绝热演化末态}\big).$$

再令 $T \to \infty$，绝热定理保证右端趋于 $C_{\max}$。两个极限合并即得 $r_p \to 1$。需要说明的是，我们在此把"$T$ 与 $p$ 同时增大时离散化误差与绝热误差可以同时压小"作为证明思路陈述；严格的版本需要对日程与步长的联合选取做细致分析。

### 优化景观的困难

QAOA 只有 $2p$ 个参数，不落入 McClean 等人针对随机深电路的 Barren Plateau 定理的适用范围（该定理要求参数数量随 $n$ 增长的全局随机电路）。QAOA 优化面临的实际困难是另外三类：

- 优化景观非凸，存在大量局部极值，随图规模增大，不同初始点的最优参数盆地增多，随机初始化容易陷入次优盆地；
- 噪声会压缩 $F$ 的动态范围，使有效梯度变小（"噪声致平"）；
- 最优参数随问题规模与实例变化，不能简单外推（参数集中现象只在特定问题族中出现）。

常用的缓解策略包括：用绝热日程（线性斜坡 $\gamma_l \propto s_l\Delta t$、$\beta_l \propto (1-s_l)\Delta t$）初始化参数；逐层训练（先优化浅层，固定后加深）；利用 $\beta$ 的 $\pi/2$ 周期（以及度数奇偶一致图中 $\gamma$ 的 $\pi$ 周期）约减搜索空间。

## 具体例子

### MaxCut：三角形图 $K_3$ 的完整 $p=1$ 分析

三角形图有 $3$ 个顶点、$3$ 条边，由逐边公式：

$$H_C = \frac{3}{2}I - \frac{1}{2}(Z_0Z_1 + Z_1Z_2 + Z_2Z_0),$$

全局最优切断数为 $C_{\max} = 2$（奇圈不可能切断全部三条边；任取两个顶点同侧、第三个异侧即得）。

我们把 $p = 1$ 的能量 $F(\gamma, \beta) = \langle\gamma,\beta|H_C|\gamma,\beta\rangle$ 完整推导成闭式。推导利用对称性把 $8$ 维空间约化到二维不变子空间。

**第一步：不变子空间。** 记

$$|a\rangle = \frac{|000\rangle + |111\rangle}{\sqrt 2}, \qquad |b\rangle = \frac{|001\rangle + |010\rangle + |100\rangle + |011\rangle + |101\rangle + |110\rangle}{\sqrt 6}.$$

初态 $|s\rangle = |+\rangle^{\otimes 3} = \frac{1}{\sqrt 8}\sum_{\mathbf{z}}|\mathbf{z}\rangle = \frac{1}{2}|a\rangle + \frac{\sqrt3}{2}|b\rangle$（两个系数分别由 $\langle a|s\rangle = \frac{1}{\sqrt2}\cdot\frac{2}{\sqrt8} = \frac12$、$\langle b|s\rangle = \frac{1}{\sqrt6}\cdot\frac{6}{\sqrt8} = \frac{\sqrt3}{2}$ 算出）。$H_C$ 是对角的、且在每个顶点同时翻转的变换 $X^{\otimes 3}$ 下不变，$e^{-i\beta H_B}$ 是置换对称的，因此演化不离开 $\mathrm{span}\{|a\rangle, |b\rangle\}$。

**第二步：$H_C$ 在子空间上的作用。** $|000\rangle$、$|111\rangle$ 的切断数为 $0$，六个混合串的切断数为 $2$（每个混合串恰好断开两条边：两条同色边不断开、两条异色边断开），所以 $H_C|a\rangle = 0$、$H_C|b\rangle = 2|b\rangle$，问题层只给 $|b\rangle$ 乘上相位：

$$e^{-i\gamma H_C}|s\rangle = \frac{1}{2}|a\rangle + \frac{\sqrt3}{2}e^{-2i\gamma}|b\rangle.$$

**第三步：混合层矩阵。** 我们逐项计算 $\Sigma X = X_0 + X_1 + X_2$ 在子空间上的矩阵元。$\Sigma X\,|a\rangle$：$X$ 作用在 $|000\rangle + |111\rangle$ 的每一项上给出一个混合串（如 $X_0|000\rangle = |100\rangle$），三个 $X$ 共给出全部六个混合串，因此 $\Sigma X|a\rangle = \frac{\sqrt6}{\sqrt2}|b\rangle = \sqrt3\,|b\rangle$。$\Sigma X\,|b\rangle$：把六个混合串各自翻转三位，共 $18$ 个像，其中 $|000\rangle$ 与 $|111\rangle$ 各出现 $3$ 次（例如 $|001\rangle$ 翻转唯一的 $1$ 得 $|000\rangle$），其余 $12$ 个像都是混合串、每个恰出现 $2$ 次，因此 $\Sigma X|b\rangle = \frac{1}{\sqrt6}(3|000\rangle + 3|111\rangle + 2\sum_{\text{mixed}}) = \sqrt3\,|a\rangle + 2|b\rangle$。于是

$$\Sigma X\big|_{\mathrm{span}\{a,b\}} = \begin{pmatrix} 0 & \sqrt3 \\ \sqrt3 & 2 \end{pmatrix},$$

其本征值为 $3$（迹与行列式 $\mathrm{tr} = 2$、$\det = -3$，解 $\lambda^2 - 2\lambda - 3 = 0$ 得 $\lambda = \{3, -1\}$），本征矢分别为 $|u_3\rangle = \frac{1}{2}|a\rangle + \frac{\sqrt3}{2}|b\rangle = |s\rangle$（直接验证矩阵作用得 $3|u_3\rangle$）与 $|u_{-1}\rangle = -\frac{\sqrt3}{2}|a\rangle + \frac{1}{2}|b\rangle$。混合层因此只给两个分量乘相位 $e^{-3i\beta}$（注意 $H_B = -\Sigma X$ 时相应为 $e^{+3i\beta}$；我们这里直接按 $e^{-i\beta\Sigma X}$ 计算，与 $\beta \to -\beta$ 的约定等价）与 $e^{+i\beta}$。

**第四步：闭式能量。** 把 $|\psi\rangle = e^{-3i\beta}c_3|u_3\rangle + e^{i\beta}c_{-1}|u_{-1}\rangle$ 代入 $F = \langle\psi|H_C|\psi\rangle$，所需的三个矩阵元为 $\langle u_3|H_C|u_3\rangle = \frac32$、$\langle u_{-1}|H_C|u_{-1}\rangle = \frac12$、$\langle u_3|H_C|u_{-1}\rangle = \frac{\sqrt3}{2}$（由 $H_C|u_3\rangle = \frac{\sqrt3}{2}\cdot 2|b\rangle$ 型的逐项计算得到）。系数为

$$c_3 = \frac{1}{4} + \frac{3}{4}e^{-2i\gamma}, \qquad c_{-1} = \frac{\sqrt3}{4}\big(e^{-2i\gamma} - 1\big).$$

利用 $|c_3|^2 = \frac{10 + 6\cos 2\gamma}{16}$、$|c_{-1}|^2 = \frac{3}{4}\sin^2\gamma$、以及 $c_3^* c_{-1} = \frac{\sqrt3}{4}\big(\frac12 + \frac14 e^{-2i\gamma} - \frac34 e^{2i\gamma}\big)$，代入并整理（半角恒等式 $\sin^2\gamma = \frac{1-\cos2\gamma}{2}$）得到

$$F(\gamma, \beta) = \frac{3}{8}\big(3 + \cos 2\gamma\big) + \frac{3}{8}\cos 4\beta + \frac{3}{16}\cos(4\beta - 2\gamma) - \frac{9}{16}\cos(4\beta + 2\gamma).$$

两个极限情形可以核对：$\gamma = 0$ 时问题层为恒等，$F$ 必须恒为 $\frac32$（随机比特串平均切断 $3 \times \frac12 = 1.5$ 条边）——代入 $\cos$ 项相消确为 $\frac32$；$\beta = 0$ 时混合层为恒等，$H_C$ 与 $e^{-i\gamma H_C}$ 对易，$F = \langle s|H_C|s\rangle = \frac32$——同样成立。

**第五步：最大化。** 在子流形 $4\beta = 2\gamma + 2\pi$（即 $\beta = \frac{\gamma}{2} + \frac{\pi}{2}$）上，三个 $\cos$ 项分别化为 $\cos 2\gamma$、$1$、$\cos 4\gamma$，代入 $\cos 4\gamma = 2\cos^2 2\gamma - 1$ 并记 $c = \cos 2\gamma$：

$$F = \frac{30}{16} + \frac{3}{4}c - \frac{9}{8}c^2.$$

对 $c \in [-1, 1]$ 求导 $\frac{dF}{dc} = \frac34 - \frac94 c = 0$ 得 $c = \frac13$，此时

$$F_{\max} = \frac{30}{16} + \frac{3}{4}\cdot\frac{1}{3} - \frac{9}{8}\cdot\frac{1}{9} = \frac{30}{16} + \frac{4}{16} - \frac{2}{16} = \frac{32}{16} = 2 = C_{\max}.$$

对应参数 $\gamma^* = \frac{1}{2}\arccos\frac13 \approx 0.6155$、$\beta^* = \frac{\gamma^*}{2} + \frac{\pi}{2} \approx 1.8786$。我们在 $\gamma \in [0, \pi)$、$\beta \in [0, 2\pi)$ 上的细网格数值搜索（配合黄金分割细化）确认这是全局最大值：$p = 1$ 的 QAOA 在三角形图上达到精确最优，近似比为 $1$。态矢量模拟还显示，此时六个最优串上的概率各为 $\frac{1}{6}$、$|000\rangle$ 与 $|111\rangle$ 上为零——由于 $H_C$ 的最大本征值只属于这六个串，$F = 2$ 必然蕴含这样的支撑集，与第四步末尾的数值核对互相印证。$p \ge 2$ 时最优值保持为 $2$（近似比单调性）。

### MaxCut：环图 $C_6$

环图 $C_6$ 有 $6$ 个顶点、$6$ 条边。它是二部图，把顶点按奇偶分成两组即可切断所有边，故 $C_{\max} = 6$（恰有两个最优串：$|010101\rangle$ 型与 $|101010\rangle$ 型）。对 $p = 1$、$2$、$3$ 层的 QAOA 做态矢量数值模拟（在参数空间多起点搜索最优），得到：

| 层数 $p$ | 最优期望 $\max F_p$ | 近似比 $r_p$ |
|:---:|:---:|:---:|
| $1$ | $4.500$ | $0.750$ |
| $2$ | $5.000$ | $\approx 0.833$ |
| $3$ | $6.000$ | $1$ |

可以看到近似比随 $p$ 严格提升，且在 $p = 3$ 时已经达到精确最优：此后的层不再带来改进。$p = 1$ 的值 $4.5 = \frac34 C_{\max}$ 与 $p = 2$ 的 $5 = \frac56 C_{\max}$ 都是精确的有理数，这来自环图的高度对称性；一般图上的最优值没有这么整洁，需要数值优化。

## QAOA 的变体

### Grover 混合算符变体（Grover-mixer QAOA）

把标准混合层 $e^{-i\beta H_B}$ 替换为 Grover 扩散型算符 $D = 2|s\rangle\langle s| - I$（$|s\rangle = |+\rangle^{\otimes n}$）的指数 $e^{-i\beta D}$。$D$ 与任意对角 $H_C$ 的对易关系更好刻画，适合约束优化中保持可行子空间。

### Multi-Angle QAOA（ma-QAOA）

标准 QAOA 每层内所有边共享同一个 $\gamma_l$、所有量子比特共享同一个 $\beta_l$；ma-QAOA 为 $H_C$ 的每个项、每个量子比特分配独立角度，参数数量从 $2p$ 增至 $O(p\cdot(|E| + n))$，表达能力更强（对同样的 $p$ 可以达到不低于标准 QAOA 的 $F$），但优化更困难。

### Warm-Start QAOA

用经典近似算法的解构造初始态（例如把 Goemans-Williamson 解的四舍五入向量转化为各量子比特的偏置初态），替代均匀叠加 $|+\rangle^{\otimes n}$，把经典信息"注入"量子计算。初始态更接近优质解所在的子空间，通常能加快收敛并提升浅层表现。

### Recursive QAOA（RQAOA）

迭代地：运行 QAOA、测量关联函数 $\langle Z_iZ_j\rangle$、把 $|\langle Z_iZ_j\rangle|$ 最大的变量对按符号关系固定（$z_i = \pm z_j$）、在缩小的图上重复，直到规模足够小可以精确求解。RQAOA 在某些图族上的表现超过 Goemans-Williamson，也被用来研究低深度 QAOA 的能力边界。

## 复杂度分析

| 组件 | 资源 |
|------|------|
| 量子比特 | $n$ |
| 单层门数 | $O(|E| + n)$（每边 2 个 CNOT + 1 个 $R_z$，每比特 1 个 $R_x$） |
| $p$ 层电路深度 | $O(p\cdot\Delta)$，$\Delta$ 为最大度（近邻架构下） |
| 单次能量估计的测量次数 | $O(\log(1/\delta)/\varepsilon^2)$（Hoeffding，$\varepsilon$ 精度、$\delta$ 失败率） |
| 参数优化迭代数 | 多项式（经验上；无理论保证） |

总代价：若优化器迭代 $T_{\text{opt}}$ 次、每次能量估计用 $m$ 次测量，则总电路执行次数为 $O(T_{\text{opt}}\cdot m)$，每次执行的深度为 $O(p\cdot\Delta)$。可以看到测量开销（$m \sim 1/\varepsilon^2$，推导见 VQE 一篇的测量开销一节）往往主导总时间。

## 当前进展与挑战

### 理论进展

| 年份 | 结果 |
|------|------|
| 2014 | Farhi, Goldstone, Gutmann 提出 QAOA：3 正则图 MaxCut 的 $p = 1$ 近似比 $0.6924$，$p \to \infty$ 收敛到最优 |
| 2016 | Farhi & Harrow：$p = O(\mathrm{polylog}\, n)$ 的 QAOA 输出分布难以被经典算法忠实采样（除非复杂度类坍塌），是"量子优势"可能性的证据 |
| 2019 | Hastings：固定深度 $p$ 的 QAOA 具有局域性（可观测量只依赖半径 $O(p)$ 的邻域），因此对相应实例存在可匹敌的经典局部算法——低深度 QAOA 的优势存在理论限制 |
| 2024 | Blekos et al. 在 Physics Reports 发表 QAOA 及其变体的系统综述 |

### 实验挑战

1. NISQ 噪声：门错误率 $\sim 10^{-3}$ 累积限制有效深度 $p$，噪声同时压低可分辨的能量差；
2. 优化困难：非凸景观、局部极值与参数不可转移；
3. 读出噪声：测量错误降低关联函数 $\langle Z_iZ_j\rangle$ 的估计精度，需要读出误差缓解；
4. 规模匹配：对有实际价值的实例（$n$ 数百以上、连通度高），当前设备的量子比特数与连接拓扑都不足。

## 总结

QAOA 把组合优化编码为对角成本哈密顿量与混合哈密顿量的交替演化，其层结构可以从绝热演化的一阶 Trotter 离散化严格导出，因此 $p \to \infty$ 时收敛到精确最优；对小实例（如三角形图）可以完整解出闭式能量并验证 $p = 1$ 即达精确最优。浅层（小 $p$）时的最坏情形保证目前不敌最好的经典近似算法，但warm start、递归与多角度等变体不断缩小差距。它为量子-经典混合优化算法提供了清晰的设计范式，也是衡量 NISQ 设备与噪声影响的标准应用之一。

---

**参考文献：**

1. Farhi, E., Goldstone, J., & Gutmann, S. (2014). *A quantum approximate optimization algorithm.* arXiv:1411.4028.
2. Farhi, E., & Harrow, A. W. (2016). *Quantum supremacy through the quantum approximate optimization algorithm.* arXiv:1602.07674.
3. Basso, J., Farhi, E., Marwaha, K., Villalonga, B., & Zhou, L. (2021). *The quantum alternating operator ansatz with Grover operators.* arXiv:2108.06811.
4. Blekos, K., et al. (2024). *A review on quantum approximate optimization algorithm and its variants.* Physics Reports, 1068, 1-66.
---

> 返回目录：[量子计算算法教程系列](https://chenzhaoyun.com/index.php/archives/54/)