HHL算法学习笔记（一）

本期预告

今天起，咱们就来聊一聊上周提到的由Harrow等人提出的HHL算法，该算法在2009年发表在PRL上，带领了量子机器学习领域的真正起飞，基于HHL的机器学习算法在过去的几年中涌现出了很多论文。

• 那么这个算法究竟解决了什么问题？
• 算法的核心思想在什么地方？
• 具体的算法流程是怎样的？
• 如何更简单快速的了解这个算法呢？

本期预计用三篇文章对该算法进行解读。

今天介绍第一部分，咱们就简单聊聊前两个问题。

HHL算法解决了一个怎样的问题？就是求解线性方程的问题。线性系统是很多科学和工程领域的核心，由于HHL算法在特定条件下实现了经典算法的指数加速效果，未来能够在数据处理、机器学习、数值计算等场景具有广泛应用。

咱们先用两张图来了解下这个算法的概述。图1 给出了HHL算法的输入和输出。经典的求解线性方程的问题：输入一个n*n的矩阵A和一个n维向量b，输出n维向量x，满足Ax=b。

图1 HHL算法输入、输出

HHL这个量子算法则是有一定的限制条件的：

1. 对输入A和b的要求：首先要求n*n的矩阵A是一个Hermitian矩阵（即A的共轭转置矩阵等于它本身），其次输入b是一个单位向量。当A不是Hermitian时，作者在文中也给出了构造Hermitian矩阵的方法，关于这个技巧咱们以后讨论。算法的输入部分如图1中红色方框所标出。输入b存放在底部寄存器中，输入A作为相位估计中酉算子的一个组成部分。

2. 输出x的形式：算法的输出如图1中蓝色部分标出，依旧存放在底部寄存器中（即输出x和输入b是在同一个寄存器中）。底部寄存器存放的是一个蕴含了向量x的量子态。这里的“蕴含”的意思是我们并不能读出这个x的确切值是什么。不过我们能够得到一个关于x的整体特性，比如我们能够通过一个算子M，得到一个关于x期望值的一个评估：x’Mx。这也是HHL算法的一个局限性。然而，对于很多应用来说，也许x的确切值并不是非要提取出来，在这种情况下，HHL算法还是相当高效的。

咱们再来看看HHL算法的过程。这个过程中包含了HHL算法的一个核心思想，小编把它总结成了四个字“提取占比”。这四个字对小编的作用是什么呢？

有没有觉得它很神奇，不知道这四个字能不能给你带来同样的收获。接下来咱们就来深入看一看它究竟是什么含义？

先来简单的介绍下HHL算法的3个子过程，如图2所示。HHL算法以及很多基于它的算法都可以分为3个子过程：相位估计（phase estimation），受控旋转（controlled rotation），逆相位估计（Inverse phase estimation）。逆相位估计就是相位估计的逆运算（如果把相位估计整个子过程看做是一个矩阵$U_{PE}$，逆相位估计就可以看作是矩阵$U_{PE}$的逆）。

图2 HHL算法过程

不知道大家有没有发现，相位估计是已经有的一个量子算法，那么HHL算法的核心和神奇之处就在于中间那部分（如图中蓝色方框标出的部分）：受控旋转。它起的作用就是小编说的那四个字：“提取占比”。

我们接下来慢慢看。Hermitian矩阵A可以分解为如图2中黄色底部标出的式子。A的特征值为$\lambda_j$，特征向量为$u_j$。为了看起来更清晰，本文将 $\lambda_j$简写为 j。

经过相位估计运算之后，中间的寄存器会存储一系列的特征值 j（存储在基态|j>中），而底部寄存器存储的输入|b>会在A的特征空间上进行分解，表示为$\mid{b}\rangle= \beta_j \mid{u_j}\rangle$（接下来为了简化描述，在介绍设计思想时省略了底部寄存器，这一部分将在下篇文章中进行详细介绍）。

还记得相位估计那篇文章介绍的一个技巧么？就是相位估计的第二阶段，把存储在概率幅上的值提取到了基态上。在HHL算法的第二个阶段用到了类似的技巧（不过是反向的），即通过受控旋转操作，将基态中的值提取到了概率幅上。

