如今的许多高科技都依赖于各种大数据，因此，数据库的搜索速度至关重要。量子计算机搜索数据库的速度更快，是其相对经典计算机的众多优势之一，本篇将介绍的Grover量子搜索算法便展示了这种能力。
01
搜索问题（经典和量子）
警察追踪一个男性罪犯，最后罪犯进了一个小区，逃回了家。这个小区有400个单元，每个单元住一对夫妇，因此共有400个男人。警方有逃犯的照片，在警方数据库中也有这400个人的照片。那么，如何从这400个嫌疑人中找出这个罪犯呢？这是一个搜索问题，假设数据库中的400张男性照片是完全无序的，那么，这是一个非结构化搜索问题。
Grover量子搜索算法也是用来解决这一类的搜索问题。下面是更为一般的描述：
假设给你一个很大的N个项目列表，其中有一项是我们希望找到具有独特属性的。我们把这一项称为“获胜者”，用w表示。或者用刚才那个最简单的比喻，假设我们是要在许多嫌疑人中搜索一个逃犯，w表示的就是逃犯。
考虑最简单的情况：N个嫌疑人x中只有一个罪犯w，如图1a所示。首先将列表中的每个候选者标以特定颜色，逃犯w为红色，所有其他人x都标以灰色。我们可以规定某种方法判定逃犯，例如可以采取比较照片的方法等。
或者可以考虑一个与“计算”有关的方法：假设我们知道罪犯的身份证号码w，可将它与所有嫌疑人的号码x比较，即做减法计算（x-w）。计算的结果可以用一个二元目标检验函数f(x)表示：如果x不等于w，f(x)=0；如果x是逃犯，即x= w，f(x)=1。
▲图1：搜索问题和检验函数f(x)
因为嫌疑人的数据x是无序的，如果使用经典的方法，要找到逃犯的号码w，只能一个一个地做减法。最坏情况需检查所有N个嫌疑人，最好情况也得检查1个，平均而言必须做N/2次减法。因此，经典搜索的运算次数与N的关系是线性的：O(N)。
那么现在考虑，如果是量子搜索，是否可以降低搜索运算的复杂度呢？
量子搜索的优越性是在于利用量子比特的叠加性，如图1b所示，量子计算中的“数据库”，是由量子比特可能处于的所有计算基组成的。例如如果我们有3个量子比特，计算基列表就是：|000>, |001>,……|111>，即从0到7八个值。而量子搜索与经典搜索不同之处是：量子计算可以操作这8个寄存器同时工作，如同是8个寄存器同时进行平行运算。寄存器越多，就越能体现这种平行运算“加速”的威力。
与经典计算不同的另外一点是：量子物理是概率性的，表征量子态的数值是一串概率幅。例如，一开始我们并不知道要找的逃犯w在哪里，所有的嫌疑人都有可能是罪犯。也就是说，8个寄存器给出的初始量子态是概率均等的，每个寄存器是w（逃犯）的概率辐是一样的。
我们再用刚才那个找逃犯的过程来比喻说明一下经典搜索和量子搜索的区别。
经典情况，假设数据库中的照片一次只能拿出一张，所以没有什么更好的办法，只能用逃犯的照片与其一张一张地比对。最好的情况做1次，最坏情况做400次，平均200次。
量子情况，就好比是有了一个所有照片都能放在一起的魔法大平台，这样就能将逃犯的照片同时比较数据库里所有的。不过，你也不要高兴太早了！大平台容易塌，不能随便打开，并且，虽然400张照片都在，但每张照片都有不同的亮度，每张照片以不同的概率被照亮，这个概率会根据逃犯信息的暴露程度而改变，比如说，一开始时，完全不知逃犯在哪里，因此，概率（亮度）均分在400张照片上，如果这时候打开看，全都看不清楚。
科学家们总有他们独特的办法。Grover就找到一种方法，在打开这个大平台之前，他对平台上所有的照片，反复地进行某些“运算”或“比对”操作，使得照片被照亮的概率辐变化，变化的趋势是使得越来越多的概率辐集中到数据库中对应逃犯照片的那个位置上。这样一来，最后打开平台时，就几乎只有那一个位置的照片被照亮。于是，就抓住逃犯了！
重要的是，Grover这个办法，对400张照片的情况，只需要20（400的平方根）次的比对操作，就搜索到了目标，而不是经典搜索的平均200次。这就表现出了量子算法的优越性。
02
Grover寻找量子算法
洛夫·格罗弗（Lov Grover，1961年—）是一名印度裔美国计算机科学家。他因为于1996年发明的量子算法赢得了声誉，格罗弗算法是继1994年的秀尔算法之后，为量子计算提出的第二个主要算法，2017年才终于在可扩展的物理量子系统中实现。
格罗弗于1981年获得印度理工学院德里分校的学士学位，并于1985年获得斯坦福大学电气工程博士学位。1984年，他进入贝尔实验室。1987年至1994年，他担任康奈尔大学的客座教授。他于2008年退休，成为一名独立研究员。
2001年，Lov Grover 写了一篇论文，介绍他如何提出了量子搜索算法。
格罗弗的灵感，来源于物理和数学两方面。从物理角度：无论是经典系统还是量子系统，最后都“移动”到势能最低的点，这是一个普适的物理规律。就像经典小球滚入势能较低的区域一样，在薛定谔方程下演化的均匀量子叠加态也将被引向势能较低的区域。见图2。
▲图2：格罗弗量子搜索算法
格罗弗研究了薛定谔方程无限短时间内的演化问题，还考虑了有限点集上的量子态。他试图找到一种量子算法，来有效地实现在搜索问题中量子态的演化过程。比如，图2中所示的“概率均分”态，对应的“势能”比较高，而要搜索的、标记了目标的量子态，对应的“势能”较低。因此，搜索问题就是要找出一种幺正算子的交替迭代变换方法，实施与薛定谔方程演化类似的过程，使得势能高的量子态，逐步演化到“势能”更低的量子态。最后得到势能最低的量子态，也就是目标位置具有最大概率辐的状态。这样就完成了搜索任务。
我们经常强调量子计算中是“概率辐”而不是“概率”本身，虽然是一字之差，但这却是量子计算与经典计算的一个重要区别。概率是概率辐的平方。经典物理中，叠加的是概率；而量子物理中的叠加态，是概率幅的叠加。正是基于这个特点，才能使得Grover算法搜索的复杂度从O(N)降低到O(sqrt(N))。
量子计算还有一个不可忽略的特性，就是在运算过程中，不方便对量子态进行测量，测量将引起波函数塌缩而破坏量子态。所以，一般只在最后进行测量。
总结Grover算法的中心思想是：利用量子叠加态的平行运算功能，经过数次反复迭代后，放大提高“标记”处w的概率幅而降低其它位置的概率幅，最后进行测量，波函数塌缩到概率辐最大的状态，即w态。
可以证明，Grover算法只要计算sqrt(N)次就可以找到w。听起来加速不多，仅仅是平方级的加速。但实际上是我们所能期望的搜索算法最大加速。并且当N很大时，二次加速确实可以节省大量时间。比如有100个嫌疑人，身份证号码1到100，随机无序地分布在100个寄存器中，找出某个特别数字，经典方法平均需要50次操作，量子算法只需10次！此外，该算法的用途不止于数据搜索，还可以为各种其他算法获得二次运行的时间改进。
03
Grover算法的具体步骤
▲图3：Grover算法步骤示意图
综上所述，Grover算法的核心就是振幅放大：将目标w的概率幅放大，而将其它所有“非目标项”x的概率幅缩小。整个过程如图3所示，从通过H门制备初始量子态开始，中间的迭代循环便是振幅放大，循环结束后的最后一步，是测量。
初始状态是一个均匀量子叠加态，表示所有嫌疑人是罪犯的概率相等。均匀态|s>可以很容易地从n个H门作用于n个量子比特基态|0>上构造出来。
然后就想办法让概率变化，同时对N个寄存器反复进行某种操作，使得目标项w的概率幅|w>不断放大，其他的概率幅|x>不断缩小，这个“振幅放大”过程需要重复进行直到找到w为止。
循环的振幅放大过程分为两步：量子黑箱函数U（预言机），和扩散算符操作U。
▲图4：振幅放大的几何解释
“振幅放大”算法有很好的几何解释，表示为态矢量在一个二维平面中产生旋转，如图4所示。初始状态是一个均匀叠加态|s>，|w>和|s>张成向量空间中的一个二维平面，两个向量|w>和|s>并不完全垂直，因为|w>也以N的概率辐出现在叠加态|s>中。然而，我们可以引入一个额外的状态|s‘>，它位于|w>和|s>构成的二维平面上但垂直于|w>。
初始状态如图4左图所示。在|w>和|s‘>构成的平面坐标下，初始状态|s>可以表示为：
|s> = sinT |w> + cosT |s‘>,
角T = arcsin(s在w的投影) = arcsin(1/ N)，图4左下图形是均匀叠加态|s>的bar图。
迭代中的两步：
步骤1，应用黑箱函数U将状态|s>翻转，见图4的中图：U的作用是将目标状态|w>反相，其它状态不变。从几何上讲，这对应于|s>态关于|s‘>轴的翻转。这意味着状态|s>中|w>的幅度变为负值，也意味着平均幅度（由虚线表示）的降低。
步骤2，现在关于状态|s>应用另一个扩散算符U。此转换将|s>映射到状态UU|s>。两次反射U和U对应一个旋转，将初始状态|s>旋转得更接近|w>，见图4右图。
幅度条形图中U的反射操作可以理解为关于平均幅度（虚线）的反射。由于第一次反射降低了平均振幅，这变换将|w>的振幅提高到其原值的数倍，同时也降低了其他振幅，故称为振幅放大。
然后重复步骤1和步骤2，继续振幅放大的过程直到达到要求。
图4所示的过程的确可将振幅放大，但到此为止我们有两个问题：一是图中的黑箱函数U和扩散算符U具体是什么？二是此过程要重复几次才能找到w呢？
Grover算法的预言机Oracle函数U所做的，是给解|w>添加了一个负相位，也就是说，对于计算基中的任何状态|x>，可以创建一个函数U：U (x) = x，如果|x>不等于|w>；而U(x) = -x，如果|x>等于|w>，如图5a所示。该函数被称为Oracle。
▲图5：a）黑箱函数将w反相；b）相位黑箱函数
图5a中，黑箱函数U可以表达为一个对角矩阵，其中对应于目标项w的值为-1，其它为1。图5a下图表示三个量子位的U矩阵。进一步具体而言，Oracle可以用图5b中所示的经典检验函数f(x)构成的相位函数来实现。
也许有人会说，既然U可以将w那一项反相，不是已经知道了w的位置吗？那还搜索什么呢？这是初学Grover算法时经常感觉困惑的问题。这儿需要再次强调量子计算的特点：可以让多个寄存器同时运算但不能检查每个寄存器的结果。因此，虽然我们说U能够将w反号，但因为没有进行测量，我们并不知道是哪个寄存器的结果反相了。反相的结果是每个寄存器根据它自己内部的数据检验函数f(x)而反馈回来的。
说通俗点：每个嫌疑人自己知道他是不是罪犯，但我们并不知道，除非进行测量！
即使进行测量，仅仅是将|w>反号这一个操作，也不能确定w的位置。因为|w>是概率辐，而测量得到的是概率，即概率辐的平方。|w>符号的改变使概率辐反相，但并不会影响概率。Grover算法巧妙之处是在步骤3中我们又应用了一个扩散函数U = 2 |s><s|-1。其作用是将态矢量关于平均幅度进行反射，反射后w的概率幅被放大了。因此，步骤2和3的共同作用U=UU，使得测量后塌缩到|w>的概率被放大了。
那么，现在回到第二个问题：此过程U要重复多少次才能使w的概率幅达到最大值呢？
每一步过程U，都使态矢量的位置更接近|w>的位置，假设每次改变的角度是均匀的2θ，对初始态|s>作用t次之后：|ψ>= (UU)|s>。最后需要的次数可用图6的描述来粗略地理解。
▲图6：Grover算法
事实也证明旋转N^1/2次就足够了。能从经典的N次减到N^1/2次，原因是由于处理的是概率辐而不是概率，即被放大的是概率幅而不仅是概率，这也是量子计算秘诀所在。
参考资料：
【1】Grover L.K.: A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
【2】From Schrödinger's Equation to the Quantum Search Algorithm, Lov K. Grover (Bell Labs, Murray Hill, NJ), https://arxiv.org/abs/quant-ph/0109116
来源：墨子沙龙
原标题：量子计算机能更快地找出罪犯吗？｜量子计算群英会（十）
编辑：virens