量子计算（八）——QAOA量子近似优化算法

量子近似优化算法（Quantum Approximate Optimization Algorithm，QAOA）是一种混合量子–经典架构的变分算法，即用经典优化器迭代训练一个含参量子线路，主要用于求解组合优化问题。所谓组合优化问题，典型的如旅行商问题、背包问题等，是在有限且离散的解空间中寻找最优解的优化问题，这一解空间会随着问题规模指数增长，因此一般是NP-hard的，可以给出数学模型为：

\begin{aligned} min & 𝒞︀ (𝑥) \\ s.t. & 𝒰︀ (𝑥) \geq 0 \\ 𝑥 \in 𝔻 \end{aligned}

其中 $𝒞︀ (𝑥)$ 是代价函数， $𝒰︀ (𝑥)$ 是约束条件， $𝔻$ 表示离散空间。在量子算法中，还会进一步要求 $𝑥$ 是二值的。

量子绝热算法（Quantum Adiabatic Algorithm，QAA）指出，通过设计哈密顿量的演化过程，量子系统可以从易制备的初始基态绝热演化至问题哈密顿量的基态，从而获得问题的一个近似解。而QAOA借鉴于这一物理图像，将连续的绝热演化过程，经由Trotter分解处理，离散化为多层的参数化量子门序列，从而在有限的电路深度下近似求解组合优化问题。

QAOA一般要求问题的数学模型要进一步约化到二次无约束二值优化（Quadratic Unconstrained Binary Optimization，QUBO）问题，即要求代价函数 $𝒞︀ (𝑥)$ 是最高次项不超过2的多项式，变量 $𝑥$ 取值为0或1，并且没有任何约束条件。实际上，QAOA亦可直接应用于多项式无约束二值优化（Polynomial Unconstrained Binary Optimization，PUBO）问题。相较于仅包含二次项的QUBO问题，PUBO问题推广了交互项的阶数，能够编码包含高阶关联的复杂目标函数。本节将从QUBO和PUBO问题的数学模型入手，详细说明QAOA算法的构造步骤与运行原理。

一、伊辛模型，QUBO问题与PUBO问题

伊辛模型 [1] 是统计物理中最具代表性的模型之一，用于研究自旋系统中的相变行为。伊辛模型定义在一个离散格点系综上，系统的总能量由伊辛哈密顿量给出：

ℋ︀ = - 𝐽 \sum_{⟨ 𝑖, 𝑗 ⟩} 𝑠_{𝑖} 𝑠_{𝑗} - ℎ \sum_{𝑖} 𝑠_{𝑖}

其中， $⟨ 𝑖, 𝑗 ⟩$ 表示所有相邻格点对的集合； $𝐽$ 为耦合常数，决定自旋之间的相互作用强度和类型；每个格点 $𝑖$ 上的自旋变量 $𝑠_{𝑖}$ 只能取 $+ 1$ （向上）或 $- 1$ （向下）两种状态。自旋变量 $𝑠$ 的取值与计算机中常用的0-1布尔变量 $𝑏$ 不相同，但可以使用 $𝑠 = 2 𝑏 - 1$ 相互转换。注意到式 (2) 中的次数为2，如果该次数能取更大的值，那么称模型为高阶伊辛模型。在组合优化和量子计算中，许多 NP-hard 问题都可以转化为寻找等效伊辛模型的基态。 QAOA算法由Edward Farhi在2014年提出时 [2]，就已经用在了有界度数图的最大割问题中。该问题是典型的QUBO问题，即其代价函数具有数学形式：

𝒞︀ (𝒙) ≔ 𝒙^{⊤} 𝑸 𝒙, 𝒙 \in {0, 1}^{𝑛},

其中问题中有 $𝑛$ 个变量， $𝒙$ 是一个具有 $𝑛$ 个元素的0-1向量， $𝑸$ 是 $𝑛 \times 𝑛$ 的实数矩阵。这显然是一个二次型，但由于对任意二进制变量 $𝑏$ 都有 $𝑏^{2} = 𝑏$ ，因此 $𝑸$ 的对角线元素在QUBO问题中可以特指一次项系数。有时候式 (3) 会被写成求和的形式：

𝒞︀ (𝑥) = \sum_{\begin{matrix} 𝑖, 𝑗 = 1 \\ 𝑖 \leq 𝑗 \end{matrix}}^{𝑛} 𝑄'_{𝑖 𝑗} 𝑥_{𝑖} 𝑥_{𝑗} + \sum_{𝑖 = 1}^{𝑛} 𝑐_{𝑖} 𝑥_{𝑖},

从而更加方便地转换为伊辛模型。需要注意：

注 1.

式 (4) 中的 $𝑄'_{𝑖 𝑗}$ 不一定等于式 (3) 中二次型矩阵 $𝑸$ 的第 $𝑖$ 行第 $𝑗$ 列元素 $𝑄_{𝑖 𝑗}$ ，而应视 $𝑸$ 的形式决定¹¹ 例如， $[\begin{matrix} 2 & 2 & 2 \\ 0 & 4 & 4 \\ 0 & 0 & 6 \end{matrix}]$ 和 $[\begin{matrix} 2 & 1 & 1 \\ 1 & 4 & 2 \\ 1 & 2 & 6 \end{matrix}]$ 都表示同一个二次型 $2 𝑥_{1}^{2} + 4 𝑥_{1} 𝑥_{2} + 6 𝑥_{2}^{2}$ ，但前者的 $𝑄'_{12} = 8$ ，后者的 $𝑄'_{12} = 4$ 。。例如，若 $𝑸$ 是对称矩阵，那么 $𝑄'_{𝑖 𝑗} = 2 𝑄_{𝑖 𝑗}$ 。
$𝑄'_{𝑖 𝑗}$ 允许 $𝑖 = 𝑗$ ，这似乎会造成与一次项求和部分的冗余。但允许 $𝑖 = 𝑗$ 会使之后转换伊辛模型的计算更加简单。事实上，可以令 $𝑄'_{𝑖 𝑖} = 0, 𝑐_{𝑖} = 𝑄_{𝑖 𝑖}$ 以消除冗余，此时求和号下 $𝑖 \leq 𝑗$ 改为 $𝑖 < 𝑗$ 不影响结果。

为了将代价函数转换为伊辛模型，只需将布尔变量 $𝑥_{𝑖}$ 转换为自旋变量 $𝑠_{𝑖}$ 。通过代入变换关系 $𝑥_{𝑖} = \frac{𝑠_{𝑖} + 1}{2}$ ，即可得到伊辛哈密顿量：

由于式 (5) 的最后一个求和项为常数，不影响优化问题的解，因此常常略去。令 $𝐽_{𝑖 𝑗} = - \frac{𝑄'_{𝑖 𝑗}}{4}, ℎ_{𝑖} = - \frac{1}{2} (𝑐_{𝑖} + \sum_{𝑗 = 1}^{𝑛} 𝑄'_{𝑖 𝑗})$ ，就成功转化为伊辛哈密顿量：

ℋ︀ (𝑠) = - \sum_{𝑖, 𝑗 = 1}^{𝑛} 𝐽_{𝑖 𝑗} 𝑠_{𝑖} 𝑠_{𝑗} - \sum_{𝑖 = 1}^{𝑛} ℎ_{𝑖} 𝑠_{𝑖} .

当实际问题具有约束的时候，一般会通过添加惩罚项的方式将问题转换为QUBO问题。例如式 (1) 所示的原始问题，将会被转化为:

min 𝒞︀ (𝑥) + 𝜆 𝒫︀ (𝑥),

其中 $𝒫︀ (𝑥)$ 是约束条件 $𝒰︀ (𝑥)$ 对应的惩罚函数； $𝜆 > 0$ 是任取的惩罚系数，一般不应取太小。表 1 给出了一些典型约束条件应转换到的惩罚函数。

表 1 约束条件及其对应惩罚函数

