QAOA（量子近似优化算法）

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

问题背景：组合优化

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

${\mathbf{z}}^{\ast }=\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}⟩⟨\mathbf{z}|,$

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

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

$H_B={\sum }_{i=1}^n{X}_i.$

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

$p$ 层 QAOA 态定义为

$|\vec{\gamma },\vec{\beta }⟩={\prod }_{l=1}^p[e^{-i{\beta }_l{H}_B}\cdot e^{-i{\gamma }_l{H}_C}]\cdot |+{⟩}^{\otimes n},$

其中参数向量 $\vec{\gamma }=({\gamma }_1,\dots ,{\gamma }_p)$、$\vec{\beta }=({\beta }_1,\dots ,{\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\ne 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$）。对每条边，切断指示符有两种等价写法：

$1[b_i\ne b_j]=b_i+b_j-2b_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_i{s}_j=+1$、取值为 $0$，$b_i\ne b_j$ 时 $s_i{s}_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_i{s}_j}{2}=\frac{1-s_i{s}_j}{2},$

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

$C(\mathbf{b})={\sum }_{(i,j)\in E}\frac{1-s_i{s}_j}{2}.$

现在把经典变量提升为算符。计算基 $|\mathbf{b}⟩=|b_1{b}_2\cdots b_n⟩$ 满足 $Z_i|\mathbf{b}⟩=(1-2b_i)|\mathbf{b}⟩=s_i|\mathbf{b}⟩$（由 $Z|0⟩=+|0⟩$、$Z|1⟩=-|1⟩$ 直接得到）。因此 $Z_i$ 正是自旋变量 $s_i$ 对应的算符，而 $Z_i{Z}_j$ 对基矢的本征值就是 $s_i{s}_j$。把逐边求和中的 $s_i{s}_j$ 替换为 $Z_i{Z}_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}⟩=C(\mathbf{b})|\mathbf{b}⟩$：每条边贡献一个 $-\frac{1}{2}{Z}_i{Z}_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}(I-Z_i-Z_j+Z_i{Z}_j).$

代入并按 $I$、$Z_i$、$Z_i{Z}_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},h_i=-\frac{Q_{ii}}{2}-\frac{1}{4}{\sum }_{j>i}{Q}_{ij}-\frac{1}{4}{\sum }_{j<i}{Q}_{ji},J_{ij}=\frac{Q_{ij}}{4}.$

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

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

$c_0=\frac{1}{2}{\sum }_i\mathrm{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}_i{Z}_j$，与逐边推导完全一致。这也解释了为什么 MaxCut 的 QAOA 哈密顿量没有单比特（场）项：无向图的切断数在同构翻转下不变。

第二步：构造 QAOA 电路

初始态取 $|s⟩=|+{⟩}^{\otimes n}=H^{\otimes n}|0{⟩}^{\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}_i{Z}_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(\varphi )=e^{-i\varphi Z/2}$，我们断言

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

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

$\mathrm{CNOT}{Z}_j\mathrm{CNOT}|b_i{b}_j⟩=\mathrm{CNOT}{Z}_j|b_i,b_j\oplus b_i⟩=(-1{)}^{b_j\oplus b_i}\mathrm{CNOT}|b_i,b_j\oplus b_i⟩=(-1{)}^{b_i\oplus b_j}|b_i{b}_j⟩=Z_i{Z}_j|b_i{b}_j⟩,$

其中最后一步用了 $(-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\varphi Z_j/2}\mathrm{CNOT}=e^{-i\varphi \mathrm{CNOT}{Z}_j\mathrm{CNOT}/2}=e^{-i\varphi Z_i{Z}_j/2}$。证毕。

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

第二个恒等式关于混合层：$e^{+i\beta X}=R_x(-2\beta )$（由 $R_x(\varphi ):=e^{-i\varphi X/2}$，取 $\varphi =-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}F(\vec{\gamma },\vec{\beta })=⟨\vec{\gamma },\vec{\beta }|H_C|\vec{\gamma },\vec{\beta }⟩.$

可选的优化方法包括：

