这周教课刚好说了QAOA (Quantum Approximate Optimization Algorithm，量子近似优化算法)，我再把自己写的note翻译成中文讲一遍，哈哈哈。其他的教科书级别的经典算法，比如Shor算法，Deutsch–Jozsa算法，随便找本量子计算的书都写得很清楚，也就不在这里赘述了（主要是我懒）

未经授权禁止转载！要转载之前先私信问下作者（就是本人）同不同意，谢谢合作。

0、约定一些记号

因为我在这里讨论的是量子计算里研究的问题，所以在取了一组基之后，可以认为量子态的空间（规范化之前）就是有限维复线性空间 ，算子被认同为矩阵 。这里，依照习惯， 其中 是量子比特的数量。量子态我都写成列向量，而不采用Dirac记号了（同样，因为懒，不想打\langle or \rangle）， 。内积记成 。Planck常数令为1（还是因为懒）。

1、从量子控制的角度引出QAOA

量子控制，顾名思义就是给量子系统加控制来实现某一特定的目的。我们先考虑一个如下的量子控制问题 。其中， 是控制。我们可以考虑引入时间演化矩阵 ，上面的方程成为 。特别的，如果 不含时间，解可以形式化得写成 。

为了得到QAOA，我们考虑一个特殊形式的控制，布尔函数， 。那么，上面的控制其实就是交替作用两个哈密顿量。假设控制函数有 次交替，这个控制也同时等同于一个时间的序列， 。其中， 作用的时间是 ， 作用的时间是 。可以想象一下，两束激光分别交替打开与否，时间由这个序列给出。（不需要太纠结刚开始的时候 ，scale一下就一样了）。根据前面的讨论，总的时间演化矩阵为 ，其中 。这就是QAOA的ansatz。可见，QAOA是一种对酉矩阵的参数化，参数就是时间。QAOA的好处也有不少，比如实现起来简单（交替作用两个哈密顿量），优化比较简单（自由度都放到时间上了）。

2、QAOA的普遍性(universality)

不知道这么翻译对不对。上面已经说了，QAOA是一种对酉矩阵的参数化，那么很自然的问题就是这个参数化到底在酉群里能张出来多大（或者说能近似多少酉矩阵）。这里先改一下记号， 是一个 层参数为 的QAOA。记 为 层QAOA可以表示的酉矩阵的集合。显然， ，置一层时间为0可见。上面我们取QAOA ansatz的时候要求层数固定为了固定自由度以便优化，如果不加此限制，那么QAOA可达的集合为 。如果 在 中稠密，那么就称由 生成的QAOA是universal的。这里不过多讨论universality，只给出一些思路。由于酉群是连通的，任意一个酉矩阵都能由李代数，对于酉群就是厄米矩阵，中的元素 ，表示成 。又由BCH公式， 。因此，如果由 生成的李代数满足 ，那么QAOA就是universal的。对于具体的例子的分析可以参考后面贴的几篇paper。

3、QAOA优化问题的一般形式

之前已经说了，QAOA提供了一个酉矩阵参数化的ansatz。那么，我们可以定义一个含有 目标函数 来描述QAOA参数在当前问题下的表现如何。并且还可以对参数加以限制，比如要求时间小于某个数可以要求 。因此，优化问题的一般形式为

其中 是可行域。求解的方法也有很多，可以用比如梯度下降，牛顿法，次序凸规划（每一步求解一个凸子问题），神经网络近似，或者强化学习。具体可以参考后面贴的几篇paper。

为了方便讨论，下面都假设已经给定了一个universal的QAOA。

4、应用

（1）量子门的近似

直接对量子门分解到universal gate set是非常困难的。既然量子门就是个酉矩阵，那我们可以考虑用QAOA作为ansatz来近似。首先要给一些定义方便量化的讨论逼近的有多好。先定义一下Hilbert-Schmidt内积或者Frobenius内积。注意的是，我下面给的定义跟标准的定义差一个常数。

定义 1. (Hilbert-Schmidt inner product or Frobenius inner product)
是定义在线性空间 上的内积。

有这个内积诱导的范数就是Frobenius范数（差一个常数）。再给一个命题。

命题 2.
是两个酉矩阵。 当且仅当 ，即二者相等up to一个global phase。（在量子力学意义下就是一样的）

Pf. 直接算就行， 由Cauchy-Schwarz不等式。

因此，用QAOA近似量子门的目标函数可以取做 。

（2）量子态制备

现在的任务是给定一个初始态 ，如何将其变成 。依然考虑QAOA ansatz， 为目标函数。实际上可以把这个问题看成上一个问题的特例。选取一个坐标变换使得 ，那么这个目标函数实际上只关注 的第一列，最优解显然不唯一。直接暴力Gram-Schmidt正交化都能构造出一大堆。

（3）求解基态

量子力学有变分原理。

命题 3.
是一个厄米矩阵。则任意态下的期望值给出最小特征值的上界， ，等号成立当 是最小特征值对应的特征向量。

我们可以考虑QAOA参数化尝试变分函数 ，如果 已经规范化， 是规范化的。取目标函数为 。

（4）最大割问题

这也是QAOA提出来时要解决的问题。给定一张图 ，最大割问题要求解的是对节点的划分，使得将原图分成两个子图，并且破坏的边数最大。

先把这个问题变成一个量子力学问题。给每个节点加一个自旋，自旋相同的分成一组，那么节点上的Pauli矩阵 给出这个节点的自旋。对于一条边， ，矩阵 作用下给出 说明自旋同向属于同一组， 说明自旋反向属于不同组。给图定义如下的厄米矩阵， 。每一条边的自旋反转贡献能量变化 ，因此，最大割是这一厄米矩阵的基态。由（3）中的方法求解就可以。

总结

QAOA作为一个经典-量子杂交算法（hybrid algorithm）还是很好的，虽然也有一些问题，比如优化系统尺度一大就很复杂很不好求解，但是总的来说还是很有潜力的算法。

参考文献

[1] Marin Bukov, Alexandre GR Day, Dries Sels, Phillip Weinberg, Anatoli Polkovnikov, and Pankaj Mehta. Reinforcement learning in different phases of quantum control. Physical Review X, 8(3):031086, 2018.

[2] Yulong Dong, Xiang Meng, Lin Lin, Robert Kosut, and K Birgitta Whaley. Robust control op- timization for quantum approximate optimization algorithm. arXiv preprint arXiv:1911.00789, 2019.

[3] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm, 2014.

[4] Robert L Kosut, Matthew D Grace, and Constantin Brif. Robust control of quantum gates via sequential convex programming. Physical Review A, 88(5):052326, 2013.

[5] Seth Lloyd. Quantum approximate optimization is computationally universal. arXiv preprint arXiv:1812.11075, 2018.

[6] Mauro ES Morales, Jacob Biamonte, and Zolt an Zimbor as. On the universality of the quantum approximate optimization algorithm. arXiv preprint arXiv:1909.03123, 2019.

[7] Murphy Yuezhen Niu, Sirui Lu, and Isaac L Chuang. Optimizing qaoa: Success probability and runtime dependence on circuit depth. arXiv preprint arXiv:1905.12134, 2019.

[8] Jiahao Yao, Marin Bukov, and Lin Lin. Policy gradient based quantum approximate optimiza- tion algorithm. arXiv preprint arXiv:2002.01068, 2020.