序号	约束条件	惩罚函数
1	$𝑥_{1} + 𝑥_{2} \leq 1$	$𝑥_{1} 𝑥_{2}$
2	$𝑥_{1} + 𝑥_{2} \geq 1$	$1 - 𝑥_{1} - 𝑥_{2} + 𝑥_{1} 𝑥_{2}$
3	$𝑥_{1} + 𝑥_{2} = 1$	$1 - 𝑥_{1} - 𝑥_{2} + 2 𝑥_{1} 𝑥_{2}$
4	$𝑥_{1} = 𝑥_{2}$	$𝑥_{1} + 𝑥_{2} - 2 𝑥_{1} 𝑥_{2}$
5	$𝑥_{1} \leq 𝑥_{2}$	$𝑥_{1} - 𝑥_{1} 𝑥_{2}$
6	$𝑥_{1} + 𝑥_{2} + 𝑥_{3} \leq 1$	$𝑥_{1} 𝑥_{2} + 𝑥_{1} 𝑥_{3} + 𝑥_{2} 𝑥_{3}$

以QUBO问题为基础，若不限定代价函数中最高次项的次数，则问题扩展为PUBO问题。此时代价函数可以写为：

\begin{aligned} 𝒞︀ (𝑥) & = \sum_{𝑖_{1}} 𝑇_{𝑖_{1}} 𝑥_{𝑖_{1}} + \sum_{𝑖_{1} < 𝑖_{2}} 𝑇_{𝑖_{1} 𝑖_{2}} 𝑥_{𝑖_{1}} 𝑥_{𝑖_{2}} + \sum_{𝑖_{1} < 𝑖_{2} < 𝑖_{3}} 𝑇_{𝑖_{1} 𝑖_{2} 𝑖_{3}} 𝑥_{𝑖_{1}} 𝑥_{𝑖_{2}} 𝑥_{𝑖_{3}} + \dots \\ = \sum_{𝛿 = (𝛿_{1}, \dots, 𝛿_{𝑛}) \in {0, 1}^{𝑛}} 𝑇_{𝛿} \prod_{𝑖 = 1}^{𝑛} 𝑥_{𝑖}^{𝛿_{𝑖}}, \end{aligned}

其中 $𝑛$ 是变量的数量。通过变量代换、添加约束并转换为惩罚项的方式，PUBO问题总能被归约为QUBO问题。相关算法在文献[3]中有详尽的总结。利用变换式 $𝑠 = 2 𝑥 - 1$ 能将PUBO问题转换为高阶伊辛模型。

二、将问题编码为厄米矩阵

在“一、伊辛模型，QUBO问题与PUBO问题”节中已提到，使用自旋变量 $𝑠$ 与布尔变量 $𝑥$ 的变量代换 $𝑠 = 2 𝑥 - 1$ 即可将QUBO问题或PUBO问题转换为伊辛模型（包括高阶伊辛模型）。要应用QAOA算法，下一步就是将伊辛模型编码为厄米矩阵。现假设已经得到的伊辛哈密顿量为：

ℋ︀ (𝑠) = \sum_{𝛿 = (𝛿_{1}, \dots, 𝛿_{𝑛}) \in {0, 1}^{𝑛}} ℎ_{𝛿} \prod_{𝑖 = 1}^{𝑛} 𝑠_{𝑖}^{𝛿_{𝑖}},

那么只需做一点改动，即可得到对应的厄米矩阵形式哈密顿量，称为问题哈密顿量：

{𝓗︀}_{𝒞︀} = \sum_{𝛿 = (𝛿_{1}, \dots, 𝛿_{𝑛}) \in {0, 1}^{𝑛}} ℎ_{𝛿} ⨂_{𝑖 = 1}^{𝑛} 𝒁_{𝑖}^{𝛿_{𝑖}},

其中 $𝒁$ 即泡利Z矩阵，且 $𝒁^{0} = 𝒁^{2} = 𝑰$ 、 $𝒁^{1} = 𝒁$ ， $𝒁_{𝑖}$ 等价于将在第 $𝑖$ 量子比特上作用Z门。之所以这样替换，是因为可以自然地将物理可观测量——自旋沿 $𝑧$ 轴的分量，即泡利 Z 矩阵与自旋变量 $𝑠$ 对应起来。针对问题哈密顿量 ${𝓗︀}_{𝒞︀}$ ，有以下定理：

定理 1.（问题哈密顿量的特征向量和特征值[4]）

问题哈密顿量

{𝓗︀}_{𝒞︀}

的特征向量是从

| 0 ⟩

到

| 2^{𝑛} - 1 ⟩

的计算基态，且每个特征向量

| 𝑥 ⟩

对应的特征值是代价函数在相应解

𝑥

下的函数值

𝒞︀ (𝑥)

（在不忽略常数项的情况下）。

证明. 由于：

𝑰 = [\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}], 𝒁 = [\begin{matrix} 1 & 0 \\ 0 & - 1 \end{matrix}]

都是对角矩阵， $⨂_{𝑖 = 1}^{𝑛} 𝒁_{𝑖}^{𝛿_{𝑖}}$ 自然也是对角矩阵，相应地求累加后 ${𝓗︀}_{𝒞︀}$ 还是对角的，故 ${𝓗︀}_{𝒞︀}$ 的对角元素就是特征值。同时，由于 $𝑰, 𝒁$ 在计算基下可选 ${| 0 ⟩, | 1 ⟩}$ 作为共同特征向量，故任意矩阵 $𝑼 \in {𝑰, 𝒁}^{\otimes 𝑛}$ 都可选 ${| 0 ⟩, | 1 ⟩}^{\otimes 𝑛}$ 即所有计算基态作为特征向量，进一步地 ${𝓗︀}_{𝒞︀}$ 作为 ${𝑰, 𝒁}^{\otimes 𝑛}$ 中矩阵的实系数线性组合也能以所有计算基态作为特征向量。

另一方面，将特征向量 $| 𝑥 ⟩$ 写为二进制形式 $| 𝑥_{1} \dots 𝑥_{𝑛} ⟩$ 并令 $𝑠_{𝑖} = 2 𝑥_{𝑖} - 1$ 。一个显然的结果是对于任意 $𝛿 \in {0, 1}^{𝑛}$ 有：

(⨂_{𝑖 = 1}^{𝑛} 𝒁_{𝑖}^{𝛿_{𝑖}}) | 𝑥 ⟩ = (\prod_{𝑖 = 1}^{𝑛} 𝑠_{𝑖}^{𝛿_{𝑖}}) | 𝑥 ⟩,

因为每有一个 $𝑥_{𝑖} = 1$ 且 $𝛿_{𝑖} = 1$ 就会使 $| 𝑥 ⟩$ 乘一次 $- 1$ 。那么：

{𝓗︀}_{𝒞︀} | 𝑥 ⟩ = (\sum_{𝛿} ℎ_{𝛿} ⨂_{𝑖 = 1}^{𝑛} 𝒁_{𝑖}^{𝛿_{𝑖}}) | 𝑥 ⟩ = (\sum_{𝛿} ℎ_{𝛿} \prod_{𝑖 = 1}^{𝑛} 𝑠_{𝑖}^{𝛿_{𝑖}}) | 𝑥 ⟩ = ℋ︀ (𝑠) | 𝑥 ⟩ .

在不忽略常数项的情况下， $ℋ︀ (𝑠) = 𝒞︀ (𝑥)$ ，所以 ${𝓗︀}_{𝒞︀} | 𝑥 ⟩ = 𝒞︀ (𝑥) | 𝑥 ⟩$ ，故 $| 𝑥 ⟩$ 对应的特征值就是相应的代价 $𝒞︀ (𝑥)$ 。

□