在HHL算法中，受控旋转操作（蓝色方框部分）通过一个附加量子比特实现了将基态值的倒数按比例提取到了对应基态的概率幅上。

我们分步骤来解释上面这句话（借用把大象装进冰箱的三个步骤来打比方）。

第一步（打开冰箱）

设计一个关于基态|j>的函数f(j)（HHL算法中设计的是f(j)=1/j）。

【打个比方】我们把冰箱看作是量子寄存器，这里存放着一系列的基态|j>的叠加态，可以类似的理解为打开冰箱这个动作为把寄存器中的|j>“打开”，把里面的值j拿来做自变量，然后设计一个关于这个自变量j的函数f(j)。

第二步（把大象放进去）

增加一个附加量子比特，初值设为$\mid{0}\rangle$。

设计一个映射R（受控旋转操作，即图中蓝色方框部分）：将附加量子比特由基态$\mid{0}\rangle$映射到$\mid{0}\rangle$和$\mid{1}\rangle$的叠加态上，同时将函数值$f(j)$提取到了基态$\mid{1}\rangle$的概率幅上，如下所示：

$R\mid{0}\rangle=\sqrt{1-f^2(j)}\mid{0}\rangle+f(j)\mid{1}\rangle$

【打个比方】我们把附加量子比特看作是大象，大象的初值为$\mid{0}\rangle$；把“放进去”这个动作看作是受控旋转操作R。把大象放进冰箱之后，大象的状态$\mid{0}\rangle$发生了变化，变成了$\mid{0}\rangle$和$\mid{1}\rangle$的叠加态。

第三步（关上冰箱）

对附加量子比特进行测量，当测量得到1时，原来的寄存器由一系列$\mid{j}\rangle$的叠加变为$f(j)*\mid{0}\rangle$的叠加。

【打个比方】我们把“关上冰箱”这个动作看作是量子计算中对附加量子比特（大象）的测量操作。这个动作让附加量子比特（大象）发生了坍缩，状态由原来$\mid{0}\rangle$和$\mid{1}\rangle$的叠加态坍缩到了基态$\mid{1}\rangle$，整个寄存器（冰箱）由原来的一系列$\mid{j}\rangle$的叠加变成了一系列$f(j)*\mid{0}\rangle$的叠加。

经过上述三步操作后，基态$\mid{j}\rangle$中的值按照f(j)的比例被提取到了基态$\mid{j}\rangle$的概率幅上。

【划重点】今天介绍了HHL算法中的一个核心思想，小编总结为四个字：“提取占比”。可以看到，“占比”的含义就是指这个概率幅f(j)所起的作用，它描述了不同的基态|j>提取的比例f(j)不同，且这个比例由基态$\mid{j}\rangle$的值和函数f共同决定。这个功能是通过引入一个附加量子比特实现的，通过这个附加量子比特的参与，最终将基态$\mid{j}\rangle$中的值按照f(j)的比例提取到对应基态$\mid{j}\rangle$的概率幅上。

【特别注意】小编在介绍这个思想的时候做了简化，此时并没有考虑到底部寄存器（输入b），下一篇的HHL算法流程中会将其放入整体介绍。今天只介绍一个“通用”的受控旋转操作的设计思想。

根据不同的需求，我们可以基于这个思想设计不同的量子算法，其中重要的一步就是设计这个函数f的表达式。希望今天的介绍对你理解HHL算法及它的衍生算法能有所帮助。

HHL算法的提出并非表明当下的量子计算机就能够大规模的实现这样的算法。《Quantum Machine learning-what quantum computing means to data mining》一书的作者Peter Wittek曾表示，研究量子机器学习并不需要等所有条件都成熟，我们不用等到量子计算机真正面世再开展实验或理论的研究。

这也是我们致力于理论研究的意义所在。

注：作者：Duan.Bojia (QubitLab)
编辑：Zoe
校对：量豆豆

本文原创，首发在《量子机器学习》微信公众号，欢迎关注。最后感谢Zoe在量子客对本文的再次整理、校验与编辑。