• 梯度方法：$\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}_i{Z}_j/2}$（生成元 $Z_i{Z}_j$ 谱为 $\{\pm 1\}$）再对每个门分别应用 $\frac{\partial E}{\partial \theta }=\frac{1}{2}[E(\theta +\frac{\pi }{2})-E(\theta -\frac{\pi }{2})]$，最后按链式法则相加（共享参数的处理见：参数平移法则）；
• 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}$ 与任何对角算符对易、且保持 $|+{⟩}^{\otimes n}$ 不变，故 $F$ 不变。$\gamma \to \gamma +\pi$ 的对称则要求所有顶点度数奇偶性一致：此时 $e^{-i\pi H_C}={\prod }_{(i,j)\in E}{Z}_i{Z}_j={\prod }_i{Z}_i^{\mathrm{deg}(i)}$ 是恒等或全局翻转，同样不改变 $F$（3 正则图、环图都满足）。

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

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

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

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

$\hat{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}),$

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

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

$\widehat{⟨Z_0{Z}_1⟩}=\frac{2\cdot (+1)+2\cdot (-1)\cdot 4+2\cdot (+1)}{12}=\frac{2-8+2}{12}=-\frac{1}{3},$

三条边对称相同，故 $\hat{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$ 的约定，其基态为 $|+{⟩}^{\otimes n}$）

$H(s)=(1-s)H_B+s{H}_C,s:0\to 1,$

系统按薛定谔方程演化 $i\frac{d}{dt}|\psi (t)⟩=H(s(t))|\psi (t)⟩$。绝热定理指出：若演化总时间 $T$ 相对最小谱隙足够大（经验形式为 $T\gtrsim {\max }_s\Vert {\partial }_{s}H\Vert /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 tH(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(\Vert [A,B]\Vert )$（其误差界即 VQE 一篇引用的 $\Vert e^{A+B}-e^A{e}^B\Vert \le \frac{1}{2}\Vert [A,B]\Vert e^{\Vert A\Vert +\Vert B\Vert }$），这里 $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),{\beta }_l:=(1-s_l)\Delta t,{\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\left(\text{离散化绝热演化的末态}\right)\underset{p\to \infty }{\to }F\left(\text{连续绝热演化末态}\right).$

再令 $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_0{Z}_1+Z_1{Z}_2+Z_2{Z}_0),$

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

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

第一步：不变子空间。 记

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

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

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

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

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

$\Sigma X{|}_{\mathrm{span}\{a,b\}}=\left(\begin{array}{cc}0& \sqrt{3}\\ \sqrt{3}& 2\end{array}\right),$

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

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

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

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

$F(\gamma ,\beta )=\frac{3}{8}(3+\cos 2\gamma )+\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$ 必须恒为 $\frac{3}{2}$（随机比特串平均切断 $3\times \frac{1}{2}=1.5$ 条边）——代入 $\cos$ 项相消确为 $\frac{3}{2}$；$\beta =0$ 时混合层为恒等，$H_C$ 与 $e^{-i\gamma H_C}$ 对易，$F=⟨s|H_C|s⟩=\frac{3}{2}$——同样成立。

第五步：最大化。 在子流形 $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}=\frac{3}{4}-\frac{9}{4}c=0$ 得 $c=\frac{1}{3}$，此时

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

MaxCut：环图 $C_6$

环图 $C_6$ 有 $6$ 个顶点、$6$ 条边。它是二部图，把顶点按奇偶分成两组即可切断所有边，故 $C_{\max }=6$（恰有两个最优串：$|010101⟩$ 型与 $|101010⟩$ 型）。对 $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=\frac{3}{4}{C}_{\max }$ 与 $p=2$ 的 $5=\frac{5}{6}{C}_{\max }$ 都是精确的有理数，这来自环图的高度对称性；一般图上的最优值没有这么整洁，需要数值优化。

QAOA 的变体

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

把标准混合层 $e^{-i\beta H_B}$ 替换为 Grover 扩散型算符 $D=2|s⟩⟨s|-I$（$|s⟩=|+{⟩}^{\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 解的四舍五入向量转化为各量子比特的偏置初态），替代均匀叠加 $|+{⟩}^{\otimes n}$，把经典信息”注入”量子计算。初始态更接近优质解所在的子空间，通常能加快收敛并提升浅层表现。

Recursive QAOA（RQAOA）

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

复杂度分析

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

总代价：若优化器迭代 $T_{\text{opt}}$ 次、每次能量估计用 $m$ 次测量，则总电路执行次数为 $O(T_{\text{opt}}\cdot m)$，每次执行的深度为 $O(p\cdot \Delta )$。可以看到测量开销（$m\sim 1/{\epsilon }^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. 读出噪声：测量错误降低关联函数 $⟨Z_i{Z}_j⟩$ 的估计精度，需要读出误差缓解；
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.

---

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch08-qml/qaoa-tutorial
• 内容遵循 CC BY-NC-SA 4.0 许可协议