显然一种求解此组合优化问题的方法就是从 ${𝓗︀}_{𝒞︀}$ 中找到最小的特征值，再以此求出对应特征向量。但必须指出， ${𝓗︀}_{𝒞︀}$ 是 $2^{𝑛}$ 阶的，因此该方法并没有摆脱指数增长带来的困难。然而另一方面，对于一个哈密顿量，其最小特征值对应的特征向量正是量子系统的基态。因此，量子绝热算法基于量子绝热定理，通过设计一条演化路径，将一个易于制备基态的哈密顿量连续地演化为问题哈密顿量。若演化足够缓慢且满足绝热条件，最终系统将处于问题哈密顿量的基态，此时对该态进行测量，即可得到优化问题的解。而QAOA借鉴量子绝热算法，以参数化量子电路来分段近似模拟绝热演化。

定理 2.（量子绝热定理）

对于一个缓慢变化的、无简并的哈密顿量，如果系统初始处于其基态或某个瞬时能级的本征态，则系统在随时间演化的过程中将始终保持在相应的瞬时能级态上，而不会跃迁到其他能级。

三、分段近似模拟绝热演化

接下来首先给出QAOA的整体结构与电路图，之后再分模块介绍。QAOA的算法过程可以用下式完整表示：

| 𝜸, 𝜷 ⟩ = \underset{第 𝑝 层}{\underset{⏟}{𝑈 ({𝓗︀}_{𝐵}, 𝛽_{𝑝}) 𝑈 ({𝓗︀}_{𝒞︀}, 𝛾_{𝑝})}} \dots \underset{第2层}{\underset{⏟}{𝑈 ({𝓗︀}_{𝐵}, 𝛽_{2}) 𝑈 ({𝓗︀}_{𝒞︀}, 𝛾_{2})}} \underset{第1层}{\underset{⏟}{𝑈 ({𝓗︀}_{𝐵}, 𝛽_{1}) 𝑈 ({𝓗︀}_{𝒞︀}, 𝛾_{1})}} | 𝑠 ⟩,

其对应量子电路如图 1 所示。其中， ${𝓗︀}_{𝒞︀}$ 即前文所述的问题哈密顿量， ${𝓗︀}_{𝐵}$ 是混合哈密顿量，定义为：

{𝓗︀}_{𝐵} = \sum_{𝑖 = 1}^{𝑛} 𝑿_{𝑖},

$𝑿_{𝑖}$ 等价于将在第 $𝑖$ 量子比特上作用X门。 $𝜸 = (𝛾_{1}, \dots, 𝛾_{𝑝}), 𝜷 = (𝛽_{1}, \dots, 𝛽_{𝑝})$ 分别是包含 $𝑝$ 个角度参数的参数向量，称参数 $𝑝$ 为深度。由图 1 可知 $| 𝑠 ⟩$ 正是初态 ${| 0 ⟩}^{\otimes 𝑛}$ 被作用 $𝐻^{\otimes 𝑛}$ 之后得到的均匀叠加态 ${| + ⟩}^{\otimes 𝑛}$ 。而：

𝑈 (𝓗︀, 𝜃) = e^{- i 𝜃 𝓗︀}

是一个酉算子，接受一个矩阵和角度作为输入，输出一个酉矩阵。简便起见，将任意一层记为酉算子 $𝐿_{𝑖} (𝛾_{𝑖}, 𝛽_{𝑖}) = 𝑈 ({𝓗︀}_{𝐵}, 𝛽_{𝑖}) 𝑈 ({𝓗︀}_{𝒞︀}, 𝛾_{𝑖})$ ，所有层记为酉算子 $𝐿 (𝜸, 𝜷) = \prod_{𝑖 = 𝑝}^{1} 𝐿_{𝑖} (𝛾_{𝑖}, 𝛽_{𝑖})$ 。

若在式 (16) 中代入 ${𝓗︀}_{𝐵}$ 与 $𝛽$ ，那么可做如下计算：

\begin{aligned} 𝑈 ({𝓗︀}_{𝐵}, 𝛽) & = e^{- i 𝛽 \sum_{𝑖 = 1}^{𝑛} 𝑿_{𝑖}} \\ = \prod_{𝑖 = 1}^{𝑛} e^{- i 𝛽 𝑿_{𝑖}} \\ = ⨂_{𝑖 = 1}^{𝑛} e^{- i 𝛽 𝑿} \\ = ⨂_{𝑖 = 1}^{𝑛} (cos (𝛽) 𝑰 - i sin (𝛽) 𝑿) \\ = ⨂_{𝑖 = 1}^{𝑛} 𝑅 𝑋_{𝑖} (2 𝛽), \end{aligned}

这说明混合酉算子 $𝑈 ({𝓗︀}_{𝐵}, 𝛽)$ 的作用就是在每一个量子比特上都作用一个 $𝑅 𝑋 (2 𝛽)$ 门，如图 2 所示。 $𝑅 𝑋 (𝜃)$ 门是：

𝑅 𝑋 (𝜃) = [\begin{matrix} cos \frac{𝜃}{2} & - i sin \frac{𝜃}{2} \\ - i sin \frac{𝜃}{2} & cos \frac{𝜃}{2} \end{matrix}]

因此，在量子电路图 1 中，唯一会随着问题而变的结构是问题酉算子 $𝑈 ({𝓗︀}_{𝒞︀}, 𝛾_{*})$ ，故只要研究清楚问题哈密顿量 ${𝓗︀}_{𝒞︀}$ 会如何构建量子电路，QAOA的电路构建就手到擒来了。

观察式 (10)，注意到 ${𝑰, 𝒁}^{\otimes 𝑛}$ 中的矩阵是两两对易的，因此在式 (16) 中代入问题哈密顿量 ${𝓗︀}_{𝒞︀}$ 与其对应角度参数 $𝛾$ 即得：

\begin{aligned} 𝑈 ({𝓗︀}_{𝒞︀}, 𝛾) & = e^{- i 𝛾 \sum_{𝛿} ℎ_{𝛿} ⨂_{𝑖 = 1}^{𝑛} 𝒁_{𝑖}^{𝛿_{𝑖}}} \\ = \prod_{𝛿} e^{- i (ℎ_{𝛿} 𝛾) ⨂_{𝑖 = 1}^{𝑛} 𝒁_{𝑖}^{𝛿_{𝑖}}} . \end{aligned}

显然可以认为系数是角度参数的一部分，之后再回过头来处理。上式主要透露出的信息是：只需要考虑 $e^{- i 𝛾 ⨂_{𝑖 = 1}^{𝑛} 𝒁_{𝑖}^{𝛿_{𝑖}}}$ 最终能转换成什么电路，就解决了QAOA整体电路构建的问题。现给出以下定理：

证明. 首先当 $𝓗︀ = 𝒁$ 时做如下计算：

\begin{aligned} 𝑈 (𝓗︀, 𝛾) & = e^{- i 𝛾 𝒁} \\ = cos (𝛽) 𝑰 - i sin (𝛽) 𝒁 \\ = diag e^{- i 𝛾}, e^{i 𝛾} \\ = 𝑅 𝑍 (2 𝛾) \end{aligned}

在考虑将要作用到的量子比特后，易证定理的第一部分。而当 $𝓗︀ = 𝒁 \otimes 𝑍$ 时，计算如下：

\begin{aligned} 𝑈 (𝓗︀, 𝛾) & = e^{- i 𝛾 𝒁 \otimes 𝒁} \\ = diag {- e^{i 𝛾}, e^{i 𝛾}, e^{i 𝛾}, e^{- i 𝛾}} \\ = CNOT \cdot 𝑅 𝑍 (2 𝛾) \cdot CNOT \end{aligned}

在考虑将要作用到的量子比特后定理第二部分得证。

□

必须指出，图 3中的 $𝑞_{𝑖_{1}}$ 与 $𝑞_{𝑖_{2}}$ 并不一定是相邻的， $𝑖_{1}, 𝑖_{2}$ 的取值只取决于式(10) 中的 $𝛿$ 。由此定理得到以下推论：

证明. 证明留给读者作为习题。提示：使用数学归纳法。

