QAOA（Quantum Approximate Optimization Algorithm，量子近似优化算法）由 Edward Farhi、Jeffrey Goldstone 和 Sam Gutmann 于 2014 年提出，是针对组合优化问题设计的变分量子算法。它在 NISQ（近期含噪中等规模量子）设备上具有实际可行性，并在理论上可证明对某些问题优于经典近似算法。

问题背景：组合优化

许多重要的计算问题可以表述为组合优化：

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

其中 $C(\mathbf{z})$ 是成本函数（或目标函数）。

经典难题：

• Max-Cut：将图的顶点分为两组，使连接两组的边数最多
• Max-SAT：给定布尔公式，找到满足最多子句的变量赋值
• 旅行商问题（TSP）：找到访问所有城市的最短路线
• 图着色、背包问题、调度问题 等

这些问题大多是 NP-Hard，经典精确算法需要指数时间，经典近似算法给出的近似比有理论限制。

QAOA 的目标是：用 $p$ 层量子电路（$p$ 为小整数），以多项式资源找到质量优于经典近似算法的解。

核心思想：交替演化

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

问题哈密顿量 $H_C$：将目标函数编码为对角矩阵

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

$$\text{(或等价地用 Ising 形式：} H_C = \sum_{(i,j) \in E} \frac{1}{2}(I - Z_i Z_j) + \cdots\text{)}$$

混合哈密顿量 $H_B$：驱动量子态在计算基之间跃迁

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

$p$ 层 QAOA 电路：

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

参数向量 $\vec{\gamma} = (\gamma_1, \ldots, \gamma_p)$，$\vec{\beta} = (\beta_1, \ldots, \beta_p)$。

直觉：$e^{-i\gamma H_C}$ 在计算基上施加依赖于成本的相位（“标记好解”），$e^{-i\beta H_B}$ 在 $X$ 基上混合态（“扩散到其他解”）。交替施加类似于 Grover 的振幅放大，但参数可调。

算法步骤详解

第一步：问题编码

将组合优化问题编码为 Ising 哈密顿量。以 Max-Cut 为例：

给定图 $G = (V, E)$，Max-Cut 目标函数：

$$C(\mathbf{z}) = \sum_{(i,j) \in E} \frac{1 - z_i z_j}{2}, \quad z_i \in \{+1, -1\}$$

映射到量子比特（$Z_i |z_i\rangle = z_i |z_i\rangle$）：

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

对一般 QUBO（Quadratic Unconstrained Binary Optimization）：

