Variational algorithms for linear algebra——关于论文自己的 ...

NoiseFloor · 发表于 2022-6-11 14:37

该文章选自科学通报期刊-Science Bulletin(1区 Top)，作者徐晓思，袁骁等人[1]。
变分量子算法又称为量子经典混合算法。它是通过构造含参的酉电路，和与问题的解相关的代价函数，利用量子计算机强大的计算能力评估代价函数值，然后将得到的数值传递给经典计算机，利用经典计算机无差错的计算能力来进行参数优化。由于构造的是低深度的酉电路，可在近期量子设备上实现，因此变分算法成为近期的研究热点。这方面具有奠基性工作的是2014年Alberto Peruzzo et al提出的VQE[2]和2014年Edward Farhi et al提出的QAOA[3]。
一、问题介绍
该文章求解的线性代数问题主要为线性方程组求解 $\left | v _{M^{-1} } \right \rangle=M^{-1} \left | v _{0 } \right \rangle$ 和矩阵与向量乘积 $\left | v _{M } \right \rangle = M \left | v _{0 } \right \rangle$ ,其中 $\left | v_{0}\ \right \rangle$ 是初始态向量， $\left | v _{M^{-1} } \right \rangle$ 和分别表示两个问题的解向量。为 $N\times N$ 的稀疏矩阵且是 Hermitian矩阵。注：非Hermitian矩阵可扩成Hermitian矩阵，即令 $M=\begin{bmatrix} 0& M^{\dagger } \\M &0 \end{bmatrix}$ ,具体证明参见HHL算法[4]。
二、算法细节
以下分两部分说明两个问题哈密顿量的构造过程。

矩阵向量乘积 $\left | x \right \rangle =M \left | v _{0 } \right \rangle$