□

由定理 3，任意QUBO问题都能轻易地转化为QAOA量子电路了；进一步地，由推论 1，任意PUBO问题也能转化为量子电路。但千万别忘了：QAOA的终态 $| 𝜸, 𝜷 ⟩$ 是由 $𝜸, 𝜷$ 中共 $2 𝑝$ 个角度参数决定的，这些参数直接影响了算法对量子绝热过程的近似模拟的好坏。因此QAOA的下一步，是寻找到一组足够好的参数、以尽可能地模拟真实的量子绝热过程，或者说输出足够好的结果。

四、经典参数的训练

与经典计算中的机器学习、神经网络类似，这些角度参数也通常通过梯度下降法训练。衡量结果好坏的标准是——终态 $| 𝜸, 𝜷 ⟩$ 所代表的自旋构型 $𝑠$ 输入到伊辛哈密顿量后得到的期望能量值，即如式(9) 所示的 $ℋ︀ (𝑠)$ ，越低越好。显然该值也可以使用问题哈密顿量计算出：

⟨ {𝓗︀}_{𝒞︀} ⟩ (𝜸, 𝜷) = ⟨ 𝜸, 𝜷 | {𝓗︀}_{𝒞︀} | 𝜸, 𝜷 ⟩

这一关于参数 $𝜸, 𝜷$ 的函数称为能量景观（Energy Landscape）。假定角度参数 $𝜽 = (𝜸, 𝜷)$ 表示两个角度参数向量的合并， $𝜂$ 是学习率，那么参数更新公式为：

𝜽^{(𝑡 + 1)} = 𝜽^{(𝑡)} - 𝜂 \cdot \frac{𝜕 ⟨ {𝓗︀}_{𝒞︀} ⟩ (𝜽^{(𝑡)})}{𝜕 𝜽^{(𝑡)}} .

这一更新公式虽然与常见的并无二致，但在应用之前还需要讨论一些问题。第一个问题：对于变分量子线路，它的梯度绝非似经典机器学习那般，可以借助计算图、应用链式法则、实现反向传播从而轻易算出，因为这要求记录每个输出节点的数据，而在量子线路中这却是引入了测量、破坏了中间量子态。一种理论上常用的的梯度计算方式是参数移位法（Parameter-Shift Rule），该法指出 [5], [6]：

\frac{𝜕 ⟨ {𝓗︀}_{𝒞︀} ⟩ (𝜽)}{𝜕 𝜃_{𝑘}} = \frac{1}{2} [⟨ {𝓗︀}_{𝒞︀} ⟩ (𝜃_{𝑘} + \frac{𝜋}{2}) - ⟨ {𝓗︀}_{𝒞︀} ⟩ (𝜃_{𝑘} - \frac{𝜋}{2})], 𝑘 = 1, 2, \dots, 2 𝑝 .

这里 $⟨ {𝓗︀}_{𝒞︀} ⟩ (𝜃_{𝑘} - \frac{𝜋}{2})$ 是 $⟨ {𝓗︀}_{𝒞︀} ⟩ (𝜃_{1}, \dots, 𝜃_{𝑘} - \frac{𝜋}{2}, \dots, 𝜃_{2 𝑝})$ 的简写，表示在参数向量 $𝜽$ 只有第 $𝑘$ 参数 $𝜃_{𝑘}$ 被减去 $\frac{𝜋}{2}$ 。但在实践上，使用该法计算梯度的QAOA算法每一次完整的参数更新迭代需要运行线路并测量 $4 𝑝$ 次（因为 $2 𝑝$ 个参数每一者均需采样两次），无疑降低了训练效率；同时，即便式(26) 计算出的梯度理论上是精确的，真实量子硬件的噪声也使之变得不精确。因此同时扰动随机逼近算法（Simultaneous Perturbation Stochastic Approximation，SPSA）等更采样次数更少且不追求精确的算法反而更常用于真实硬件 [7]。

第二个问题：参数是否应当被截断在某一范围内？回答是肯定的，因为能量景观使用“角度”参数，它自然会隐含一个周期。在训练时将参数限制在一个周期内有助于训练的收敛。在说明周期性之前，首先介绍一个有关缩放的定理。

定理 4.（伊辛哈密顿量的缩放）

设缩放参数

𝑘 > 0

。若自旋构型

𝑠^{*}

是被缩放后的伊辛哈密顿量

\frac{ℋ︀ (𝑠)}{𝑘}

的最优解，那么

𝑠^{*}

同样是原始伊辛哈密顿量

ℋ︀ (𝑠)

的最优解。

证明.

\frac{ℋ︀ (𝑠)}{𝑘} \leq \frac{ℋ︀ (𝑠^{*})}{𝑘} ⟺ ℋ︀ (𝑠) \leq ℋ︀ (𝑠^{*}) .

□

接下来的定理描述了：能量景观关于 $𝜷$ 参数具有普适的周期性。

定理 5.（QAOA算法的能量景观中

𝜷

参数的周期性）

在忽略产生的全局相位的情况下，QAOA算法的能量景观的参数 $𝜷$ 具有周期 $𝜋$ ，即：

⟨ {𝓗︀}_{𝒞︀} ⟩ (𝜸, 𝛽_{1}, \dots, 𝛽_{𝑖} + 𝜋, \dots, 𝛽_{𝑝}) = ⟨ {𝓗︀}_{𝒞︀} ⟩ (𝜸, 𝜷), 𝑖 = 1, 2, \dots, 𝑝

证明. 注意到由式(16) 代入混合哈密顿量推导出的图 2 中 RX 门的角度参数均为

2 𝛽

，因此

𝜋

是能量景观关于

𝜷

参数的最小正周期。

□

在训练时可以将 $𝜷$ 的取值范围限制在 $[- \frac{𝜋}{2}, \frac{𝜋}{2}]$ 。

最后这个定理描述了：在一般情况下，对能量景观的 $𝜸$ 参数，不具有普适的周期性。

定理 6.（QAOA算法的能量景观中

𝜸

参数的周期性）

在忽略产生的全局相位的情况下，形如式(9) 的伊辛哈密顿量中：

若存在某个系数 $ℎ_{𝛿}$ 是无理数，那么能量景观关于 $𝜸$ 参数不具有周期性，但具
有准周期性；
若所有系数均为有理数，那么 $𝛾$ 参数具有最小公共正周期 $𝑇 = \frac{𝜋}{𝑔}$ ，其中 $𝑔 = gcd (ℎ_{𝛿}) = gcd (ℎ_{0}, \dots, ℎ_{2^{𝑛} - 1})$ 是所有系数的最大公约数。

证明. 存在无理数系数的情况下：待证。

所有系数均为有理数的情况下：由定理 3和推论 1，考虑相关系数后即按照式(19)， RZ 门的角度参数是 $2 ℎ_{𝛿} 𝛾$ 。故对单个 $𝛾$ ，其周期是 $\frac{𝜋}{ℎ_{𝛿}}$ 。那么对于所有 $𝛾$ 、即 $𝜸$ 具有最小公共正周期 $lcm (\frac{𝜋}{ℎ_{𝛿}}) = \frac{𝜋}{gcd (ℎ_{𝛿})}$ 。

□

但应当注意到，在许多实际问题中，无理数系数是较难取到的。并且，即便确实有无理数系数，一方面也可以通过近似的手段化为有理数；另一方面使用计算机处理问题时也仅能存储为近似的浮点数，因此在实际应用时认为能量景观关于 $𝜸$ 参数具有普适周期性并非不可接受的。

第三个问题：该参数空间能否进一步缩小，即能否为能量景观函数找到更小的周期、或者寻到一些特殊的对称性？回答也是肯定的。首先，利用定理 4，总能找到合适的缩放参数 $𝑘$ ，使定理定理 6 中的最小正周期约束化为 $𝜋$ ，从而使 $𝜸$ 的取值范围限定在 $[- \frac{𝜋}{2}, \frac{𝜋}{2}]$ 中。接下来，定理定理 7 给出了一种普遍的对称性。

