背景介绍

2009年10月，发表在顶级物理学期刊《PhysicalReview Letters》的文章“Quantum algorithm for linear systems of equations”带领了量子机器学习领域的真正起飞。该算法由Bristol大学的Aram W. Harrow和MIT的Avinatan Hassidim以及Seth Lloyd三人共同发明，被称之为HHL算法。（从算法的命名上我们也可以看到它的重要性，比如Shor在1994年发明的Shor因子分解算法以及Grover在1996年发明的Grover量子搜索算法均以作者姓氏命名。）

今天小编来跟大家聊一聊，这个重要的算法的核心部件之一：Phase Estimation，中文翻译：相位估计，简称PE算法。这个算法在很早就已经被提出了，然而真正带来很大影响的，就是基于它实现的HHL算法，以及各种搭着HHL顺风车实现的量子机器学习算法。

希望本文能带给你如下收获

1. 相位估计的神奇之处是什么？它是如何实现的？

2. 我们在设计量子算法时，能从相位估计算法中得到什么启发？

文章大纲

本文将用最简单的5W2H工具中的3W1H开始，简单的来看一看，这个相位估计有什么神奇的地方？它的算法是个什么样子？怎么实现它的神奇？又用在哪个地方呢？（哈哈，答案已经在图1中啦）不过今天主要只解决两个问题：Why和What。关于QFT和HHL算法，将在后续专题中慢慢展开。

图1 相位估计简介

神奇之处

相位估计最神奇的效果是达到了相比传统计算机上运行的算法的一个指数加速。这个效果怎么理解，举个简单的例子，就是传统计算机上要运行$2^{30}$（约等于10亿）次运算，量子计算机上只要运行30次左右就OK了。当然这个指数加速效果是有前提条件的，就是输入和输出都需要是量子比特，而量子比特怎么和经典比特对应起来呢，这又是另外一个问题了，本期先不讨论。我们只要知道，在算法的运算过程中，是有一个指数加速的效果就可以了。而这个算法凭借它的优势，可以用在很多应用上，比如求阶问题，因子分解问题，还有我们领域的老大算法HHL，等等，如图2所示。

【划重点】相位估计能够达到指数加速，且是很多量子算法的关键。

图2 相位估计的优势和应用

算法思路

你有没有好奇这个算法究竟是什么样子呢？也许在数学公式表达上很复杂，但如果你往下看，你会发现它就是简单的一个盒子。在这个盒子中，有两个重要的子模块（subroutine module），这两个模块通过图3中蓝色方框标出，我们后面再细讲。现在先看橙色标注的部分，这两个部分可以看作是两个黑箱，也是phase estimation在设计时需要重点考虑的地方。橙色是算法的主要输入部分：橙色圆圈标注的是输入中的一个量子态（可以简单的理解为线性代数中的向量），橙色方块标注的是输入中的一个酉算子（可以简单的理解为一个矩阵）。

【划重点】相位估计算法本身关注的是蓝色部分（算法过程）；而橙色部分（算法输入）是在设计相应的量子算法时需要重点考虑的部分。

图3 相位估计算法输入与过程

那图中的叉和勾代表什么呢？在本文中，我们暂不考虑橙色输入部分是怎么得到的，只考虑蓝色的两个子过程都是怎样的。哈哈，机智的你还发现了一个问号吧。是的，说了半天，相位估计算法输出的是什么呢？假设酉算子$U$具有一个特征值为$e^{2 i \pi \phi}$的特征向量$|u \rangle$，而$\phi$是未知的，相位估计算法的目的就是估计这个未知的$\phi$。这么描述有点学术了，借用马同学（公众号：matongxue314）在知乎上的一个解释（https://www.zhihu.com/question/21874816），如果把矩阵看作是运动，特征值就是运动的速度，特征向量就是运动的方向；那么相位估计就是去估计这个速度。我们借助图4来看一看，相位估计是怎么实现的。

图4 相位估计的两个阶段

相位估计主要包括两个阶段，图4中的右上角所示的是整个算法的一个缩略图，箭头指向的左边和下方的绿色方框围住的线路分别代表了算法的两个阶段。第一阶段执行的操作实现的功能类似特征值分解。一共有两个寄存器，第二个寄存器输入的是酉算子U的特征向量（也就是运动方向），通过第一阶段的执行后，会把酉算子的特征值（也就是运动速度）存储在第一寄存器中，但是注意，这时候的相位还在量子态的概率幅中藏着（之所以说是藏着是因为我们通常能够得到的是量子态的基态，而不是概率幅）。然后就是神奇的第二阶段，通过量子傅里叶变换QFT的逆运算（超级厉害的算法，以后开个专题慢慢聊），可以把藏在概率幅里的存储到量子态的基态中。这样我们就有办法通过测量来读取这个$\phi$啦。（这里简单的介绍下：量子态的数学表达可以看作是：量子态=概率幅1*基态1+概率幅2*基态2+…+概率幅n*基态n。基态是可以通过测量得到的，而概率幅很难直接得到，因而有了上面的提取思路，即通过QFT的逆运算把概率幅值提取到了基态中。）

【划重点】相位估计通过两个阶段实现，第一阶段提取了目标酉算子的特征值放到了量子态的概率幅中，第二阶段提取了概率幅中的相位放到了量子态的基态中。最终输出的就是估计的相位，由这个相位就可以进一步求出输入矩阵的特征值（就是运动速度）。

【重点中的重点】通过设计算法将基态中的值提取到概率幅中，或设计算法将概率幅的值存储在基态中是经常会用到或碰到的“小技巧”。大家在设计量子算法时，也可以考虑巧妙的使用它。