一篇不把推导留作读者练习的 QAOA 算法完整教程

这篇笔记是一份关于量子近似优化算法（Quantum Approximate Optimization Algorithm，QAOA）的完整入门推导，代数步骤会直接写出，而不是留作练习。重点是组合优化中常用的标准 Ising 式表述、它与绝热量子计算的联系、电路如何构造，以及如何计算最简单推导中出现的算符恒等式。

问题定义

QAOA 是一种用于近似求解优化问题的变分量子算法。经典目标函数被编码进代价哈密顿量 \(C\)，算法制备一个带参数的量子态；根据符号约定不同，对该量子态测量得到的分布会偏向低代价或高代价的比特串。

对于一个二进制优化问题，把候选解写成比特串

\[z = z_1 z_2 cdots z_n, qquad z_i in {0,1}.\]

目标函数为每个比特串赋予一个实数值 \(C(z)\)。在 QAOA 中，我们把这个经典函数提升为一个对角量子算符

\[C |zrangle = C(z)|zrangle.\]

算法还会使用一个混合哈密顿量，通常为

\[B = sum_{j=1}^{n} X_j,\]

其中 \(X_j\) 是作用在第 \(j\) 个量子比特上的 Pauli \(X\) 算符。对于深度 \(p\)，QAOA 态为

\[|gamma,betarangle = e^{-ibeta_p B} e^{-igamma_p C} cdots e^{-ibeta_1 B} e^{-igamma_1 C} |srangle,\]

其中

\[|srangle = |+rangle^{otimes n}\]

是所有计算基态上的均匀叠加。经典外层循环选择角度

\[(gamma_1,ldots,gamma_p,beta_1, ldots,beta_p)\]

来优化期望值

\[F_p(gamma,beta)=langle gamma,beta|C|gamma,betarangle.\]

对于最大化问题，我们尝试最大化 \(F_p\)。对于最小化问题，可以最小化同一个表达式，或者改变代价哈密顿量的符号。

横场 Ising 模型

许多 QAOA 示例使用 Ising 哈密顿量，因为二进制变量可以自然地由 Pauli \(Z\) 算符表示。对于两个量子比特，一个常见的相互作用项是

\[Z_i Z_j.\]

基于图的代价哈密顿量通常具有如下形式

\[C = sum_{(i,j)in E} w_{ij} Z_i Z_j,\]

也可能再加上一体局域场

\[sum_i h_i Z_i.\]

横场部分就是混合器

\[B = sum_i X_i.\]

因此，QAOA 中交替出现的两个部分是：

  1. 对角 Ising 代价演化 \(e^{-igamma C}\)，以及
  2. 横场混合演化 \(e^{-ibeta B}\)。

有用的一点是，许多项彼此对易。所有 \(Z_iZ_j\) 项都是对角的，所以它们相互对易。所有 \(X_i\) 项也相互对易，因为它们作用在不同量子比特上。这使我们可以把指数算符实现为单量子比特门和双量子比特门的乘积。

绝热量子计算

QAOA 可以看作绝热量子计算的一种数字化、变分版本。

在绝热图像中，我们从一个基态容易制备的简单哈密顿量开始，例如

\[H_B = -sum_i X_i.\]

它的基态是 \(|+rangle^{otimes n}\)。然后我们缓慢地把哈密顿量改变为问题哈密顿量 \(H_C\)：

\[H(t) = (1-s(t))H_B + s(t)H_C,\]

其中 \(s(0)=0\) 且 \(s(T)=1\)。如果插值足够缓慢，并且谱隙表现良好，那么绝热定理说明状态会近似跟随瞬时基态。

QAOA 用交替脉冲替代这个连续过程：

\[e^{-ibeta B}e^{-igamma C}.\]

当深度 \(p\) 很大时，这个序列类似于经过 Trotter 化的绝热路径。当深度较小时，角度被视为自由的变分参数，并直接进行优化。

电路设计

对于一层 QAOA，电路有三个部分。

  1. 制备初始态：