问题如上，设要计算(归一化后）的解向量为 $\left | v _{M } \right \rangle = \frac{M \left | v _{0 } \right \rangle}{\left \| M \left | v _{0 } \right \rangle\right \| }$ ，可把解编码成哈密顿量 $H_{M}$ 的基态（最小本征值对应的本征态）。如下： $H_{M} =I-\frac{M\left | v_{0} \right \rangle\left \langle v_{0}\right |M^{\dagger } }{\left \| M\left | v_{0} \right \rangle \right \|^{2} }$ ,很容易验证 $H_{M}\cdot\left | v _{M } \right \rangle=（I-\left | v _{M } \right \rangle\left \langle v_{M}\right |）\left | v _{M } \right \rangle =\left | v _{M } \right \rangle-\left | v _{M } \right \rangle=0=0\cdot\left | v _{M } \right \rangle$ ,即就是最小本征值0对应的本征态。注：为稀疏且Hermitian矩阵，故是半正定矩阵，最小本征值为0。的构造思路也很好想到，即与 $I-\left | v _{M } \right \rangle\left \langle \ v _{M } \right |$ 所构成的子空间正交。
2、解线性方程 $M\left | x \right \rangle= \left | v _{0 } \right \rangle$
问题如上，设要计算(归一化后）的解向量为 $\left|v_{M^{-1}}\right\rangle=\frac{M^{-1}\left|v_{0}\right\rangle}{\| M^{-1}\left|v_{0}\right\rangle \|}$ ，同理，构造的哈密顿量为 $H_{M^{-1}}=M^{\dagger}\left(I-\left|v_{0}\right\rangle\left\langle v_{0}\right|\right) M$ ，很容易验证 $H_{M^{-1}}\cdot\left | v _{M ^{-1}} \right \rangle=0\cdot\left | v _{M ^{-1}} \right \rangle$ 。即也把解向量构造为哈密顿量的基态。
构造出哈密顿量之后，我们接着介绍怎么利用构造好的哈密顿量。

设有一个ansatz电路， $U(\vec{\theta})=U_{L}\left(\theta_{L}\right) \ldots U_{2}\left(\theta_{2}\right)U_{1}\left(\theta_{1}\right)$ ， $\vec{\theta}=\left(\theta_{1}, \theta_{2}, \ldots, \theta_{L}\right)$ ，使得 $|\phi(\vec{\theta})\rangle=U(\vec{\theta})|0\rangle$ 。则找哈密顿量的基态问题就可以转化为寻找最小能量问题 $\vec{\theta}_{\min }=\arg \min _{\vec{\theta}}\left\langle\phi(\vec{\theta})\left|H_{M}\right| \phi(\vec{\theta})\right\rangle$ ，其中 $E_{M}（\vec{\theta}）=\left\langle\phi(\vec{\theta})\left|H_{M}\right| \phi(\vec{\theta})\right\rangle$ 是能量函数，当然线性方程问题中的能量函数为 $E_{M^{-1}}（\vec{\theta}）=\left\langle\phi(\vec{\theta})\left|H_{M^{-1}}\right| \phi(\vec{\theta})\right\rangle$ 。以下只讨论一种能量函数，另一种情况类似。
这里能量函数就是该变分问题的代价函数\损失函数，构造好代价函数后，寻找哈密顿量基态的方法可以选用现有的VQE方法，优化过程是使得代价函数取最小值。
优化方法：虚时演化。构造哈密顿量的变体 $H_{M^{-1}}(t)=M(t)^{\dagger}\left(I-\left|v_{0}\right\rangle\left\langle v_{0}\right|\right) M(t)$ ，就是给哈密顿量加上时间 t ,使 $H_{M^{-1}}（t）$ 随着时间进行演化。原文是这样介绍的：（笔者不是特别理解，只能贴图了）

关于虚时演化的介绍

ansatz

酉矩阵选用Hardware- efficient ansatz，构造方法如下：

关于ansatz，作者也在支撑材料里介绍了这种Hardware- efficient ansatz的不足之处，还给出了具体矩阵求解实例，但目前为止好像也找不到更好的ansatz来实现想要的酉矩阵功能。
原文还进行了梯度分析，并在支撑材料里详细说明了代价函数及代价函数求梯度后的电路实现（Hadamard Test）,同时举例进行了数值模拟，求解了8比特64*64的线性方程问题，并在IBM量子云服务器上对一个2维的线性方程进行了算法实验实现，实验保真度高达99.5%。具体仿真结果及量子服务器实现讨论这里不再赘述，感兴趣的读者可去原文自行品读。需要说明的是，求解线性系统的同类型的文章还有很多，如Carlos Bravo-Prieto等人提出的VQLS[5](变分量子线性求解器），其它代数问题如奇异值分解[6][7]也有类似的量子算法实现。
三、创新点
将问题的解编码为哈密顿量的基态（最小本征值对应的本征态），然后应用求解哈密顿量基态的方法（例如VQE方法）来求解该问题。采用虚时演化的方法进行优化，同时提出了哈密顿量变体（Hamiltonian morphing）方法应对优化过程中容易遇到的贫瘠高原和局部最小值问题。
——笔者认为哈密顿量的构造是本文最为巧妙的地方，将问题的解刚好编码成所求哈密顿量的最小本征值0所对应的本征态，即最小能量刚好置为0。并且这种构造方法也不是很难想。梯度分析利用多元函数的分部求导法则，代价函数的电路实现通过Hadamard Test求量子态的内积电路实现。我查了一下，全文最为复杂的虚时演化优化（笔者没读懂），是作者团队之前所做的工作。总之，文章理解起来不算太难，值得一读。
四、写在后面
偶然间发现同实验室里有一位同学通过写博客CSDN来分享自己论文阅读、python学习的心得，受此启发，才意识到自己已经读了20年的书，这20多年来从社会中不断地汲取知识、养分，却对这个社会没有丝毫贡献。平常自己在生活学习过程中遇到问题就百度，查知乎等，以前也想过这个问题，为什么百度知乎上总是有自己想要的答案，为什么有人甘愿分享自己的知识和阅历呢，为名？为财？为利？恐怕都不是。
我们生活在一个知识和文明高度发达的时代，若对社会只会一昧地索取，而不有所贡献的话，岂不白来这人世间走一遭。就好像为什么有的好演员会那么高产，一年能拍出好几部影视作品。我想，互联网是有记忆的，当他们步入人生暮年，回过头来看看自己年轻时候拍过的作品，或许会别有一番滋味吧。同样，我们今天学习的牛顿力学方程，法拉第电磁感应现象，无不是伟大先贤圣人的杰作，就好像盖楼房一样，后人是在前人工作的基础上一砖一瓦才能盖起来摩天大厦。人活着，总要给世间留下点什么。当然，我只是个凡人，恐怕这一生都不可能有这么大的成就。但是作为一名搞学术研究的，若能在期刊上公开发表几篇论文，那么当自己以后在任何时间、任何地点联网下载下来自己之前的作品，回过头来再读读那些熟悉的文字，该是多么地自豪和温暖。
然而，我现在科研刚入门，对庞大的量子世界还处于懵懵懂懂地状态，没有自己（即使拿不出手）的成果或作品，只能先做一枚小小的学术搬运工，把别人优秀的成果呈现出来，希望能帮到有需要的人。因为平常用知乎比较多，所以发到知乎上了，不足之处，还请批评指正。
参考

^Xu X, Sun J, Endo S, et al. Variational algorithms for linear algebra[J]. Science Bulletin, 2021, 66(21): 2181-2188.https://www.sciencedirect.com/science/article/pii/S2095927321004631
^Peruzzo, A., McClean, J., Shadbolt, P. et al. A variational eigenvalue solver on a photonic quantum processor. Nat Commun 5, 4213 (2014). https://doi.org/10.1038/ncomms5213https://www.nature.com/articles/ncomms5213#citeas
^Farhi E, Goldstone J, Gutmann S. A quantum approximate optimization algorithm[J]. arXiv preprint arXiv:1411.4028, 2014.https://arxiv.org/abs/1411.4028
^Harrow AW, Hassidim A, Lloyd S. Quantum algorithm for linear systems of equations. Phys Rev Lett 2009;103:150502.https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.103.150502
^[1] Bravo-Prieto C , Larose R , Cerezo M , et al. Variational Quantum Linear Solver[J]. 2019.
^Bravo-Prieto C, García-Martín D, Latorre JI. Quantum singular value decomposer. Phys Rev A 2020;101:062310.
^Wang X, Song ZX, Wang Y. Variational quantum singular value decomposition. arXiv:200602336, 2020.

		自动登录	找回密码
密码			立即注册

Variational algorithms for linear algebra——关于论文自己的 ...

本帖子中包含更多资源