量子近似优化算法(二)

上次的文章 《量子近似优化算法(一)》 介绍了量子近似优化算法及其相关的概念,并留下最终的问题,即如何找到最优化的参数 $(\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_{C,\langle j,k\rangle}(\gamma)=e^{-i\gamma H_C}=e^{-\frac{1}{2} i\gamma (I-\sigma_j^z\sigma_k^z)}$

那么我们怎么将他们用量子电路的形式进行表示呢?我们首先来看$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算法貌似非常复杂,因此,以后再来具体分享这一块的内容吧。

Leave a Reply

Your email address will not be published. Required fields are marked *