定理 7.（QAOA算法的能量景观的对称性 [8]）

QAOA算法的能量景观是关于原点对称的，即：

⟨ {𝓗︀}_{𝒞︀} ⟩ (- 𝜸, 𝜷) = ⟨ {𝓗︀}_{𝒞︀} ⟩ (𝜸, - 𝜷)

⟨ {𝓗︀}_{𝒞︀} ⟩ (- 𝜸, - 𝜷) = ⟨ {𝓗︀}_{𝒞︀} ⟩ (𝜸, 𝜷)

证明. 以证明式(30) 为例。首先易证，对任意实向量 $| 𝑣 ⟩$ 有 ${| 𝑣 ⟩}^{*} = | 𝑣 ⟩$ ，于是：

{⟨ 𝑣 | 𝑼 | 𝑣 ⟩}^{*} = {(| 𝑣 ⟩)}^{*} {(𝑼)}^{*} {(| 𝑣 ⟩)}^{*} = ⟨ 𝑣 | 𝑼^{*} | 𝑣 ⟩

其次易证对任意一层酉算子存在：

\begin{aligned} 𝐿_{𝑖}^{*} (- 𝛾_{𝑖}, - 𝛽_{𝑖}) & = {(𝑈 ({𝓗︀}_{𝐵}, - 𝛽_{𝑖}) 𝑈 ({𝓗︀}_{𝒞︀}, - 𝛾_{𝑖}))}^{*} \\ = {(e^{- i (- 𝛽_{𝑖}) {𝓗︀}_{𝐵}} e^{- i (- 𝛾_{𝑖}) {𝓗︀}_{𝒞︀}})}^{*} \\ = e^{- i 𝛽_{𝑖} {𝓗︀}_{𝐵}} e^{- i 𝛾_{𝑖} {𝓗︀}_{𝒞︀}} \\ = 𝐿_{𝑖} (𝛾_{𝑖}, 𝛽_{𝑖}), \end{aligned}

于是对于所有层酉算子存在：

𝐿^{*} (- 𝜸, - 𝜷) = \prod_{𝑖} 𝐿_{𝑖}^{*} (- 𝛾_{𝑖}, - 𝛽_{𝑖}) = \prod_{𝑖} 𝐿_{𝑖} (𝛾_{𝑖}, 𝛽_{𝑖}) = 𝐿 (𝜸, 𝜷) .

所以：

\begin{aligned} ⟨ {𝓗︀}_{𝒞︀} ⟩ (- 𝜸, - 𝜷) & = ⟨ - 𝜸, - 𝜷 | {𝓗︀}_{𝒞︀} | - 𝜸, - 𝜷 ⟩ \\ = ⟨ 𝑠 | 𝐿^{†} (- 𝜸, - 𝜷) {𝓗︀}_{𝒞︀} 𝐿 (- 𝜸, - 𝜷) | 𝑠 ⟩ \\ = {⟨ 𝑠 | 𝐿^{†} (- 𝜸, - 𝜷) {𝓗︀}_{𝒞︀} 𝐿 (- 𝜸, - 𝜷) | 𝑠 ⟩}^{*} \\ = ⟨ 𝑠 | {(𝐿^{†} (- 𝜸, - 𝜷))}^{*} {𝓗︀}_{𝒞︀}^{*} 𝐿^{*} (- 𝜸, - 𝜷) | 𝑠 ⟩ \\ = ⟨ 𝑠 | 𝐿^{†} (𝜸, 𝜷) {𝓗︀}_{𝒞︀} 𝐿 (𝜸, 𝜷) | 𝑠 ⟩ \\ = ⟨ 𝜸, 𝜷 | {𝓗︀}_{𝒞︀} | 𝜸, 𝜷 ⟩ \\ = ⟨ {𝓗︀}_{𝒞︀} ⟩ (𝜸, 𝜷) . \end{aligned}

其中式(34) 第二行到式(34) 第三行是因为能量期望值 $⟨ {𝓗︀}_{𝒞︀} ⟩ (- 𝜸, - 𝜷)$ 是实数的。式(29) 的证明类似。

□

由于式(29) (30) 所示的对称性， $𝜸, 𝜷$ 中任取一者的取值范围都能进一步缩减到非负区间，例如 ${[0, \frac{𝜋}{2}]}^{𝑝} {\times [- \frac{𝜋}{2}, \frac{𝜋}{2}]}^{𝑝}$ 。可惜的是，在一般情况下该参数空间不能再缩小了，但在特殊情形下能量景观函数可以有比 $𝜋$ 更小的周期——意味着更小的参数空间。

定理 8.（QUBO问题特殊情形下对应QAOA算法的能量景观的周期性 [8]）

若忽略全局相位，问题哈密顿量 ${𝓗︀}_{𝒞︀}$ 是从QUBO问题导出的、且不包含一次项，即仅包含二次项，那么对应的能量景观函数中，参数 $𝜷$ 的周期是 $\frac{𝜋}{2}$ ，即：

⟨ {𝓗︀}_{𝒞︀} ⟩ (𝜸, 𝛽_{1}, \dots, 𝛽_{𝑖} + \frac{𝜋}{2}, \dots, 𝛽_{𝑝}) = ⟨ {𝓗︀}_{𝒞︀} ⟩ (𝜸, 𝜷), 𝑖 = 1, 2, \dots, 𝑝

证明. 注意到对任一层酉算子有：

\begin{aligned} 𝐿_{𝑖} (𝛾_{𝑖}, 𝛽_{𝑖} + \frac{𝜋}{2}) & = e^{- i (𝛽_{𝑖} + \frac{𝜋}{2}) {𝓗︀}_{𝐵}} e^{- i 𝛾_{𝑖} {𝓗︀}_{𝒞︀}} \\ = e^{- i \frac{𝜋}{2} {𝓗︀}_{𝐵}} e^{- i 𝛽_{𝑖} {𝓗︀}_{𝐵}} e^{- i 𝛾_{𝑖} {𝓗︀}_{𝒞︀}} \\ = e^{- i \frac{𝜋}{2} {𝓗︀}_{𝐵}} 𝐿_{𝑖} (𝛾_{𝑖}, 𝛽_{𝑖}) . \end{aligned}

其中：

\begin{aligned} e^{- i \frac{𝜋}{2} {𝓗︀}_{𝐵}} & = e^{- i \frac{𝜋}{2} \sum_{𝑖 = 1}^{𝑛} 𝑿_{𝑖}} = \prod_{𝑖 = 1}^{𝑛} e^{- i \frac{𝜋}{2} 𝑿_{𝑖}} \\ = \prod_{𝑖 = 1}^{𝑛} (- i 𝑿_{𝑖}) = {(- i)}^{𝑛} \prod_{𝑖 = 1}^{𝑛} 𝑿_{𝑖} . \end{aligned}

其中 ${(- i)}^{𝑛}$ 可以作为全局相位被忽略掉。利用性质 $[𝐴, 𝐵] = 0 ⟹ [𝐴, 𝑓 (𝐵)] = 0$ ，显然 $[𝑿_{𝑖} \otimes 𝑿_{𝑗}, 𝒁_{𝑖} \otimes 𝒁_{𝑗}] = 0 ⟹ [𝑿_{𝑖} \otimes 𝑿_{𝑗}, exp {𝒁_{𝑖} \otimes 𝒁_{𝑗}}] = 0$ 。更进一步地，得到：

[\prod_{𝑖 = 1}^{𝑛} 𝑿_{𝑖}, \prod_{𝑖 < 𝑗 = 1}^{𝑛} exp {- i (ℎ_{𝛿} 𝛾) 𝒁_{𝑖} 𝒁_{𝑗}}] = 0 .

