量子计算（二十二）：Grover算法

​Grover算法

一、什么是搜索算法

举一个简单的例子，在下班的高峰期，要从公司回到家里，开车走怎样的路线才能够耗时最短呢？最简单的想法，当然是把所有可能的路线一次一次的计算，根据路况计算每条路线所消耗的时间，最终可以得到用时最短的路线，即为最决路线，这样依次的将每一种路线计算出来，最终对比得到最短路线。搜索的速度与总路线数N相关，记为O(N)，而采用量子搜索算法，则可以以O(sqrt(N))的速度进行搜索，要远快于传统的搜索算法。

二、怎么实现Grover搜索算法

首先，先化简一下搜索模型，将所有数据存在数据库中，假设有n个量子比特，用来记录数据库中的每一个数据的索引，一共可以表示2个数据，记为N个；希望搜索得到的数据有M个，为了表示一个数据是否是搜索的结果，建立一个函数：

其中x0为搜索目标的索引值，也即是说，当搜索到目标时，函数值f(x）值为1，如果搜索的结果不是目标时，f(x)值为0。

假设有一个量子Oracle可以识别搜索问题的解，是别的结果通过Oracle的一个量子比特给出。可以将Oracle定义为：

Oracle对量子态的具体操作是什么样的呢？同D-J算法相似，先将初态制备在

态上，

​编辑为查询寄存器，|1〉为结果寄存器。经过Hardmard门操作后，可以将查询寄存器的量子态，变为所有结果的叠加态；也就是说，经过了Hardmard 门，就可以得到所有结果的索引，而结果寄存器则变为

，再使其通过Oracle，可以对每一个索引都进行一次检验，如果是目标结果，则将答案寄存器的量子态进行0、1翻转，即答案寄存器变为：

其中，|x〉是查询寄存器的等额叠加态中的一种情况。

如上述所知，Oracle的作用，是通过改变了解的相位，标记了搜索问题的解。

现在，将搜索问题的解通过相位标记区分出来，那么如何能够将量子态的未态变已标记出的态呢？

将问题换一种思路进行考虑，当查询寄存器由初态经过Hardmard门后，会变为所有可能情况的等额善加态；也就是说，它包含着所有搜索问题的解与非搜索问题的解。可以将这个态记为：

将所有非搜索问题的解定义为一个量子态|α〉，其中

代表着x上所有非搜索问题的解的和，记为：

显然，|β〉为最终的量子态，而且|α〉和|β〉相互正交。利用简单的代数运算，就可以将初态|ψ〉重新表示为：

初始态被搜索问题的解的集合和非搜索问题的解的集合重新定义，也即是说，初态属于|α〉与|β〉张成的空间。因此，可以用平面向量来表示这三个量子态，如下图所示：

那么，Oracle作用在新的表示方法下的初态会产生怎样的影响呢？Oracle的作用是用负号标记搜索问题的解，所以，相当于将|β〉内每一个态前均增加一个负号，将所有的负号提取出来，可以得到：

对应在平面向量中，相当于将|ψ〉做关于|α〉轴的对称，但仅有这一种操作是无法将量子态从|ψ〉变为|β〉，还需要另一种对称操作。

第二种对称操作，是将量子态关于|ψ〉对称的操作，这个操作由三个部分构成：

1. 将量子态经过一个Hardmard门；
2. 对量子态进行一个相位变换，将

态的系数保持不变，将其他的量子态的系数增加一个负号，相当于

西变换算子；

1. 再经过一个Hardmard门。

这三步操作的数学表述为：

上述过程涉及到复杂的量子力学知识，这三部分的操作，只是为了实现将量子态关于|ψ〉对称。如果想了解为什么这三步操作可以实现，可以阅读关于量子计算相关书籍进一步理解。

前面介绍的两种对称操作，合在一起称为一次Grover迭代。假设初态|ψ〉与|α〉可以表示为：

很容易得到：

可以从几何图像上看到，每一次Grover选代，可以使量子态逆时针旋转，经历了k次Grover送代，末态的量子态为：

因此，经过多次选代操作，总可以使末态在|β〉态上概率很大，满足精确度的要求。经过严格的数学推导，可证明，选代的次数R满足：

参考路线图：