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中制备归一化的初态，得到
- 相位估计，C存储相位，得到
其中Hermitian矩阵，向量
，特征值的估计值
。
- 使用C作为控制比特，在S上旋转，得到特征值的倒数，即
- 相位估计逆变换，解耦C和I，使得C变到全0态
- 测量寄存器S，塌缩到1时，忽略S和C，只观察I的态，有
在整个过程中，用到了相位估计，而相位估计思想又起源于量子傅里叶变换，因此我们下面介绍QFT后再介绍QPE，最后回到HHL算法中参数的选择。
QFT
首先看一下经典的离散傅里叶变换：
对应关系为：
量子傅里叶变换的表达式也是如此，现在我们考察作用在正交基上，得到的结果：
为了方便构造量子线路，实现量子傅里叶变换，我们需要把表达式化简分解，最好可以写成量子比特张量积的形式：
- 把k展开成二进制的形式，即
.
- 指数相加变成相乘，把
分配到每一个量子比特
- 对每一个量子比特，把求和具体的写出来，再结合
，把
表达成小数形式
至此，就可以根据末态，构造量子线路了。用如下的量子线路可以得到量子比特顺序相反的末态，再作用SWAP门即可。
QPE
量子傅里叶变换最重要的就是展开形式的等式。总体来说，QFT把基态转化到了相位中。而相位估计问题，则是想获得相位，因此我们可以构造合适的初态，利用量子傅里叶逆变换，把相位转化到基态中，从而可以测量得到。
对于一个酉矩阵U，它的特征值模长为1，所以特征值可以表达为，其中
。我们的任务是估计
。如果可以通过线路，构造出QFT中张量积的形式，则利用量子傅里叶逆变换，就可以得到相位的二进制表示。如下的线路正好可以实现：
经过如上线路，得到的态为：
对比发现，正好满足QFT的形式，因此只需要执行逆变换，即可测量第一个寄存器，得到相位。
HHL算法进一步想法
看到的教程中，对于t和C的选择不是很明确，因此对这两个问题进行了思考，并总结自己的一部分想法。这是初步的想法，不一定正确，如有错误或疑问，欢迎交流。
- HHL算法中需要用到QPE，但QPE用到的是酉矩阵，而HHL给定的是Hermitian矩阵。注意当A是Hermitian时，矩阵
一定是酉矩阵，且二者的特征向量相同，当A的特征值为
时，U的特征值为
。这样，在QPE中使用U，可以使A的特征值出现在指数的位置，从而可以使用QPE恢复。
- 关于上述t的选择，以下纯属个人见解，如有不当，请各位指出。特征值
。取
时，
使指数部分成为周期函数，分母
将
，因为是周期的，也可以看作是
的。记
。
- QPE之后，得到表达式为
二进制
第一位代表了不同的符号，当第一位是1时，其实为负值，需要在本身的基础上减去1得到真实的
- 在控制旋转部分，根据寄存器C中的值，确定带符号的
前的系数为
，需要选择适当的C，既符合三角函数要求，又要在后处理中更加方便。取
，则
，既小于1，又出现了真正的
- 回到HHL算法的末态，把上述的t,C带入，则有
如果向量b还有归一化系数，则再相乘即可。
