量子搜索

格罗弗算法由洛夫·格罗弗于1996年提出。与德意志-乔兹萨算法类似，该量子算法在解决相同问题时，其实际运行速度远超我们最快的经典算法。究竟快多少？格罗弗算法相比其经典对应算法提供了二次加速。虽然从表面上看，这种加速不如DJ算法的指数级加速那么引人注目，但可以认为，格罗弗的解决方案具有即时实用性，并为解决类似问题提供了一个极佳的范例。

洛夫·格罗弗使用该算法解决的问题，是关于在一个无序数据集合中进行搜索。设想一个无序列表，我们需要从中查找某个特定元素。例如，在下面这个数组中，我们要找的是 -6，即倒数第二个元素。

花一点时间思考一下，你将如何用经典方法解决这个问题？考虑一般情况并问自己：

• 在一个无序集合中查找一个元素，最快的方法是什么？

经典解法

由于无法利用任何内部结构或元数据来加速搜索，我们在经典计算中能做到的最好方式就是进行线性搜索。在线性搜索中，我们从列表开头开始，逐个遍历所有元素。在每次迭代中，检查当前元素是否正是我们最初要找的那个。如果找到了目标元素，就停止搜索；否则继续检查后续元素，直到最后一个。这种解法的时间复杂度是多少？如果我们运气好，第一个检查的元素就是目标，此时复杂度为 $O(1)$。最坏情况下，我们需要遍历整个列表——要么目标元素恰好在末尾，要么根本不存在。此时时间复杂度为 $O(N)$。因此，在平均情况下，我们需要检查大约 $50\%$ 或 $\frac{N}{2}$ 个元素。

这看起来确实是我们能做的极限了，无论采用何种方法。但若如此看待问题，未免过于狭隘。实际上，我们可以利用格罗弗算法在量子计算机上更快地解决这个问题，其渐近时间复杂度为 $O(\sqrt{N})$。

此时，有些人可能会争辩说：对数据排序后使用二分查找，复杂度为 $O(\log N)$，显然比 $O(\sqrt{N})$ 快得多。但我们需要提醒自己两点：首先，对这个数组进行排序很可能需要基于比较的排序算法，带来 $O(N \log N)$ 的开销；其次，我们讨论的是一个通用的、无结构的搜索问题，其算法不应依赖于数据本身的结构。因此，排序会违背这一初衷。

澄清这一点后，让我们深入分析格罗弗算法，它不仅为我们提供了所需的通用算法，还实现了相对于经典方法的二次加速。

量子解法

格罗弗算法依赖于量子计算中的三个基础技术。我们在前一章学习DJ算法时已经接触过其中两个：叠加态和量子预言机。第三个技术称为振幅放大，本章我们将详细探讨。

首先，回顾上面那个需要寻找 -6 的数组。由于我们直接操作的是量子比特，将数组重新表述为每个元素都是一个比特串会更方便。这样，我们可以在搜索之前，将所有信息编码进量子计算机。若逐一写出这些元素的二进制表示，会使过程变得混乱。因此，我们换一种方式重构问题如下：

• 在 $n$ 个量子比特所能处的所有可能的计算基态中，找出某个特定状态 $x$。

这样一来，我们可以把 $x$ 的搜索空间理解为长度为 $n$ 的所有比特串，共对应 $2^n$ 个可能的项目。对于3个量子比特，搜索空间就是状态 $|000\rangle, |001\rangle, ..., |111\rangle$，即 $|0\rangle, |1\rangle, ..., |7\rangle$。假设我们要找的目标 $x$ 是 $|101\rangle$ 或 $|5\rangle$。

叠加态

上述表示方式是一种简洁表达同一问题的方式。你可能已经注意到，这与我们在研究DJ算法时遇到的情况类似。允许所有长度固定的比特串构成的状态空间，使我们能够利用叠加态。我们已知，叠加态允许我们将一组完整状态同时输入量子算法进行处理。这或许也能为我们的搜索问题带来有益的结果？

让我们在这里也应用同样的技巧。这并不复杂。哈达玛门 $H$ 能将一个量子比特置于等概率叠加态。我们取 $n$ 个量子比特，使它们进入等概率叠加态，其状态表示为：单个量子比特为 $\frac{|0\rangle + |1\rangle}{\sqrt{2}}$，而 $n$ 个量子比特则为 $\frac{\sum_{x}|x\rangle}{\sqrt{2^n}}$。为了清晰起见，令 $N = 2^n$，可得 $\frac{\sum_{x}|x\rangle}{\sqrt{N}}$。

现在，我们的量子比特处于等概率叠加态。我们将此状态输入量子算法。但这个量子算法到底是什么？再次回到我们熟悉的DJ算法，看看接下来可以做什么。

预言机构造

我们也尝试为这个量子搜索算法构建一个预言机。毕竟，在DJ算法中，我们在生成等概率叠加态之后，紧接着就使用了预言机。然而，为本问题设计的预言机略显非直观。与其直接创建一个能搜索并返回目标状态的预言机，不如创建一个用于验证某个候选解是否正确的预言机。这也有助于我们构建一个适用于任意状态空间的通用解决方案，而这正是我们最初的目标。

我们可以将验证解的过程映射为一个函数。这个函数 $f$ 接收一个状态作为输入，若该状态是有效解，则输出 $0$；若不是，则输出 $1$。形式化地，对于状态 $x$，当 $f(x) = 0$ 时表示 $x = w$（即有效解），当 $f(x) = 1$ 时表示 $x \neq w$（无效解），其中 $w$ 是我们要找的目标元素。为了标记无效解，我们的预言机可以为其添加一个负相位。这使得有效状态与其余状态在相位上区分开来。

综上所述，用于搜索算法的解验证预言机 $U_f$ 可定义如下：

$$U_{f}= \begin{cases} |x\rangle & \text{若 } x = w \\ -|x\rangle & \text{若 } x \neq w \end{cases}$$

换句话说，这个预言机对一个状态的作用是：$U_f|x\rangle = (-1)^{f(x)}|x\rangle$。我们可以通过将 $CNOT$ 门与处于 $|-\rangle$ 状态的辅助量子比特结合，实现这种效果，从而通过相位回授机制为控制量子比特引入负相位，而保持目标辅助量子比特不变。

过早测量的问题

到目前为止，我们已经生成了搜索空间的等概率叠加态 $|E\rangle$，并对其应用了预言机 $U_f$，该预言机可以判断给定状态 $|x\rangle$ 是否为目标状态 $|w\rangle$。这对我们有帮助吗？严格来说，目前并没有。但这背后其实有其逻辑。原因如下。

尽管应用了预言机，我们的量子比特仍然处于等概率叠加态，最终测量结果仍可能为 $2^n$ 个可能状态中的任意一个。因此，测量到我们最初想要找到的状态的概率仅为 $\frac{1}{2^n}$。记住，我们添加的负相位并未改变测量概率，因为 $|1|^2 = |-1|^2$。因此，如果我们现在就测量量子比特，很可能得不到我们期望的解。这就是问题所在：我们需要一种机制，能够放大那个隐藏在叠加态中的理想状态的概率，同时减小其他不希望出现的状态的概率。

这正是格罗弗算法的核心精髓所在。通过一种称为振幅放大的过程，我们将操控这些状态的振幅，逐步逼近我们所寻求的理想元素。下一节我们将深入探讨这一过程。