上次的文章量子近似优化算法（一）介绍了量子近似优化算法及其相关的概念，并留下最终的问题，即如何找到最优化的参数 $(\vec{\gamma}^*, \vec{\beta}^*)$ 最大化算符的平均值 $\langle\psi_p(\vec{\gamma}, \vec{\beta})|H_C|\psi_p(\vec{\gamma}, \vec{\beta})\rangle$ ，本次文章主要介绍QAOA 算法的参数优化问题。

参考文献

[1] Zhou, L., Wang, S. T., Choi, S., Pichler, H., & Lukin, M. D. (2018). Quantum approximate optimization algorithm: performance, mechanism, and implementation on near-term devices. arXiv preprint arXiv:1812.01041.

Fixed p algorithm

前面我们介绍了QAOA的算法流程，如下图所示：

而现在，我们的主要任务是寻找参数 $\vec{\gamma}, \vec{\beta}$ 的最优解。寻找参数的最简单但最有效的方法即为网格搜索，但这种方法耗时耗力，随着参数数量的增多，搜索空间成指数增长，因而我们需要更为高效的方法进行参数优化，寻找最优解。

回忆一下之前MaxCut问题，就是要让如下表达式最大化：

$H_C=\sum_\limits{\langle j k\rangle} \frac{1}{2} (1-\sigma_j^z\sigma_k^z)$

其中， $\langle jk\rangle$ 为表示链接节点 $j,k$ 的边。前面我们说过，衡量 $H_C$ 大小的方式是求算符的平均值，即：

$F_p(\gamma, \beta)=\langle s|H_C|s\rangle=\frac{1}{2}\sum\limits_{\langle jk\rangle}\langle s|(1-\sigma_j^z\sigma_k^z)|s\rangle\\=\frac{1}{2}\sum\limits_{\langle jk\rangle}\langle s|H_{C,\langle jk\rangle}|s\rangle$

其中 $|s\rangle$ 是系统制备的初态，我们最终需要制备的得到的量子态为：

$|\psi_p(\vec{\gamma}, \vec{\beta})\rangle=U_B(\beta_p)U_C(\gamma_p)\cdots U_B(\beta_1)U_C(\gamma_1)|s\rangle$

其中， $U_B(\beta)=e^{-i\beta H_B}=e^{-i\beta \sum_{j=1}^n \sigma_j^x}$ 、 $U_C(\gamma)=e^{-i\gamma H_C}$ 。因此有，

$F_p(\gamma, \beta)=\sum\limits_{\langle jk\rangle}\langle s|U^{\dagger}_C(\gamma_1)\cdots U_B^{\dagger}(\beta_p)H_{C,\langle jk\rangle}U_B(\beta_p)\cdots U_C(\gamma_1)|s\rangle$

其中 $H_{C,\langle jk\rangle}=\frac{1}{2} (1-\sigma_j^z\sigma_k^z)$ 。到这里，上面都很好理解，因为我们在上一篇博文中，也说过，QAOA的过程本质上就是制备一个量子态，而这里一系列的酉算符就是作用在态上的，其本质也是一个制备态的过程。

但是从数学上，我们可以仅考虑算符的部分，即

$U^{\dagger}_C(\gamma_1)\cdots U_B^{\dagger}(\beta_p)H_{C,\langle jk\rangle}U_B(\beta_p)\cdots U_C(\gamma_1)$

对于 $p=1$ 这种最简单的情况，可以写成

$U^{\dagger}_C(\gamma_1) U_B^{\dagger}(\beta_1)H_{C,\langle jk\rangle}U_B(\beta_1) U_C(\gamma_1)$

由于每一次只考虑两个粒子 $j,k$ ，因此 $U_B(\beta)$ 只用考虑两个粒子，因此等于 $e^{-i\beta_1 (\sigma_j^x+\sigma_k^x)}$ ，因此上式可以写成：

$U^{\dagger}_C(\gamma_1) e^{i\beta_1 (\sigma_j^x+\sigma_k^x)} H_{C,\langle jk\rangle} e^{-i\beta_1 (\sigma_j^x+\sigma_k^x)} U_C(\gamma_1)$

采用这种方法是，由于每次只有两个粒子会参与计算，而当 $p=1$ 时，仅有与 $j,k$ 直接相邻的粒子才会参加计算（ $F_p(\gamma, \beta)$ 中一项的计算），比如

QAOA的量子电路表示

前面我们已经说过，线路中的主要操作为：

$U_{B,\langle j,k\rangle}(\beta)=e^{-i\beta H_B}=e^{-i\beta (\sigma^x_j+\sigma^x_k)}$

那么我们怎么将他们用量子电路的形式进行表示呢？我们首先来看 $U_{B,\langle j,k\rangle}(\beta)$ ：

$U_{B,\langle j,k\rangle}(\beta)=e^{-i\beta H_B}=e^{-i\beta \sigma^x_j}e^{-i\beta \sigma^x_k}=R_X^{(j)}(2\beta_j) \otimes R_X^{(k)}(2\beta_k)$

这就相当与互易地对量子比特$j$和$k$执行X操作。接下来看 $U_{C,\langle j,k\rangle}(\gamma)$ ：

$U_{C,\langle j,k\rangle}(\gamma)=e^{-i\gamma H_C}=e^{-\frac{1}{2} i\gamma (I-\sigma_j^z\sigma_k^z)}= e^{- i\frac{\gamma}{2} I}e^{ i\frac{\gamma}{2} \sigma_j^z\sigma_k^z}$

其中 $e^{-u\frac{\gamma}{2}I}$ 为一个全局相位，暂时可以忽略，主要看第二项：

因此，第二项的量子电路图可以如下表示：

而对于上一节中的介绍的$p=1$的情况，即

$\langle s|U^{\dagger}_C(\gamma_1) U_B^{\dagger}(\beta_1)H_{C,\langle jk\rangle}U_B(\beta_1) U_C(\gamma_1)|s\rangle$

所对应的电路图可以如下表示：

参数优化方法

到目前为止，我们尚未介绍如何对参数进行优化，这个问题将在本节中详细给出。其实参数优化算法种类较多这里主要介绍基于梯度下降的方法。

首先我们需要知道的是，梯度下降法是在经典计算机上完成的，而我们的目标是找到参数 $(\vec{\gamma}^*, \vec{\beta}^*)$ 最大化算符的平均值：

$F_p(\gamma, \beta)=\sum\limits_{\langle jk\rangle}\langle s|U^{\dagger}_C(\gamma_1)\cdots U_B^{\dagger}(\beta_p)H_{C,\langle jk\rangle}U_B(\beta_p)\cdots U_C(\gamma_1)|s\rangle$

其中出除了参数，所有算符的具体矩阵形式都是已知的，而在理想情况下使用计算基测量得到的量子态，即为最佳的分组情况。

文献[1]中提及了在 $p$ 较小时使用BFGS来寻找局部最优解的方法，同时还提出了在 $p$ 较大时，使用启发式优化算法求解的方法。

然而作者貌似也是使用的SDK直接求解的，并且BFGS算法貌似非常复杂，因此，以后再来具体分享这一块的内容吧。

量子近似优化算法（二）

量子近似优化算法（二）

参考文献

Fixed p algorithm

QAOA的量子电路表示

参数优化方法