在问题哈密顿量中只含有二次项的情况下，上式说明 $\prod_{𝑖 = 1}^{𝑛} 𝑿_{𝑖}$ 与问题酉算子 $𝑈 ({𝓗︀}_{𝒞︀}, 𝛾_{𝑖})$ 是对易的。利用对易的性质显然也容易推知 $\prod_{𝑖 = 1}^{𝑛} 𝑿_{𝑖}$ 与混合酉算子 $𝑈 ({𝓗︀}_{𝐵}, 𝛽_{𝑖})$ 亦是对易的，从而 $\prod_{𝑖 = 1}^{𝑛} 𝑿_{𝑖}$ 与任一层酉算子 $𝐿_{𝑖} (𝛾_{𝑖}, 𝛽_{𝑖} + \frac{𝜋}{2})$ 是对易的。故 $\prod_{𝑖 = 1}^{𝑛} 𝑿_{𝑖}$ 可以被交换到下式的任意位置中：

\begin{aligned} | 𝜸, 𝛽_{1}, \dots, 𝛽_{𝑖} + \frac{𝜋}{2}, \dots, 𝛽_{𝑝} ⟩ \\ = & 𝐿_{𝑝} (𝛾_{𝑝}, 𝛽_{𝑝}) \dots 𝐿_{𝑖} (𝛾_{𝑖}, 𝛽_{𝑖} + \frac{𝜋}{2}) \dots 𝐿_{1} (𝛾_{1}, 𝛽_{1}) | 𝑠 ⟩ \\ = & 𝐿_{𝑝} (𝛾_{𝑝}, 𝛽_{𝑝}) \dots (\prod_{𝑖 = 1}^{𝑛} 𝑿_{𝑖}) 𝐿_{𝑖} (𝛾_{𝑖}, 𝛽_{𝑖}) \dots 𝐿_{1} (𝛾_{1}, 𝛽_{1}) | 𝑠 ⟩ \\ = & 𝐿_{𝑝} (𝛾_{𝑝}, 𝛽_{𝑝}) \dots 𝐿_{𝑖} (𝛾_{𝑖}, 𝛽_{𝑖}) \dots 𝐿_{1} (𝛾_{1}, 𝛽_{1}) (\prod_{𝑖 = 1}^{𝑛} 𝑿_{𝑖}) | 𝑠 ⟩ \\ = & 𝐿_{𝑝} (𝛾_{𝑝}, 𝛽_{𝑝}) \dots 𝐿_{𝑖} (𝛾_{𝑖}, 𝛽_{𝑖}) \dots 𝐿_{1} (𝛾_{1}, 𝛽_{1}) | 𝑠 ⟩ \\ = & | 𝜸, 𝜷 ⟩ . \end{aligned}

其中式(39) 第四行到式(39) 第五行是因为初态 $| 𝑠 ⟩$ 就是 $\prod_{𝑖 = 1}^{𝑛} 𝑿_{𝑖}$ 的特征向量。因此，在忽略全局相位的情况下能量景观也是不变的。

□

进一步地，将定理定理 8 推广至PUBO问题得到以下推论。

推论 2.（特殊情形下QAOA算法的能量景观的周期性 [8]）

若忽略全局相位，问题哈密顿量 ${𝓗︀}_{𝒞︀}$ 中仅包含偶数次项，那么对应的能量景观函数中，参数 $𝜷$ 的周期是 $\frac{𝜋}{2}$ ，即：

⟨ {𝓗︀}_{𝒞︀} ⟩ (𝜸, 𝛽_{1}, \dots, 𝛽_{𝑖} + \frac{𝜋}{2}, \dots, 𝛽_{𝑝}) = ⟨ {𝓗︀}_{𝒞︀} ⟩ (𝜸, 𝜷), 𝑖 = 1, 2, \dots, 𝑝

证明. 该推论为读者留作习题。

□

在这种特殊情况下，利用 $𝜷$ 参数的周期性，可以进一步将参数空间缩小到 ${[0, \frac{𝜋}{2}]}^{𝑝} {\times [0, \frac{𝜋}{2}]}^{𝑝}$ 。

五、QAOA 背后的图景

量子绝热算法利用量子绝热定理，通过设计一条演化路径，将易于制备基态的初始哈密顿量连续演化为问题哈密顿量。若演化足够缓慢且满足绝热条件，系统最终将处于问题哈密顿量的基态，此时对该态进行测量即可得到优化问题的解。QAOA 则借鉴量子绝热算法的思想，使用参数化量子电路分段近似模拟这一绝热演化过程。那么，QAOA 算法究竟是如何推演得到的呢？下面阐述这个问题。

假设总演化时间为T，选定的初始哈密顿量为H0，那么系统随时间演化到问题哈密顿量HC 的一种路径如下所示：

𝓗︀ (𝑡) = (1 - \frac{𝑡}{𝑇}) {𝓗︀}_{0} + \frac{𝑡}{𝑇} {𝓗︀}_{𝒞︀} .

若初始哈密顿量的基态是 $| 𝑠 ⟩$ ，定义时间演化算子 $𝑼 (𝑡)$ ，则系统绝热演化到某时间t 时哈密顿量的基态是 $𝜓 (𝑡) = 𝑼 (𝑡) | 𝑠 ⟩$ 。解含时薛定谔方程：

\frac{d}{d 𝑡} 𝜓 (𝑡) = - i 𝓗︀ (𝑡) 𝜓 (𝑡) ⟺ \frac{d}{d 𝑡} 𝑼 (𝑡) = - i 𝓗︀ (𝑡) 𝑼 (𝑡),

得到：

\begin{aligned} 𝑼 (𝑡) & = 𝒯︀ exp {- i \int_{0}^{𝑇} 𝓗︀ (𝜏) d 𝜏} \\ = lim_{𝑝 \to \infty} e^{- i 𝓗︀ (𝑡_{𝑝}) Δ 𝑡} \cdot e^{- i 𝓗︀ (𝑡_{𝑝 - 1}) Δ 𝑡} \cdot \dots \cdot e^{- i 𝓗︀ (𝑡_{1}) Δ 𝑡} e^{- i 𝓗︀ (𝑡_{0}) Δ 𝑡} . \end{aligned}

其中 $Δ 𝑡 = \frac{𝑇}{𝑝}$ ， $𝑡_{𝑘} = 𝑘 Δ 𝑡$ ； $𝒯︀$ 是时序算子，作用在于保证式(43) 中第二式中严格按时间顺序相乘。该式的导出不在此处给出，可以参考文献[8]。

那么，将式(43) 离散化得到近似，并代入式(41) 的线性演化路径，得到：

𝑼 (𝑡) \approx 𝒯︀ \prod_{𝑘 = 1}^{𝑝} exp {- i [(1 - \frac{𝑡_{𝑘}}{𝑇}) {𝓗︀}_{0} + \frac{𝑡_{𝑘}}{𝑇} {𝓗︀}_{𝒞︀}] Δ 𝑡},

再利用一阶 Lie-Trotter 近似，进一步得到：

𝑼 (𝑡) \approx 𝒯︀ \prod_{𝑘 = 1}^{𝑝} exp {- i (1 - \frac{𝑡_{𝑘}}{𝑇}) Δ 𝑡 {𝓗︀}_{0}} \cdot exp {- i \frac{𝑡_{𝑘}}{𝑇} Δ 𝑡 {𝓗︀}_{𝒞︀}} .

到这里相信读者能够看出，上式形式上已经基本对应到 QAOA 的整体分层形式即式(14) 了。不妨直接记 $𝐿_{𝑘} = exp {- i (1 - \frac{𝑡_{𝑘}}{𝑇}) Δ 𝑡 {𝓗︀}_{0}} \cdot exp {- i \frac{𝑡_{𝑘}}{𝑇} Δ 𝑡 {𝓗︀}_{𝒞︀}}$ ，再同时令 $𝛽_{𝑘} = (1 - \frac{𝑡_{𝑘}}{𝑇}) Δ 𝑡$ 、 $𝛾_{𝑘} = \frac{𝑡_{𝑘}}{𝑇} Δ 𝑡$ ，则 $𝑼 (𝑇) \approx \prod_{𝑘 = 1}^{𝑝} 𝐿_{𝑘 (𝛾_{𝑘}, 𝛽_{𝑘})}$ ，便得到前述的QAOA 构造了。