\[|0rangle^{otimes n} xrightarrow{H^{otimes n}} |+rangle^{otimes n}.\]
  1. 施加代价酉算符：
\[U_C(gamma)=e^{-igamma C}.\]

对于一条 Ising 边 \((i,j)\)，双量子比特项为

\[e^{-igamma w_{ij} Z_iZ_j}.\]

一种标准分解是：

CNOT(i, j)
RZ(2 gamma w_ij) on j
CNOT(i, j)

角度的符号取决于量子 SDK 对 \(R_Z(theta)\) 的约定。务必根据本地门定义进行核对。

  1. 施加混合器酉算符：
\[U_B(beta)=e^{-ibetasum_i X_i}=prod_i e^{-ibeta X_i}.\]

由于许多 SDK 定义

\[R_X(theta)=e^{-itheta X/2},\]

因此通常实现为

RX(2 beta) on every qubit

同样，要根据本地 SDK 定义核对符号和二倍因子。

完整的深度 \(p\) 电路会重复代价块和混合器块：

H on every qubit
for layer = 1..p:
    apply cost unitary with gamma[layer]
    apply mixer unitary with beta[layer]
measure

编码

一个最小实现有三个组成部分：

  1. 一个根据给定参数构造 QAOA 电路的函数，
  2. 一个根据测量计数估计期望代价的函数，以及
  3. 一个更新角度的经典优化器。

伪代码：

def qaoa_circuit(graph, gammas, betas):
    circuit = QuantumCircuit(len(graph.nodes))

    for q in graph.nodes:
        circuit.h(q)

    for gamma, beta in zip(gammas, betas):
        for i, j, weight in graph.edges(data="weight", default=1.0):
            circuit.cx(i, j)
            circuit.rz(2 * gamma * weight, j)
            circuit.cx(i, j)

        for q in graph.nodes:
            circuit.rx(2 * beta, q)

    circuit.measure_all()
    return circuit

要评估一个比特串，需要定义与构造哈密顿量时相同的代价函数。例如，对于 Ising 目标：

def spin(bit):
    return 1 if bit == "0" else -1


def ising_cost(bitstring, edges):
    total = 0.0
    for i, j, weight in edges:
        total += weight * spin(bitstring[i]) * spin(bitstring[j])
    return total

然后根据计数估计期望值：

def expected_cost(counts, edges):
    shots = sum(counts.values())
    return sum(ising_cost(bits, edges) * count / shots for bits, count in counts.items())

这里刻意保持与 SDK 无关。在真实实现中，需要检查后端或模拟器的比特顺序约定。有些框架返回的比特串，其视觉顺序相对于量子比特索引是反过来的。

平凡态制备

经过几天的思考和查阅资料后，我决定回答自己的问题。

N.B. 当没有混淆风险时，张量积符号 otimes 会被省略，尤其是在指标不同时。用符号表示就是 A_iB_j = A_i otimes B_j (i neq j)。

首先，对于 e^{i beta B} Z_i Z_j e^{-i beta B} 的情形，只考虑量子比特 j，其中 B_e=sum_{k in e}{X_k}。由于 X_i 和 X_j 作用在不同量子比特上，

begin{equation*}e^{i{(X_i+X_j)}}=e^{i((X_iotimes I_j)+(I_i otimes X_j))}=e^{iX_i}e^{iX_j}.end{equation*}

现在，

