# 量子近似优化算法(QAOA)

```{card}
写于2023年11月15日
^^^
最近因工作需要研究了一下QAOA，注意到这篇文章[*A Review on Quantum Approximate Optimization Algorithm and its Variants*](https://arxiv.org/abs/2306.09198)，感觉不错。故将其中间有意思的内容记录于此。

```

## 定义

QAOA实际上可以认为是一种特殊的VQE，也可以认为是QAA的一种理论实现。

```{seealso}
### 变分算法

VQE (变分量子求解器, Variational Quantum Eigensolver) 是VQA (变分量子算法, Variational Quantum Algorithm) 思想的一种实现。其实在量子化学问题里这种想法就已经普遍应用了。

变分的思想就是说，有一个基于泛函$F[f(x)]$的优化问题，要在不停的变化的$f(x)$中找到一个$f_0(x)$，来达到$F$的极值。VQA就是想办法扰动$f(x)$使$F(f)$下降，直至收敛的方法。

在量子化学和量子计算中通常面临的此类问题就是对哈密顿量的能量最小化问题。

$$
\min\left(\braket{\alpha|H|\alpha}\right)
$$

这种情况下哈密顿量往往是确定的，所以通常对态矢进行参数化：

$$
\ket{\alpha} \Rightarrow \ket{\mathbf{\theta}}
$$

$\theta$通常是一组参数，在量子化学里可能是需要SCF过程求解的各类耦合参数，而在量子计算中可能是ansatz线路中的待优化参数[^1].
```

```{seealso}
### VQA & VQE
在量子线路里使用变分算法的思想就是VQA. 而使用量子经典混合的线路来实际完成这件事，则称为VQE.
```

```{seealso}
### QAA

量子绝热算法 (Quantum Adiabatic Algorithm) 是使用绝热定理的想法来实现对基态的搜索。绝热定理指出系统的一个态在绝热演化下一定会落在系统的基态上。对优化问题来说，目标函数的基态就是我们要搜索的优化结果，所以构造这种绝热演化就完事了。

通常会把初始态设置成一个好制备的哈密顿量$H_M$的基态。目标函数我们称为$H_C$，那么演化哈密顿量则为:

$$
H(t) = f(t)H_C + g(t)H_M
$$ (qaa-def)

一种简单的取法是

$$
\begin{cases}
& f(t) = \frac{t}{T} \\
& g(t) = 1 - \frac{t}{T}
\end{cases}
$$

显然在$t=T$时系统哈密顿量演化为了$H_C$. 对应的演化算符为:

$$
U(t) = e^{-i\int_0^t d\tau H(\tau)}
$$

可以对它进行Trotter化，

$$
U(t) \approx \prod_{k=0}^{r-1}\exp(-iH(k\Delta\tau)\Delta\tau)
$$ (qaa-trotter)

$$
\Delta\tau=\frac{t}{r}
$$
```

相较于QAA的演化思路，QAOA把乘积里的每一个项参数化了，以方便使用VQE的思路降低量子线路的深度。在公式{eq}`qaa-trotter`中的某一项变为:

$$
\begin{split}
\exp(-iH(k\Delta\tau)\Delta\tau) 
&= \exp(-if(k\Delta\tau)H_C\Delta\tau)\exp(-ig(k\Delta\tau)H_M\Delta\tau) \\
&= \exp(-i\gamma H_C)\exp(-i\beta H_M) \\
&= U_C(\gamma)U_M(\beta)
\end{split}
$$

其中第一行来自于公式{eq}`qaa-def`, 第二行是QAOA的ansatz. 因为$H_C$和$H_M$都是有很多项的，实际的线路中这些项共享一个参数，称为一层 (layer). 一层包含cost层和mix层，即$H_C$和$H_M$的下标对应的层。可以看到在QAOA拟设中，每一层已经和时间小区间$\Delta\tau$无关了，因此也不需要严格的指定层数。

```{figure} pics/qaoa_workflow.png
---
figclass: margin-caption
name: qaoa-workflow
---
QAOA作为VQE的一个特例，有着类似的优化工作流。图片来自题记中的原始论文。
```

## 在 MaxCut 问题上的使用

对MaxCut问题[^2]而言，目标哈密顿量常常定义为:

$$
H_C = \frac{1}{2} \sum_{i,j\in e} w_{ij}(I-Z_iZ_j)
$$

而mix layer通常定义为:

$$
H_M = \sum_{i\in v} X_i
$$

显然这二者是对易的，初态可以用一串$H$门来制备。

```{figure} pics/qaoa_all_in_one.png
---
figclass: margin-caption
name: qaoa_all_in_one
---
很好看的一张图片，可以说我是为了这张图写的这篇译文。图片来自题记中的原始论文。
```

## 几种有意思的QAOA变种 (Ansatz Vatiants)

- `DC-QAOA`[^3][^4]: Digitized Counterdiabatic - QAOA. 增加了所谓"counterdiabatic driving term", 听起来很科学。据说能在降低线路深度的同时增加收敛率。
- `QAOAnsatz`[^5]:  Quantum Alternating Operator Ansatz - QAOAnsatz. 似乎适用于有约束的体系，实用价值可能不错。
- `Constraint Preserving Mixers`[^6]: 能解决有硬约束的问题。

## 复杂度分析

在最大割问题中，一般认为QAOA将使用$O(n^2p)$个门，并且运行时间为$O(np)$, 这里$n$是顶点数，$p$是层数。然而，目前的经验结果表明QAOA的速度仍然和经典算法有差距，参数的数量似乎实际上对时间的影响很大，对参数的优化速度可能是目前的最大问题。

## 解的质量

QAOA解的质量在不同的体系下不同，理论上似乎没有GW那么好的保证，但是经常能找到还不错的结果。

<!-- 以下是side note -->

[^1]: 这里就不对每个名词做细节解释了，毕竟只是个博文~
[^2]: 一类组合优化问题
[^3]: 10.1103/PhysRevResearch.4.013141
[^4]: 10.22331/q-2022-01-27-635.
[^5]: 10.3390/a12020034
[^6]: 10.3390/a15060202