读者大概会疑惑于：既然按照如上的推导，角度参数 $𝛾, 𝛽$ 应当已经是唯一指定的了，又为何在 QAOA 中需要一个经典参数的训练步骤呢？首先，显然地，依据式(43)，当 QAOA 的层数 $𝑝 \neq 1$ 时，电路运行结果就是理想情况下量子退火得到的最优解。但是，当 $𝑝$ 是有限值时，便可以视作后续所有层酉算子都是 $𝑰$ ，对应能量景观函数值必然大于等于最优解对应的能量。这就会引入误差，影响收敛性，所以使用上述指定值时基本得不到足够好的结果，故而重新训练这些角度参数反而是更好的选择。

六、PUBO 电路构造中的构建块与合并

定义 1.（

𝑛

次单项式

𝑇 (𝑛)

）

$𝑇 (𝑛)$ 表示 $𝑛$ 次单项式。若参与该项的变量编号为 $𝑖_{1} < 𝑖_{2} < \dots < 𝑖_{𝑛}$ ，则：

𝑇 (𝑛) = 𝑥_{𝑖_{1}} 𝑥_{𝑖_{2}} \dots 𝑥_{𝑖_{𝑛}} .

定义 2.（

𝑛

重 Pauli-

𝑍

张量积

𝑍 (𝑛)

）

$𝑍 (𝑛)$ 表示 $𝑛$ 重 Pauli- $𝑍$ 张量积。若参与该项的量子比特编号为 $𝑖_{1} < 𝑖_{2} < \dots < 𝑖_{𝑛}$ ，则：

𝑍 (𝑛) = ⨂_{𝑟 = 1}^{𝑛} 𝒁_{𝑖_{𝑟}} .

在“三、分段近似模拟绝热演化” 已经说明，QAOA 中真正随具体优化问题改变的是问题酉算子 $𝑈 ({𝓗︀}_{𝒞︀}, 𝛾)$ 。若问题是 PUBO 形式，那么高阶单项式会在问题哈密顿量中产生多重 $𝑍$ 张量积。因此，直接把 PUBO 问题送入 QAOA 的核心问题可以重新表述为：如何从标量形式中的 $𝑇 (𝑛)$ 出发，得到若干个带系数的 $𝑍 (𝑛)$ 算子，并将这些 $𝑍 (𝑛)$ 算子系统地翻译为量子线路。

直觉上，最直接的方法是“按 $𝑇 (𝑛)$ 构造”：对 PUBO 标量哈密顿量中的每个单项式分别展开，并为其产生的每个 $𝑍 (𝑘)$ 项添加对应的电路构建块。不过，这种方法会在不同单项式之间反复生成相同的构建块。例如 $𝑥_{1} 𝑥_{2} 𝑥_{3}$ 和 $𝑥_{1} 𝑥_{2} 𝑥_{4}$ 在展开后都会产生作用于同一组量子比特的 $𝑍 (1)$ 、 $𝑍 (2)$ 以及 $𝑍 (1) 𝑍 (2)$ 项，这可以参考图 6；如果逐个 $𝑇 (𝑛)$ 直接生成线路，这些相同结构的构建块就会重复出现，只是 $𝑅 𝑍$ 门的角度不同，造成大量冗余。正因为如此，实际构造时更应当先把所有 $𝑇 (𝑛)$ 展开到 $𝑍 (𝑛)$ 的线性组合中，再合并相同的 $𝑍 (𝑛)$ 项，最后按 $𝑍 (𝑛)$ 构造电路。

图 6 $𝑇 (3)$ 对应的量子电路

由推论 1和图 4或者图 7 可知，若 $𝑍 (𝑘)$ 前带有系数 $𝛼$ ，那么其对应的电路基本构建块（Building Block）为：

\begin{aligned} 𝑈 (𝛼 𝑍 (𝑛), 𝛾) & = e^{- i 𝛼 𝛾 𝑍 (𝑛)} \\ = (\prod_{𝑘 = 1}^{𝑛 - 1} {CNOT}_{𝑖_{𝑛}}^{𝑖_{𝑘}}) \cdot 𝑅 𝑍_{𝑖_{𝑛}} (2 𝛼 𝛾) \cdot (\prod_{𝑘 = 1}^{𝑛 - 1} {CNOT}_{𝑖_{𝑛}}^{𝑖_{𝑛 - 𝑘}}) . \end{aligned}

也就是说，先按 $𝑖_{1}, \dots, 𝑖_{𝑛 - 1}$ 的顺序把这些量子比特作为控制位、 $𝑖_{𝑛}$ 作为目标位作用 $CNOT$ 门；再在 $𝑖_{𝑛}$ 上作用 $𝑅 𝑍 (2 𝛼 𝛾)$ ；最后按反向顺序再次应用这些 $CNOT$ 门。这种结构就是 PUBO 线路构造中最基本的构建块。

定义 3.（子序列）

对序列

𝑆 = (𝑠_{1}, 𝑠_{2}, \dots, 𝑠_{𝑛})

，若