begin{equation*} begin{aligned} e^{-i beta X} & = e^{-i beta begin{bmatrix}0 & 1\ 1 & 0end{bmatrix}} \ & = e^{-i beta begin{bmatrix}frac{1}{sqrt{2}} & frac{1}{sqrt{2}}\ frac{1}{sqrt{2}} & -frac{1}{sqrt{2}}end{bmatrix} begin{bmatrix}1 & 0\ 0 & 1end{bmatrix} begin{bmatrix}frac{1}{sqrt{2}} & frac{1}{sqrt{2}}\ frac{1}{sqrt{2}} & frac{1}{sqrt{2}}end{bmatrix}} \ & = begin{bmatrix}frac{1}{sqrt{2}} & frac{1}{sqrt{2}}\ frac{1}{sqrt{2}} & -frac{1}{sqrt{2}}end{bmatrix} begin{bmatrix}e^{-i beta} & 0\ 0 & e^{-i beta}end{bmatrix} begin{bmatrix}frac{1}{sqrt{2}} & frac{1}{sqrt{2}}\ frac{1}{sqrt{2}} & frac{1}{sqrt{2}}end{bmatrix} \ & = begin{bmatrix}cos(beta) & -isin(beta)\ -isin(beta) & cos(beta)end{bmatrix} \ & = Icos(beta)-iXsin(beta). end{aligned} end{equation*}

因此，

begin{equation*}begin{aligned}e^{i beta X}& = Icos(beta)+iXsin(beta).end{aligned}end{equation*}

于是，

begin{equation*}begin{aligned}e^{i beta X} Z e^{-i beta X} & = (Icos(beta)+iXsin(beta))Z(Icos(beta)-iXsin(beta)) \& = Z cos(2beta) + Ysin(2beta).end{aligned}end{equation*}

对于横场 Ising 哈密顿量，考虑 G_{e=(i,k)}=Z_iZ_k。

对于 e^{i gamma Z_iZ_k}，它可以计算为

begin{equation*} begin{aligned} e^{i gamma Z_iZ_k} = & e^{i gamma begin{bmatrix}1&&&\&-1&&\&&-1&\&&&1end{bmatrix}} = begin{bmatrix}e^{igamma}&&&\&e^{-igamma}&&\&&e^{-igamma}&\&&&e^{igamma}end{bmatrix} \ = & begin{bmatrix}cosgamma+isingamma &&&\&cosgamma-isingamma&&\&&cosgamma-isingamma&\&&&cosgamma+isingammaend{bmatrix} \ = & cosgammabegin{bmatrix}1&&&\&1&&\&&1&\&&&1end{bmatrix}+isingammabegin{bmatrix}1&&&\&-1&&\&&-1&\&&&1end{bmatrix} \ = & I_i I_k cosgamma + i Z_1Z_2 singamma. end{aligned} end{equation*}

我们可以独立计算双量子比特操作：

begin{equation*}Y_i (Z_i Z_k) = (Y_i otimes I_k)(Z_i otimes Z_k)=(Y_i Z_i) otimes (I_kZ_k) = i X_i otimes Z_k = i X_i Z_k.end{equation*}

如果你无法说服自己，也可以用数值形式看：

begin{equation*}Y_i otimes I_k = begin{bmatrix} &&-i&\&&&-i\i&&&\&i&& end{bmatrix}end{equation*}

以及

begin{equation*}Z_i otimes Z_k = begin{bmatrix} 1&&&\&-1&&\&&-1&\&&& 1end{bmatrix}end{equation*}

并且

begin{equation*}(Y_i otimes I_k)(Z_i otimes Z_k) = begin{bmatrix} &&i&\&&&-i\i&&&\&-i&&end{bmatrix} = i(X_i otimes Z_k).end{equation*}

现在，来看一个更具体的例子，

begin{equation*} begin{aligned} e^{-i gamma Z_iZ_k} Y_i e^{i gamma Z_iZ_k} & = (I_i I_k cosgamma - i Z_1Z_2 singamma) (Y_i otimes I_k) (I_i I_k cosgamma + i Z_1Z_2 singamma) \ & = Y_i cos^2gamma - Y_isin^2gamma - X_i Z_ksingammacosgamma - X_i Z_k singammacosgamma \ & = Y_i cos 2gamma - X_iZ_ksin 2gamma. end{aligned} end{equation*}

Q.E.D.

参考文献

  1. Choi J, Kim J. A Tutorial on Quantum Approximate Optimization Algorithm (QAOA): Fundamentals and Applications. In: 2019 International Conference on Information and Communication Technology Convergence (ICTC). IEEE; 2019. doi:10.1109/ictc46691.2019.8939749

Leave a Reply