HHL算法 Quantum Algorithm for Line

作者: richybai | 来源:发表于2023-04-20 14:28 被阅读0次

Harrow A W, Hassidim A, Lloyd S. Quantum algorithm for linear systems of equations[J]. Physical review letters, 2009, 103(15): 150502.

论文导读

最近参加本源量子比赛初赛，最后一个题是求解一个线性方程组。之前对HHL算法一知半解，借此机会重温HHL算法。本文简要介绍HHL算法，并对其中用到的量子相位估计，量子傅里叶变换进行解释。求解的复杂度与矩阵的规模N，条件数k，以及行稀疏程度s，精度e有关。算法求解Ax=b，要求A是Hermitian，b是单位向量。关于实验中参数t和C的选择，是个人的一些想法，如有错误，请大家指正。

HHL算法流程

在register I中制备归一化的初态，得到
$|0\rangle \otimes |0\rangle \otimes |b\rangle$
相位估计，C存储相位，得到
$|0\rangle \otimes \sum_k \beta_k |\tilde \lambda_k\rangle \otimes |u_k\rangle,$
其中Hermitian矩阵 $A = \sum_k \lambda_k |u_k\rangle \langle u_k|$ ，向量 $|b\rangle = \sum_k \beta_k |u_k\rangle$ ，特征值的估计值 $\tilde \lambda_k$ 。
使用C作为控制比特，在S上旋转，得到特征值的倒数，即
$\sum_k \beta_k (\sqrt{1-\frac{C^2}{\tilde \lambda_k^2}}|0\rangle + \frac{C}{\tilde \lambda_k}|1\rangle) \otimes |\tilde \lambda_k\rangle \otimes |u_k\rangle$
相位估计逆变换，解耦C和I，使得C变到全0态
$\sum_k \beta_k (\sqrt{1-\frac{C^2}{\tilde \lambda_k^2}}|0\rangle + \frac{C}{\tilde \lambda_k}|1\rangle) \otimes |0\rangle \otimes |u_k\rangle$
测量寄存器S，塌缩到1时，忽略S和C，只观察I的态，有
$\sum_k \beta_k \frac{C}{\tilde \lambda_k}|u_k\rangle = A^{-1}|b\rangle.$

在整个过程中，用到了相位估计，而相位估计思想又起源于量子傅里叶变换，因此我们下面介绍QFT后再介绍QPE，最后回到HHL算法中参数的选择。

QFT

首先看一下经典的离散傅里叶变换：
$\text{input: } x = [x_0, x_1, \cdots, x_{N-1}]\text{, output: } y = [y_0, y_1, \cdots, y_{N-1}]$
对应关系为：

离散傅里叶变换表达式

量子傅里叶变换的表达式也是如此，现在我们考察作用在正交基上，得到的结果：

量子傅里叶变换

为了方便构造量子线路，实现量子傅里叶变换，我们需要把表达式化简分解，最好可以写成量子比特张量积的形式：

张量积形式计算过程

把k展开成二进制的形式，即 $|k\rangle = |k_1k_2 \cdots k_n\rangle, k = k_12^{n-1} + k_22^{n-2}+\cdots+k_n2^0$ .
指数相加变成相乘，把 $k_i$ 分配到每一个量子比特
对每一个量子比特，把求和具体的写出来，再结合 $j2^{-l}$ ，把 $j$ 表达成小数形式

至此，就可以根据末态，构造量子线路了。用如下的量子线路可以得到量子比特顺序相反的末态，再作用SWAP门即可。

QFT线路（除去SWAP部分）

QPE

量子傅里叶变换最重要的就是展开形式的等式。总体来说，QFT把基态转化到了相位中。而相位估计问题，则是想获得相位，因此我们可以构造合适的初态，利用量子傅里叶逆变换，把相位转化到基态中，从而可以测量得到。
对于一个酉矩阵U，它的特征值模长为1，所以特征值可以表达为 $e^{i2\pi \varphi}$ ，其中 $\varphi\in[0, 1)$ 。我们的任务是估计 $\varphi$ 。如果可以通过线路，构造出QFT中张量积的形式，则利用量子傅里叶逆变换，就可以得到相位的二进制表示。如下的线路正好可以实现：

相位估计第一阶段

经过如上线路，得到的态为：

第一个寄存器上的末态

对比发现，正好满足QFT的形式，因此只需要执行逆变换，即可测量第一个寄存器，得到相位。

HHL算法进一步想法

看到的教程中，对于t和C的选择不是很明确，因此对这两个问题进行了思考，并总结自己的一部分想法。这是初步的想法，不一定正确，如有错误或疑问，欢迎交流。

HHL算法中需要用到QPE，但QPE用到的是酉矩阵，而HHL给定的是Hermitian矩阵。注意当A是Hermitian时，矩阵 $U=e^{iAt}$ 一定是酉矩阵，且二者的特征向量相同，当A的特征值为 $\lambda$ 时，U的特征值为 $e^{i\lambda t}$ 。这样，在QPE中使用U，可以使A的特征值出现在指数的位置，从而可以使用QPE恢复。
关于上述t的选择，以下纯属个人见解，如有不当，请各位指出。特征值 $\lambda$ 的取值范围可能超出[0,1)范围，因此需要适当的选取t，使得缩放后的 $\tilde \lambda\in [0, 1)$ 。取 $t = \frac{2\pi}{2|\lambda|_{max}}$ 时， $2\pi$ 使指数部分成为周期函数，分母 $2|\lambda|_{max}$ 将 $\lambda$ 缩放到 $[-0.5, 0.5)$ ，因为是周期的，也可以看作是 $[0, 1)$ 的。记 $\tilde \lambda = \frac{\lambda}{2|\lambda|_{max}}$ 。
QPE之后，得到表达式为 $|0\rangle \otimes \sum_k \beta_k |\tilde \lambda_k\rangle \otimes |u_k\rangle,$ 二进制 $\tilde \lambda$ 第一位代表了不同的符号，当第一位是1时，其实为负值，需要在本身的基础上减去1得到真实的 $\tilde \lambda$ 。
在控制旋转部分，根据寄存器C中的值，确定带符号的 $\tilde \lambda$ 。因为要旋转使得 $|1\rangle$ 前的系数为 $\frac{C}{\tilde \lambda}$ ，需要选择适当的C，既符合三角函数要求，又要在后处理中更加方便。取 $C=\frac{|\lambda|_{min}}{2|\lambda|_{max}}$ ，则 $\frac{C}{\tilde \lambda} = \frac{|\lambda|_{min}}{2|\lambda|_{max}} \frac{2|\lambda|_{max}}{\lambda} = \frac{|\lambda|_{min}}{\lambda}$ ，既小于1，又出现了真正的 $\lambda$ 。
回到HHL算法的末态，把上述的t,C带入，则有
$\sum_k \beta_k \frac{C}{\tilde \lambda_k}|u_k\rangle = \sum_k \beta_k \frac{|\lambda|_{min}}{\lambda_k}|u_k\rangle = |\lambda|_{min}A^{-1}|b\rangle$
如果向量b还有归一化系数，则再相乘即可。

HHL算法 Quantum Algorithm for Line

论文导读

HHL算法流程

QFT

QPE

HHL算法进一步想法

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读