目前关于QSVT的介绍共这四期。后续如果有更多关于这方面的研究,可能会追加关于该算法的介绍。为了保证系统性,咱们先来看一下前期回顾。

前期回顾

本期导读

量子奇异值阈值算法QSVT(三)中,我们遗留了一个问题,就是在controll-rotation操作中引入了的参数$\alpha$该如何取值呢?本期咱们就针对这个问题采用2W1H方法进行解读:

  1. Why:为什么引入$\alpha$?
  2. What:$\alpha$的计算依据是什么?
  3. How:如何计算$\alpha$?

参数$\alpha$的解读

本节就针对这个神秘的$\alpha$进行解读。

Why:为什么引入$\alpha$?

【背景】在学习HHL算法时,研读了一些关于HHL算法的实验实现。下面给出这些算法的线路截图及参考来源:

量子奇异值阈值算法QSVT(四)-量子客

参考文献:

  • [1] Y. Cao, A. Daskin, S. Frankel, and S. Kais,Quantum circuits for solving linear systems of equations. Molecular Physics 110, 1675 (2012).
量子奇异值阈值算法QSVT(四)-量子客
参考文献:

  • [2] J. Pan, Y. Cao, X. Yao, Z. Li, C. Ju, H. Chen, X. Peng, S. Kais, and J. Du,Experimental realization of quantum algorithm for solving linear systems of equations. Phys. Rev. A, 89, 022313 (2014).
量子奇异值阈值算法QSVT(四)-量子客
参考文献:

  • [3] X. Cai, C. Weedbrook, Z. Su, M. Chen, M. Gu, M. Zhu, L. Li, N. Liu, C. Lu, and J. Pan, Experimental quantum computing to solve systems of linear equations. Phys. Rev. Lett. 110, 230501 (2013).

上述三个实例中,有一个共同点,即在controlled-rotation操作中,都采用了Pauli-Y操作实现的,其矩阵表示为:

$R_y(\theta)={\cos(\theta/2)\qquad-\sin(\theta/2)\choose \sin(\theta/2)\qquad\cos(\theta/2)}$

在Pauli-Y中涉及的旋转角度$\theta$在实验中被设置为型如$\frac{2\pi}{2^r}$的式子,其中r为整数。在实验结果分析时,会观察r的不同取值对输出值的保真度和实验成功概率的影响。

关于这一点,通常在设计时,会有一种说法:即$\alpha$值越小,$\sin(\theta)$越接近于$\theta$值,因此输出值的保真度越高;但同时由于$\sin(\theta)$值很小,因此一次实验成功的概率就会比较低[1]。通常在取r值时,会选择一个保真度尽可能高时,成功概率也较大的值。

关于这个$\theta$值的计算,在参考文献[4]的附录中有给出相关算法,大家感兴趣可以查阅。

[4] Iris Cong and Luming Duan,Quantum discriminant analysis for dimensionality reduction and classification. New J. Phys. 18 073011, 2016.

那么问题来了,$\theta$为什么一定要是$\frac{2\pi}{2^r}$这样的表达式呢?是实验的限制么?为什么一定要满足$\sin(\theta)$接近于$\theta$这个条件呢?如果抛开上述限制,有没有可能使保真度和概率同时取很高的值呢?

我把这个想法带入了QSVT中,进行了试验,发现当不考虑上述限制时,能够使输出值的保真度和实验成功概率都比较大。这是一个有趣的现象。在这里,为了区别上述的$\theta$,我引入了一个参数$\alpha$。

What:$\alpha$的计算依据是什么?

回忆一下,“$\sin(\theta)$接近于$\theta$”是为了满足用Pauli-Y实现的旋转操作之后得到量子系统中各个基态的概率幅与理论值均接近。假设线路输出的向量为a=[a1,...,ai,....],理论输出的向量为b=[b1,...bi,...],“$\sin(\theta)$接近于$\theta$”这个条件下满足的是对于任意i,有$a_i$接近于$b_i$。

但我们关注的输出值的保真度由$\langle{a}\mid{b}\rangle=\sum(a_i{b_i})$决定。因此可以理解“$\sin(\theta)$接近于$\theta$”是保证输出值保真度高的充分而非必要条件

因此,计算$\alpha$的值和前面研究中计算$\theta$值的依据不同,即$\alpha$的值要保证$\langle{a}\mid{b}\rangle$的值大,同时算法成功的概率也高。