$$C(\mathbf{z}) = \sum_{i} h_i z_i + \sum_{i

对应 $H_C = \sum_i h_i Z_i + \sum_{i

第二步：构造 QAOA 电路

初始态：$|s\rangle = |+\rangle^{\otimes n} = H^{\otimes n}|0\rangle^{\otimes n}$。

$p$ 层电路的第 $l$ 层：

1. 问题层：$e^{-i\gamma_l H_C} = \prod_{(i,j)} e^{-i\gamma_l Z_i Z_j / 2} \cdot \prod_i e^{-i\gamma_l h_i Z_i}$
   • $e^{-i\gamma Z_i Z_j / 2}$ 由 2 个 CNOT + 1 个 $R_z(2\gamma)$ 实现
   • $e^{-i\gamma h_i Z_i}$ 由 1 个 $R_z(2\gamma h_i)$ 实现
2. 混合层：$e^{-i\beta_l H_B} = \prod_i e^{-i\beta_l X_i}$
   • $e^{-i\beta X_i}$ 由 1 个 $R_x(2\beta)$ 实现

总门数（$p$ 层）：$O(p \cdot (|E| + n))$

第三步：参数优化

选择参数 $(\vec{\gamma}, \vec{\beta})$ 使期望值 $\langle H_C \rangle$ 最大：

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

优化方法：

• 梯度下降：计算 $\partial F / \partial \gamma_l$，$\partial F / \partial \beta_l$
• COBYLA：无梯度的经典优化器
• 参数平移规则：$\frac{\partial F}{\partial \theta} = \frac{F(\theta + \pi/2) - F(\theta - \pi/2)}{2}$

第四步：测量与解提取

测量得到比特串 $\mathbf{z}$，计算 $C(\mathbf{z})$。多次采样取最优。期望值 $F(\vec{\gamma}, \vec{\beta})$ 给出平均解质量。

理论分析

近似比

近似比定义为：

$$r_p = \frac{\min_{\text{所有实例}} F_p(\vec{\gamma}^*, \vec{\beta}^*)}{C_{\max}}$$

其中 $C_{\max}$ 是全局最优值。

定理（Farhi et al., 2014）：对任意图 $G$，$p = 1$ 层 QAOA 的近似比 $r_1 \ge 0.6924$（对 Max-Cut）。

对比经典 Goemans-Williamson 算法的近似比 $\approx 0.8786$，$p = 1$ QAOA 不如经典算法。但随着 $p$ 增加：

定理：当 $p \to \infty$，QAOA 的近似比趋于 1（全局最优）。

$p$ 层 QAOA 与绝热演化的关系

QAOA 可以视为绝热量子计算的离散化。绝热演化从 $H_B$ 的基态（$|+\rangle^{\otimes n}$）出发，缓慢插值到 $H_C$：

$$H(s) = (1-s) H_B + s H_C, \quad s \in [0, 1]$$

绝热定理保证：若演化足够慢（时间 $T = O(g^{-2})$，$g$ 为最小能隙），系统停留在瞬时基态。

$p$ 层 QAOA 对应于将 $[0, 1]$ 切成 $p$ 段，每段内先施加 $H_C$ 再施加 $H_B$。$p$ 层的参数空间 $2p$ 维，足以逼近连续绝热路径。

定理（Farhi et al.）：$p \to \infty$ 时，QAOA 的最优参数 $(\vec{\gamma}^*, \vec{\beta}^*)$ 收敛到绝热路径的离散化。

Barren Plateaus 问题

问题：当 $n$ 很大时，梯度 $\partial F / \partial \theta_l$ 以高概率指数衰减：

$$\mathbb{E}\left[\frac{\partial F}{\partial \theta_l}\right] = 0, \quad \text{Var}\left[\frac{\partial F}{\partial \theta_l}\right] = O(2^{-n})$$

这导致优化景观平坦（“贫瘠高原”），随机初始化的梯度下降失效。

缓解策略：

• 使用结构化初始参数（如来自绝热路径的参数）
• 限制电路深度 $p$（$p = O(\text{poly}\log n)$ 时可避免）
• 使用局域代价函数（$H_C$ 为局部算符之和）

具体例子

Max-Cut：三角形图

考虑三角形图 $K_3$（3 个顶点，3 条边），$n = 3$。

$$H_C = \frac{3}{2}I - \frac{1}{2}(Z_1 Z_2 + Z_2 Z_3 + Z_3 Z_1)$$

全局最优：$C_{\max} = 2$（任意两个顶点同色，第三个异色）。

$p = 1$ QAOA：

$F(\gamma, \beta) = \frac{3}{2} - \frac{1}{2}[\cos(2\gamma)\cos(2\beta) + \cos(2\gamma)\sin^2(2\beta)\sin(2\gamma)]$（对 $K_3$ 的对称化分析）

数值优化得 $\gamma^* \approx 0.274$，$\beta^* \approx 0.546$，$F \approx 1.75$，近似比 $1.75/2 = 0.875$。

$p = 2$ QAOA：近似比提升至 $\approx 0.97$。

Max-Cut：环图 $C_6$

6 个顶点的环，$n = 6$。$C_{\max} = 6$（完美二分）。

• $p = 1$：$F^* \approx 4.6$，$r \approx 0.77$
• $p = 2$：$F^* \approx 5.3$，$r \approx 0.88$
• $p = 5$：$F^* \approx 5.9$，$r \approx 0.98$

QAOA 的变体

Grover-QAOA（GQAOA）

结合 Grover 的相位匹配思想，在 QAOA 电路中引入受控相位翻转，提升解的振幅放大速度。

Multi-Angle QAOA（ma-QAOA）

每层使用独立的参数集，参数数量 $O(p \cdot L)$（$L$ 为 $H_C$ 的项数），表达能力更强，但优化更困难。

QAOA with Warm Start

使用经典近似算法的解作为量子电路的初始态（而非 $|+\rangle^{\otimes n}$），将经典信息”注入”量子计算，提升收敛速度。

Recursive QAOA（RQAOA）

迭代地：运行 QAOA → 测量相关函数 $\langle Z_i Z_j \rangle$ → 固定相关性最强的变量 → 减少问题规模 → 重复。对 Max-Cut 在某些图族上超过 Goemans-Williamson。

复杂度分析

总时间：$O(T_{\text{opt}} \cdot p \cdot \Delta \cdot n_{\text{shots}} / \varepsilon^2)$

当前进展与挑战

理论进展

实验挑战

1. NISQ 噪声：门错误率 $\sim 10^{-3}$ 限制电路深度 $p \lesssim 100$
2. Barren plateaus：大 $n$ 时优化景观平坦
3. 读出噪声：测量错误降低解质量
4. 参数转移：最优参数随问题规模变化，不能简单外推

总结

QAOA 是 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.