假设你有一个包含很多城市的地图，并且希望找出找出一条经过所有城市的最短线路。假设存在N种可能的路线，若采用遍历的搜索算法，在经典计算机上时间复杂度为 ，若采用量子搜索算法（Quantum Search Algorithm，或者称为Grover算法），则时间复杂度仅为 。此外，量子搜索算法是一种通用算法，它还可以加速除路径搜索外的许多别的启发式的经典算法。

1.1 量子搜索算法

1.1.1 操作O

假设搜索空间有N个元素，为方便起见，我们假设 ，且有M个解。我们将问题描述为：如果第x个元素是问题的解，则 ，否则 。

按照我们上一篇的讨论，存在一个操作O，使得 。

可以看出，当f(x)=1时，比特|q>发生翻转，否则保持不变，我们把|q>称为信息比特。此时我们可以通过对|x>|0>执行操作O并观测第信息比特是否翻转成|1>来检测x是不是问题的解。

和Deutsch–Jozsa算法中的操作一样，我们把|q>设置为 ，则如果x不是问题的解，状态保持不变，否则信息比特发生翻转变为 。写成公式为：

注意到信息比特不发生变化，即状态 在整个计算中不发生变化，因此我们省略对它的描述。现在我们表示为：

也就是说，操作O通过翻转相位来标记x是否为问题的解。

1.1.2 算法流程

下图是算法的流程：

初态为 ，其中Oracle workspace是执行操作O时需要的辅助空间。根据笔记（8）的推导，在对初态的 执行 后我们得到 ，其中求和是对所有可能的态|x>。由于 ，我们也可以把状态写为 。

接下来，算法将执行若干个Grover迭代或者称为Grover操作，记为G。

关于G，如下图，我们可以将其拆解成四个部分：

1. 执行操作O
   
   
2. 应用H门
   
3. 执行条件相位操作，对除了态|0>以外的所有计算基执行-1的相位翻转。即：
   。
   
4. 应用H门
   

注意，两次H门，复杂度为O(n)，相位翻转复杂度也为O(n)，操作O所需我们暂且不讨论，只需要记住每次Grover迭代会执行一次操作O。

考虑到：

，x不等于|0>时。

上式成立是因为，计算基是彼此正交且归一的，因此 。

明白了上面两式，我们可以把234三步写为

，令 ，

则 ，于是

再考虑G中的O，我们可以把G表示为 。

1.1.3 Grover迭代的作用与几何表示

我们现在记 为对所有问题的解的x的求和， 为所有不是问题的解的x的求和。

定义状态：

其中M为问题的解的数量。

易知：

因此可以把系统初态视为由 和 张成空间中的向量，我们把这个空间称为A空间（或者A平面）。并且由于计算基的正交性，这两个向量也正交。

于是我们可以将 表示为：

其中：

在此基础上我们讨论G的作用：

首先：操作O会使得解的相位翻转，即 。可以理解为A平面中的关于轴的映射。

同样的， 作用于向量上，会使得该向量相对于 反正翻转。

在这里我们设：

，

则

故:

又：

故：

由于：

系数相除得到角度的tan值：

根据倍角公式可以计算出，若:

则

于是我们可以知道，经过 处理后，我们得到的向量的角度为原来角度的三倍，即：

下图给出来上面我们公式推导的结果：

也就是说，每一次Grover迭代实现了一次旋转，我们也可以用矩阵表示G：

1.1.4 算法性能

由于初态为：

其旋转 后得到

因此需要执行的Grover迭代次数为

其中 ，是求出最靠近x的整数。

旋转之后，系统状态距离 最多 ，由于 是问题的解的态的和，此时我们对系统的状态进行观察，将至少有1/2的概率获得问题的解。

当 时， ，

此时，出错的概率至多为 。

由于：

，

有

因此，算法的时间复杂度为O(N/M)的操作O调用。

1.1.5 算法描述

当M=1时，算法的描述如下：

需要注意的是我们仍有几个问题未解决，如在上述的讨论中需要我们知道解的个数M，但很多时候我们不知道M，此时该怎么办？另外如何实现f(x)，使得f能够判断x是不是问题的解。关于第一个问题，我们将在介绍量子相位估计电路的时候进行讨论。

PS：如有错误，欢迎指正。

参考资料：Quantum Computation and Quantum Information