Tldr

通过绝热定理，我们可以写出哈密顿量的一个形式：

H = \sum_{i = 1}^NH_i

又根据含时哈密顿量在薛定谔方程中的解，我们可以得出

根据 Trotter-Suzuki decomposition

我们可以将系统最终演化酉变换写为：

U(H, t, p) = \prod^p_{j=1}\prod_ke^{\frac{-iH_kt}{n}}, H = \sum_k H_k

而 QAOA 就是在这个基础上，让哈密顿量在基态与问题哈密顿量之间切换，通过优化时间的参数，来达到优化最终损失函数的目的

A Quantum Approximate Optimization Algorithm#

Abstract

We introduce a quantum algorithm that produces approximate solutions for combinatorial optimization problems. The algorithm depends on a positive integer p and the quality of the approximation improves as p is increased. The quantum circuit that implements the algorithm consists of unitary gates whose locality is at most the locality of the objective function whose optimum is sought. The depth of the circuit grows linearly with p times (at worst) the number of constraints. If p is fixed, that is, independent of the input size, the algorithm makes use of efficient classical preprocessing. If p grows with the input size a different strategy is proposed. We study the algorithm as applied to MaxCut on regular graphs and analyze its performance on 2-regular and 3-regular graphs for fixed p. For p = 1, on 3-regular graphs the quantum algorithm always finds a cut that is at least 0.6924 times the size of the optimal cut.

组合优化问题的编码#

任意一个组合优化问题都可以被编码为 MAX-SAT 的形式（个变量，条子句），并使用这个 0-1 变量定义一个目标函数：

C(z) = \sum^m_{\alpha=1}C_{\alpha}(z)

其中，，为一个比特串，表示第条子句是否满足

对于一个量子计算机，其运行在一个维的希尔伯特空间内，我们需要求得的比特串为，使得最大

我们通过量子计算原理中的内容，将目标改写为通过构造一个参数，使我们能够求得哈密顿量的基态，也就是使得损失函数最小的量子态

在介绍如何构造哈密顿量之前，我们引入一个理论基础

绝热量子计算#

那么，我们构建一个含时的哈密顿量演化过程如下，其中，其对应的本征态为，注意这里的表示张量积

\hat{H}(t) = (1 - s(t))H_B + s(t)H_P

其中，

Tldr

通过薛定谔方程，我们可以直接求得

\begin{aligned}
\ket{\psi} &= \mathcal{T}\exp{(\frac{-i}{\hbar}\int^{t}_{0}\hat{H}(t)dt)\ket{\psi_0}}\\
&= U(t)\ket{\psi_0}
\end{aligned}

我们期望演化足够缓慢，于是，换而言之，我们对这个区间进行细分，得到：

\hat{H}(t) = \prod_j^p \bigg((1 - s(j\Delta t))H_B + s(j\Delta t)H_P \bigg)\Delta t

本质上，我们相当于演化了次，每次的时间为，我们可以通过以下等式求得经过次演化的本征态：

\ket{\psi} = \prod_i U_i\ket{\psi_0}

其中是一个酉变化，根据上面提到的哈密顿量演化过程，我们可以将其写为如下形式：

\ket{\psi} = \prod^p_{j=1} \exp \Bigg(-i \bigg( (1 - s(j\Delta t))H_B + s(j\Delta t)H_P \bigg)\Delta t \Bigg)\ket{\psi_0}

进一步的，为了方便电路的实现，对每次的演化，我们规定如下：

\begin{aligned}
s(t) = 1 &,  t \in [0, \gamma_1) \\
s(t) = 0 &, t \in [\gamma_1, \gamma_1 + \beta_1)\\
s(t) = 1 &, t \in [\gamma_1 + \beta_1, \gamma_1 + \beta_1 + \gamma_2)\\
&\vdots
\end{aligned}

也就是来回演化与，那么我们可以写出的表达如下：

\begin{aligned}
\ket{\psi(\overrightarrow{\gamma}, \overrightarrow{\beta})} &= e^{-iH_B\beta_p}\times e^{-iH_P\gamma_p} \times \dots \times e^{-iH_B\beta_1} \times e^{-iH_P\gamma_1} \ket{+} \\
&= \prod^p_{j=1} e^{-iH_B\beta_j} e^{-iH_P\gamma_j} \ket{+} \\
&= \prod^p_{j=1}U_B^{(j)}U_C^{(j)} \ket{+}
\end{aligned}

我们令，即可得到：

\ket{\psi(\theta)} = \prod^p_{j=1}U_B^{(j)}U_C^{(j)} \ket{+}

其中，

根据量子计算理论基础可以知道，我们现在就得到了一个可以使用经典优化器优化的模型：

C(\theta) = \bra{\psi(\theta)}H\ket{\psi(\theta)}

通过测量得到后，调用传统优化器更新（梯度下降，牛顿法，单纯形法等），不断重复这个过程，如下图所示：

最后，我们在基态中测量，测得概率最大的一个作为问题的解

最小顶点覆盖示例#

考虑上的 MVC 问题，我们的目标是选取最少的顶点，使得所有的边均覆盖

于是，对于每个顶点，我们使用这个量子比特来表示，其为的叠加态，那么对这个图而言，我们需要求得一个比特串，这个比特串的第位表示顶点是否被选择，那么对于整个量子系统，我们可以写出的表示为个量子比特的张量积：

\ket{z} = \ket{\psi_i} \otimes \dots \otimes \ket{\psi_n}

问题的哈密顿量为：

H_C \ = \ 3 \sum_{(i, j) \in E(G)} (\sigma^i_z \sigma^j_z \ + \ \sigma^i_z \ + \ \sigma^j_z) \ - \

                  \displaystyle\sum_{i \in V(G)} \sigma^i_z

其中

于是，我们的目的就是求得当哈密顿量最小时的基态的值

考虑一个简单的图，如下所示，显然其最小顶点覆盖的解为：{2, 1}，需要求得的量子比特位（当然也有其他解）

我们考虑两层的 QAOA 算法，线路如下所示：

随后，我们使用梯度下降优化器来优化参数，使得取得最小值，我们运行 70 轮：

最终，我们测量出现概率最高的基态：

概率最高的也同样是，但我们发现其实还有错误的解，如果我们扩大，那么可以测量得到如下结果：

可以发现现在概率高的都已经是正确解了

QAOA 算法