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

最后更新时间：2026年06月07日

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 \lt j} J_{ij} z_i z_j$$

对应 $H_C = \sum_i h_i Z_i + \sum_{i \lt j} J_{ij} Z_i Z_j$。

第二步：构造 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$

代码示例（uniqc 实现）

下面用 unified-quantum（pip install unified-quantum）的 qaoa_ansatz + scipy.optimize.minimize 实现并优化 QAOA。我们对比两类小图：

  • K_3（三角形）：高度对称，$p = 1$ 就能达到全局最优。
  • C_5（5-环）：奇环存在”挫败”边，$p = 1$ 受限，$p \ge 2$ 才能达到 max-cut。
import numpy as np
from scipy.optimize import minimize
from uniqc import qaoa_ansatz

# 用 numpy 构造 Z_i Z_j 矩阵, 用于无噪期望值
I2 = np.eye(2, dtype=complex)
Z = np.array([[1, 0], [0, -1]], dtype=complex)

def zz_matrix(q1, q2, n):
    mats = [I2] * n; mats[n - 1 - q1] = Z; mats[n - 1 - q2] = Z
    out = mats[0]
    for m in mats[1:]: out = np.kron(out, m)
    return out

def run_qaoa(edges, n, max_cut, p_values=(1, 2, 3), n_starts=20, seed=42):
    cost_terms = [(f'Z{i}Z{j}', 1.0) for i, j in edges]   # 例: 'Z0Z1'
    H_C = sum(zz_matrix(i, j, n) for i, j in edges)
    psi0 = np.zeros(2 ** n, dtype=complex); psi0[0] = 1.0

    def energy(params, p):
        circuit = qaoa_ansatz(cost_terms, p=p,
                              gammas=params[:p], betas=params[p:])
        psi = circuit.get_matrix() @ psi0
        return float(np.real(psi.conj() @ H_C @ psi))

    rng = np.random.default_rng(seed)
    print(f"{'p':>2}|{'⟨H_C⟩':>10}{'平均割':>10}{'近似比':>10}")
    print('-' * 50)
    for p in p_values:
        best = None
        for _ in range(n_starts):
            x0 = rng.uniform(0, np.pi, size=2 * p)
            res = minimize(energy, x0, args=(p,), method='COBYLA',
                           options={'maxiter': 300, 'rhobeg': 0.1})
            if best is None or res.fun < best.fun:
                best = res
        cut = (len(edges) - best.fun) / 2.0
        print(f'{p:>2}|{best.fun:>10.4f}{cut:>10.4f}{cut/max_cut:>10.4f}')

print('=== K_3 (三角形, max-cut = 2) ===')
run_qaoa(edges=[(0, 1), (1, 2), (0, 2)], n=3, max_cut=2)

print('\n=== C_5 (5-环, max-cut = 4) ===')
run_qaoa(edges=[(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)], n=5, max_cut=4)

运行结果：

=== K_3 (三角形, max-cut = 2) ===
 p |      ⟨H_C⟩      平均割      近似比
--------------------------------------------------
 1 |    -1.0000     2.0000     1.0000
 2 |    -1.0000     2.0000     1.0000
 3 |    -1.0000     2.0000     1.0000

=== C_5 (5-环, max-cut = 4) ===
 p |      ⟨H_C⟩      平均割      近似比
--------------------------------------------------
 1 |    -2.5000     3.7500     0.9375
 2 |    -3.0000     4.0000     1.0000
 3 |    -3.0000     4.0000     1.0000

关键现象：

  • K_3：3 条边都参与同一个三角形，所有非平凡分割（6/8 个比特串）都达到 max-cut = 2。$p = 1$ 的 QAOA 在最优角度下把所有概率均分到这 6 个最优解上（$|000\rangle, |111\rangle$ 概率精确为 0），达到 $\langle H_C\rangle = -1$，近似比 = 1.0。该高度对称的小实例上 $p = 1$ 已达最优，并不与正文 $r_1 \ge 0.6924$（针对一般 $3$-正则无三角图）的最坏情况下界冲突。
  • C_5：5 个顶点的奇环，最大 2-着色不可避免有 1 条”挫败”边，max-cut = 4。$p = 1$ 仅能给出 $\langle H_C\rangle = -2.5$（$15/16$ 比例），$p = 2$ 即可达到 max-cut = 4。这正是 QAOA 在 NISQ 时代的核心承诺：用少量层数 $p$ 换近似比的提升。

注：qaoa_ansatz(cost_terms, p, gammas, betas) 直接展开成 Circuit，内部 cost 层用 CNOT-Rz-CNOT 实现每个 $Z_iZ_j$，mixer 层用 H-Rz-H 实现 $X$ 旋转（等价于 $R_x$）。

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。

复杂度分析

组件 资源
量子比特 $n$
电路深度（$p$ 层） $O(p \cdot \Delta)$，$\Delta$ 为最大度
参数优化迭代 $O(\text{poly}(p, n))$（经验）
测量次数（每次优化迭代） $O(1/\varepsilon^2)$（统计精度）

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

当前进展与挑战

理论进展

年份 结果
2014 Farhi et al. 提出 QAOA，证明 $p \to \infty$ 收敛到最优
2019 Hastings: 局部经典算法至少与低深度 QAOA 一样有效（负面结果）
2024 Blekos et al.：QAOA 的全面综述与进展

实验挑战

  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.

返回目录：量子计算算法教程系列

声明：Zhaoyun's Quantum Lab|版权所有，违者必究|如未注明，均为原创|本网站采用BY-NC-SA协议进行授权

转载：转载请注明原文链接 - QAOA 算法详解：量子近似优化算法

With code, we create everything