𝑆^{'} = (𝑠_{𝑖_{1}}, 𝑠_{𝑖_{2}}, \dots, 𝑠_{𝑖_{𝑘}})

满足

1 \leq 𝑖_{1} < 𝑖_{2} < \dots < 𝑖_{𝑘} \leq 𝑛

，则称

𝑆^{'}

是

𝑆

的一个子序列。它可以通过删除

𝑆

中的一些元素得到，同时保持剩余元素的相对顺序不变。

现在先说明“按 $𝑇 (𝑛)$ 构造”会发生什么。考虑一个 $𝑛$ 次 PUBO 单项式：

𝑇_{𝑙} (𝑛) = 𝑥_{𝑖_{1}} 𝑥_{𝑖_{2}} \dots 𝑥_{𝑖_{𝑛}} .

由于每个二进制变量满足 $𝑥 = \frac{1 - 𝑠}{2}$ ，而量子哈密顿量中 $𝑠_{𝑖}$ 对应 $𝒁_{𝑖}$ ，所以该单项式会被展开为：

𝛼_{𝑙} 𝑇_{𝑙} (𝑛) ⟶ \frac{𝛼_{𝑙}}{2^{𝑛}} \prod_{𝑟 = 1}^{𝑛} (𝑰 - 𝒁_{𝑖_{𝑟}}) .

展开后，除了常数项以外，每一个非空子序列 $(𝑖_{𝑗_{1}}, \dots, 𝑖_{𝑗_{𝑘}})$ 都对应一个 $𝑘$ 重 $𝑍$ 算子：

⨂_{𝑚 = 1}^{𝑘} 𝒁_{𝑖_{𝑗_{𝑚}}} .

因此，从一个 $𝑛$ 次单项式出发，会产生所有非空子序列对应的构建块。子序列中的编号说明相应的 $𝑍 (𝑘)$ 算子具体作用在哪些量子比特上。

由此可以得到一种直接但朴素的构造方式：逐项遍历代价函数中的每个 $𝛼_{𝑙} 𝑇_{𝑙} (𝑛)$ ，并对它展开出的每个非空子序列添加相应的构建块。对 $𝑇_{𝑙} (𝑛)$ 而言，若选取其中 $𝑘$ 个变量形成 $𝑍 (𝑘)$ ，则对应 $𝑅 𝑍$ 门角度中的系数符号为 ${(- 1)}^{𝑘}$ ，系数量级为 $\frac{𝛼_{𝑙}}{2^{𝑛}}$ ；换言之，其构建块中的 $𝑅 𝑍$ 参数可写成：

2 \cdot ({(- 1)}^{𝑘} \frac{𝛼_{𝑙}}{2^{𝑛}}) 𝛾 = {(- 1)}^{𝑘} \frac{𝛼_{𝑙} 𝛾}{2^{𝑛 - 1}} .

这种方法的优点是直观：从 PUBO 的标量形式出发，不需要先整理整个矩阵形式的哈密顿量。但它的问题也正发生在这里：每一个 $𝑇 (𝑛)$ 都会展开出 $2^{𝑛} - 1$ 个非空子序列，而不同的 $𝑇 (𝑛)$ 往往共享变量，因此它们展开出的许多 $𝑍 (𝑘)$ 会作用在完全相同的一组量子比特上。如果逐项添加线路，就会反复加入结构相同、只差角度的构建块。

更好的方法是先在哈密顿量层面做合并、再生成线路，也就是“按 $𝑍 (𝑛)$ 构造”。由于所有 $𝑍 (𝑘)$ 算子都是对角矩阵，所以它们两两对易，意味着每个构建块都可以在量子电路上随意摆放；而相同目标量子比特集合的构建块只是在同一个相位旋转角上累加。例如两个不同的三重 $𝑍$ 算子的构建块可以合并成一个构建块：

𝑅_{𝑍 𝑍}^{𝑖, 𝑗, 𝑘} (𝛾_{1}) \cdot 𝑅_{𝑍 𝑍}^{𝑖, 𝑗, 𝑘} (𝛾_{2}) = 𝑅_{𝑍 𝑍}^{𝑖, 𝑗, 𝑘} (𝛾_{1} + 𝛾_{2}) .

其中 $𝑅_{𝑍 𝑍}^{𝑖, 𝑗, 𝑘} (𝛾)$ 表示：

{CNOT}_{𝑘}^{𝑖} \cdot {CNOT}_{𝑘}^{𝑗} \cdot 𝑅 𝑍_{𝑘} (𝛾) \cdot {CNOT}_{𝑘}^{𝑗} \cdot {CNOT}_{𝑘}^{𝑖} .

式(53) 的直观含义是：相连且相反的CNOT链会相互抵消，之后两个 $𝑅 𝑍$ 旋转可以合并成一个角度为 $𝛾_{1} + 𝛾_{2}$ 的 $𝑅 𝑍$ 旋转。一般的 $𝑍 (𝑘)$ 构建块也具有同样的合并规则。

因此，基于 $𝑍 (𝑛)$ 的线路生成可以按如下步骤完成[9]。它和按 $𝑇 (𝑛)$ 构造的区别在于：前两步只在哈密顿量表达式中收集和合并项，还不立即生成电路；只有合并完成后，才为每个剩余的 $𝑍 (𝑘)$ 项生成一次构建块。

将 PUBO 标量哈密顿量逐项展开为 $𝑍 (𝑘)$ 算子的线性组合。对 $𝑇_{𝑙} (𝑛) = 𝑥_{𝑖_{1}} \dots 𝑥_{𝑖_{𝑛}}$ ，遍历序列 $(𝑖_{1}, \dots, 𝑖_{𝑛})$ 的所有非空子序列，并记录每个子序列对应的系数。
将作用在同一组量子比特上的 $𝑍 (𝑘)$ 项合并：若两个子序列完全相同，则把它们的系数相加。
遍历合并后的 $𝑍 (𝑘)$ 项，并对每一项使用式(48) 生成一个构建块。遍历顺序不影响结果，因为这些 $𝑍 (𝑘)$ 项彼此对易。

定理 9.（

𝑍 (𝑘)

构建块的门数）

一个

𝑘

重

𝑍

算子的构建块需要

1

个

𝑅 𝑍

门和

2 (𝑘 - 1)

个

CNOT

门。

证明. 由式(48) 或图 7 立即可知。

□

定理 10.（

𝑇 (𝑛)

所需构建块数量）

一个

𝑛

次单项式

𝑇 (𝑛)

会产生

2^{𝑛} - 1

个构建块。其中，

𝑍 (𝑘)

类型的构建块数量为

(\binom{𝑛}{𝑘})

。

证明.

𝑇 (𝑛)

的展开需要遍历

𝑛

个变量指标构成的序列的所有非空子序列。非空子序列的数量等于

𝑛

元集合的非空子集数量，即

2^{𝑛} - 1

。其中长度为

𝑘

的子序列数量就是从

𝑛

个指标中选出

𝑘

个指标的方式数，因此为

(\binom{𝑛}{𝑘})

。

□

推论 3.（无合并情况下

𝑇 (𝑛)

对应量子电路的门数量）

若不对不同构建块进行合并，那么一个 $𝑛$ 次单项式 $𝑇 (𝑛)$ 需要 $2^{𝑛} - 1$ 个 $𝑅 𝑍$ 门，以及：

\begin{aligned} \sum_{𝑘 = 1}^{𝑛} 2 (𝑘 - 1) (\binom{𝑛}{𝑘}) & = 𝑛 2^{𝑛} - 2 (2^{𝑛} - 1) \\ = (𝑛 - 2) 2^{𝑛} + 2 \end{aligned}

个

CNOT

门。

由此可见，若机械地从每个 $𝑇 (𝑛)$ 单项式生成线路， $𝑅 𝑍$ 门数量按 $𝑂 (2^{𝑛})$ 增长，而 $CNOT$ 门数量按 $𝑂 (𝑛 2^{𝑛})$ 增长。更重要的是，这个估计还没有计入不同 $𝑇 (𝑛)$ 之间的重复构建块：如果多个高阶单项式共享变量，按 $𝑇 (𝑛)$ 构造会把同一组量子比特上的 $𝑍 (𝑘)$ 构建块反复生成。对 NISQ 设备而言， $CNOT$ 门通常更昂贵也更容易引入噪声，因此合并构建块是直接处理 PUBO 问题时必须重视的预处理步骤。先合并相同量子比特集合上的 $𝑍 (𝑘)$ 项，再按 $𝑍 (𝑛)$ 生成电路，往往能显著减少冗余的 $CNOT$ 门。但必须承认：该合并不会改变门数量的渐近复杂度，仍然是指数级增长。

Bibliography

[1] E. Ising, “Beitrag zur Theorie des Ferromagnetismus,” Zeitschrift für Physik, vol. 31, no. 1, pp. 253–258, Feb. 1925, doi: 10.1007/BF02980577.
[2] E. Farhi, J. Goldstone, and S. Gutmann, “A Quantum Approximate Optimization Algorithm.” [Online]. Available: https://arxiv.org/abs/1411.4028
[3] N. Dattani, “Quadratization in discrete optimization and quantum mechanics.” [Online]. Available: https://arxiv.org/abs/1901.04405
[4] C. Grange, M. Poss, and E. Bourreau, “An introduction to variational quantum algorithms for combinatorial optimization problems,” 4OR, vol. 21, no. 3, pp. 363–403, Jul. 2023, doi: 10.1007/s10288-023-00549-1.
[5] K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii, “Quantum circuit learning,” Physical Review A, vol. 98, no. 3, 2018, doi: 10.1103/physreva.98.032309.
[6] D. Wierichs, J. Izaac, C. Wang, and C. Y.-Y. Lin, “General parameter-shift rules for quantum gradients,” Quantum, vol. 6, p. 677, Mar. 2022, doi: 10.22331/q-2022-03-30-677.
[7] A. Kandala et al., “Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets,” Nature, vol. 549, no. 7671, pp. 242–246, 2017, doi: 10.1038/nature23879.
[8] A. Giovagnoli, “An Introduction to the Quantum Approximate Optimization Algorithm.” [Online]. Available: https://arxiv.org/abs/2511.18377
[9] J. Wang, “Direct Application of QAOA Algorithm to PUBO Problem,” in 2025 4th Asia Conference on Algorithms, Computing and Machine Learning (CACML), 2025, pp. 1–8. doi: 10.1109/CACML64929.2025.11010958.