下面考虑$\alpha$的表达式,设$R_y$线路输入为:

$\theta=0.\theta_1\cdots\theta_d=\sum\nolimits_{j=1}^d\theta_j\cdot2^{-j},(\theta_j\in\{0,1\})$

则$R_y$表示为$\alpha$的函数:

$R_y(2\alpha\theta)=e^{-i\alpha\theta Y}=\prod\limits_{j=1}^{d}e^{-i\alpha\theta Y/{2j}}=\prod\limits_{j=1}^{d}R_y^{\theta_j}(2^{1-j}\alpha)\\=R_y^{\theta_1}(\alpha)R_y^{\theta_2}(\alpha)\cdots R_y^{\theta_d}(\alpha/{2^{d-1}})$

因此,$R_y$的线路设计可以表示为:

量子奇异值阈值算法QSVT(四)-量子客

根据上述$\alpha$的表示可以让我们很容易的计算出算法成功的概率

$P(\alpha)=\frac{N_{\alpha}}{N_1}=\frac{\sum\limits_{k=1}^{r}\sigma_k^2\sin^2(y_k\alpha)}{\sum\limits_{k=1}^{r}\sigma_k^2}$

以及输出值的保真度

$F(\alpha)=\langle\psi_{\hat{S}}\mid\psi_S\rangle=\frac{1}{aqrt{N_2 N_{\alpha}}}\sum\nolimits_{k=1}^{r}\sigma_k^2y_k\sin(y_k\sigma)\\=\frac{\sum\limits_{k=1}^{r}\sigma_k^2y_k\sin(y_k\alpha)}{\sqrt{\sum\nolimits_{k=1}{r}\sigma_k^2y_k^2\times\sum\nolimits_{k=1}^r\sigma_k^2\sin^2(y_k\alpha)}}$

因此,$\alpha$的计算依据可以表示为:求$\alpha$,使$P(\alpha),F(\alpha)$的取值都比较大。

更具体的描述可以参考文献[5]。

How:如何计算$\alpha$?

我们最后简单的讨论下如何计算$\alpha$。

观察$P(\alpha)$和$F(\alpha)$的式子,我们发现求解P(alpha)的极值要相对容易一些,但求$F(\alpha)$就相对复杂了些(分母表达式复杂且包含变量$\alpha$)。

回忆我们的目标是:求解$\alpha$,使$P(\alpha)$和$F(\alpha)$的取值都比较大。这时候我们可以考虑引入一个新的目标函数G:

$G(\alpha)=\sqrt{P(\alpha)}\times F(\alpha)=\sqrt{\frac{N_{\alpha}}{N_1}}\times\frac{1}{\sqrt{N_2N_{\alpha}}}\sum\nolimits_{k=1}^{r}\sigma_k^2y_k\sin(y_k\alpha)\\=\frac{\sum\nolimits_{k=1}{r}\sigma_k^2y_k\sin(y_k\sigma)}{\sqrt{\sum\nolimits_{k=1}{r}\sigma_k^2\times\sum\nolimits_{k=1}{r}\sigma_k^2y_k^2}}$

G的引入使得在目标函数的分母中消去了变量$\alpha$,而使求解问题变得简单。因而最终的求解问题变成了:

$\arg_{\alpha}\max G(\alpha)$

该问题可以通过求导计算:

$G^{`}(\alpha)=\frac{\sum\nolimits_{k=1}^{r}\sigma_k^2y_k\cos(y_k\sigma)}{\sqrt{\sum\nolimits_{k=1}^{r}\sigma_k^2\times\sum\nolimits_{k=1}{r}\sigma_k^2y_k^2}}=0$

关于具体的求解过程小编这里就不多说啦。有兴趣的小伙伴可以参考文献[5]。文中列举了一些求解方法。

小结

本文针对QSVT线路中controlled-rotation模块中$R_y$的设计,给出了一些自己的想法。如果大家针对这个问题有更好的想法,欢迎留言交流~

参考文献:

  • [5] Bojia Duan, Jiabin Yuan, Ying Liu and Dan Li. Efficient quantum circuit for singular value thresholding. arXiv:1711.08896. (2017)
注:作者:Duan.Bojia (QubitLab)
编辑:Zoe
校对:量豆豆
本文原创,首发在《量子机器学习》微信公众号,欢迎关注。最后感谢Zoe在量子客对本文的再次整理、校验与编辑。

量子奇异值阈值算法QSVT(四)-量子客