假设给定一张包含一些城市的地图，希望确定经过所有城市的最短路径。寻找这条路径的最简单的算法就是遍历经过这些城市的所有可能路线，维护一个具有最短长度路径的动态记录。在一台经典计算机上，如果有 $N$ 条可能的路线，使用这种方法显然需要 $O(N)$ 次操作来确定最短路线。出乎意料的是，存在一个量子搜索算法，有时候被称为 Grover算法，它能够实质性地加速这个搜索方法，使之只需要 $O(\sqrt{N})$ 次操作。而且，除了刚才的路径寻找问题，量子搜索算法可以加速许多（不是所有）使用启发式搜索的经典算法，在这个意义下它是通用的。
本章我们阐述快速量子搜索算法。 6.1 节描述基础算法。 6.2 节基于 4.7 节的量子模拟算法，从另一个视角推导该算法。将给出这个算法的 3 个重要的应用： 6.3 节是量子计数， 6.4 节是 NP完全问题的求解加速，6.5节是无结构数据库的搜索。人们可能希望去改进搜索算法，使之比平方根加速更好，但 6.6 节证明这是不可能的。最后 6.7 节证明这个加速的限制适用于大多数无结构问题。
与 3.1.1 节类似，我们首先引人基于 oracle 的搜索算法，这允许我们给出搜索过程的一个非常通用的描述，且能用几何方式去可视化它的步骤和执行方式。
假设在 $N$ 个元素的搜索空间进行搜索。我们不直接搜索元素，而是关注这些元素的索引，索引对应于从 0 到 $N-1$ 的数字。为了方便，我们假设 $N=2^{n}$ ，因此索引可以存储在 $n$ 个比特中，并且假设搜索问题恰好有 $M$ 个解，其中 $1 \leqslant M \leqslant N$ 。搜索问题的一个特例可以方便地表示为一个函数 $f$ ，它的输人是 0 到 $N-1$ 之间的整数。若 $x$ 是搜索问题的一个解，那么 $f(x)=1$ ；若 $x$不是搜索问题的解，那么 $f(x)=0$ 。
假设有一个可以识别搜索问题的解的量子 oracle，我们把它视为黑盒，它的内部工作原理我们之后再讨论，但是现在来说并不重要。识别结果标记在一个 oracle 量子比特上。更确切地说， oracle 是一个西操作 $O$ ，在计算基上的行为定义如下：
$$ \begin{equation*} |x\rangle|q\rangle \xrightarrow{O}|x\rangle|q \oplus f(x)\rangle \tag{6.1} \end{equation*} $$
其中 $|x\rangle$ 是索引寄存器，$\oplus$ 表示模 2 加，并且 oracle 比特 $|q\rangle$ 是一个单量子比特，若 $f(x)=1$ ，则它进行翻转，否则不改变。我们可以通过制备 $|x\rangle|0\rangle$ ，作用 oracle，并且检查 oracle 量子比特是否翻转为 $|1\rangle$ ，来判断 $x$ 是否为搜索问题的一个解。
在量子搜索算法中，正如 1.4.4节的 Deutsch－Jozsa 算法所做的那样，把 oracle 量子比特的初始态置为 $(|0\rangle-|1\rangle) / \sqrt{2}$ 是有用的。若 $x$ 不是搜索问题的一个解，对状态 $|x\rangle(|0\rangle-|1\rangle) / \sqrt{2}$ 作用 oracle 不会改变状态。另一方面，若 $x$ 是搜索问题的解，那么 $|0\rangle$ 和 $|1\rangle$ 在 oracle 的作用下互换，使得最终的态为 $-|x\rangle(|0\rangle-|1\rangle) / \sqrt{2}$ 。于是 oracle 的作用是
$$ \begin{equation*} |x\rangle\left(\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right) \xrightarrow{o}(-1)^{f(x)}|x\rangle\left(\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right) \tag{6.2} \end{equation*} $$
注意到 oracle 量子比特的状态没有改变。在量子搜索算法中，它保持为 $(|0\rangle-|1\rangle) / \sqrt{2}$ ，为了简化描述，可以在下面的算法讨论中将其忽略。
在这个约定下，oracle 的行为可以被写为
$$ \begin{equation*} |x\rangle \xrightarrow{O}(-1)^{f(x)}|x\rangle \tag{6.3} \end{equation*} $$
我们说 oracle 通过改变解的相位，标记了搜索问题的解。在量子计算机中，对于一个有 $M$ 个解的 $N$ 元搜索问题，为了得到一个解，我们只需要运行搜索 oracle $O(\sqrt{N / M})$ 次。
在没有描述它在实际中是如何工作的情况下，对 oracle 的讨论是相当抽象的，甚至可能是令人费解的。这看上去好像 oracle已经知道了搜索问题的答案，基于这种 oracle 查询的量子搜索算法有什么用呢？答案是，知道搜索问题的解和能够把解识别出来是有区别的，关键在于有可能在不必知道解的情况下识别解。
阐述这个问题的一个简单例子是因子分解。假设给定一个大数 $m$ ，且被告知它是两个素数 $p$和 $q$ 的乘积，相同的情形出现在试图去破解 RSA 公钥密码系统时（附录 E ）。为了确定 $p$ 和 $q$ ，在经典计算机上明显的办法是搜索从 2 到 $m^{1 / 2}$ 的所有整数，以找到两个素因子中更小的那个。即我们连续地用 2 到 $m^{1 / 2}$ 之间的每个数去试除 $m$ ，直到找到较小的素因子。另一个素因子可以通过用 $m$ 除以较小的素因子得到。显然，为找到一个因子，这种基于搜索的方法在一个经典计算机上需要大约 $m^{1 / 2}$ 次试除。
量子搜索算法可以被用来加速这一过程。由定义可得，oracle 在输人态 $|x\rangle$ 的作用是用 $x$ 去除 $m$ ，并且检查是否可以除尽；如果是，就翻转 oracle 量子比特。运用带 oracle 的量子搜索算法可以以很大的概率给出两个素因子中较小的一个。但是为了使算法工作，我们需要构造一个有效的电路来实现 oracle。如何实现是可逆计算技术中的一个练习。首先，我们定义 $f(x)$ 如下：若 $x$
整除 $m$ ，则 $f(x) \equiv 1$ ，否则 $f(x)=0$ 。 $f(x)$ 告诉我们试除是否成功。利用 3.2.5 节的可逆计算技术，通过改造通常用于试除的（不可逆）经典电路，构建一个经典可逆电路，把 $(x, q)$ ——表示一个输人寄存器初始化为 $x$ ，一个单比特输出寄存器初始化为 $q$ ——变为 $(x, q \oplus f(x))$ 。这个可逆电路的资源代价在试除的不可逆经典电路的两倍以内，因而我们认为两个电路本质上消耗同样的资源。进一步，经典可逆电路可以立即转换成把 $|x\rangle|q\rangle$ 变成 $|x\rangle|q \oplus f(x)\rangle$ 的量子电路，像 oracle 所要求的那样。关键在于，即使不知道 $m$ 的因子，我们也可以具体地构造一个可以识别解的 oracle。利用这个 oracle 和量子搜索算法，我们可以使用 $O\left(m^{1 / 4}\right)$ 次 oracle 查询来搜索 2 到 $m^{1 / 2}$ 的范围，即只需要大概 $m^{1 / 4}$ 次试除，而不像经典算法的 $m^{1 / 2}$ 次！
上述因子分解的例子只有概念上而非实际上的意义：存在比遍历所有可能因子更快的经典因子分解算法。不过，它说明了应用量子搜索算法的一般方式：基于搜索技术的经典算法可以被量子搜索算法加速。本章后面的部分将考察量子搜索算法确实有助于加速 NP 完全问题的求解的情形。
搜索算法如图 6－1 所示。算法很好地利用了一个 $n$ 量子比特寄存器。oracle 的内部工作，包括可能需要的额外的工作量子比特，对描述量子搜索算法本身并不重要。算法的目标是使用最少次数的 oracle 去找到搜索问题的一个解。
图 6－1 量子搜索算法的电路示意图。为实现 oracle 可能会用到工作量子比特，但是量子搜索算法的分析只涉及 $n$ 位量子比特寄存器
算法开始于状态 $|0\rangle^{\otimes n}$ ，用阿达玛变换使计算机处于均匀叠加态
$$ \begin{equation*} |\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle \tag{6.4} \end{equation*} $$
量子搜索算法由反复地作用一个记为 $G$ 的称为 Grover 迭代或 Grover 算子的量子子程序构成。Grover 迭代的量子电路如图 6－2 所示，可分为如下 4 个步骤：
1.作用 oracle $O$ 。
2.作用阿达玛变换 $H^{\otimes n}$ 。
3.执行条件相位偏移，使得除 $|0\rangle$ 之外的每个计算基矢态获得一个 -1 的相位偏移：
$$ \begin{equation*} |x\rangle \rightarrow-(-1)^{\delta_{x 0}}|x\rangle \tag{6.5} \end{equation*} $$
4.作用阿达玛变换 $H^{\otimes n}$ 。
图 6－2 Grover 迭代 $G$ 的量子电路
习题 6.1 证明在 Grover 迭代中，对应于相位偏移的酉算子是 $2|0\rangle\langle 0|-I$ 。
Grover 迭代中的每个操作都可以在量子计算机上有效实现。步骤 2 和步骤 4 的阿达玛变换各需要 $n=\log (N)$ 次操作。步骤 3 的条件相位偏移，可以通过 4.3 节的技术，使用 $O(n)$ 个门实现。 oracle 调用的代价取决于具体的应用；目前，Grover 迭代只需要单次 oracle 调用。注意到步骤2， 3 和 4 组合在一起的效果为
$$ \begin{equation*} H^{\otimes n}(2|0\rangle\langle 0|-I) H^{\otimes n}=2|\psi\rangle\langle\psi|-I \tag{6.6} \end{equation*} $$
其中 $|\psi\rangle$ 是式（6.4）中的均匀叠加态。因此 Grover 迭代 $G$ 可以写成 $G=(2|\psi\rangle\langle\psi|-I) O$ 。
习题 6.2 证明操作 $(2|\psi\rangle\langle\psi|-I)$ 作用在一般的状态 $\sum_{k} \alpha_{k}|k\rangle$ 上产生
$$ \begin{equation*} \sum_{k}\left[-\alpha_{k}+2\langle\alpha\rangle\right]|k\rangle \tag{6.7} \end{equation*} $$
其中 $\langle\alpha\rangle \equiv \sum_{k} \alpha_{k} / N$ 是 $\alpha_{k}$ 的均值。因此，$(2|\psi\rangle\langle\psi|-I)$ 有时被称为关于均值的反演操作。
Grover 迭代做了什么？我们已经注意到 $G=(2|\psi\rangle\langle\psi|-I) O$ 。事实上，我们将证明 Grover 迭代可以被视为一个二维空间的旋转，这个空间由初始态 $|\psi\rangle$ 和搜索问题中解的均匀叠加态张成。为了弄清楚这一点，用 $\sum_{x}^{\prime}$ 表示搜索问题中所有解的和，$\sum_{x}^{\prime \prime}$ 表示在搜索问题中所有非解元素的和。定义归一化状态
$$ \begin{align*} |\alpha\rangle & \equiv \frac{1}{\sqrt{N-M}} \sum_{x}^{\prime \prime}|x\rangle \tag{6.8}\\ |\beta\rangle & \equiv \frac{1}{\sqrt{M}} \sum_{x}^{\prime}|x\rangle \tag{6.9} \end{align*} $$
简单的代数运算表明，初始态 $|\psi\rangle$ 可以被重新表示为
$$ \begin{equation*} |\psi\rangle=\sqrt{\frac{N-M}{N}}|\alpha\rangle+\sqrt{\frac{M}{N}}|\beta\rangle \tag{6.10} \end{equation*} $$
因此量子计算机的初始态属于由 $|\alpha\rangle$ 和 $|\beta\rangle$ 张成的空间。
$G$ 的作用效果可以以一种优美的方式如下理解。oracle 操作 $O$ 是在由 $|\alpha\rangle$ 和 $|\beta\rangle$ 定义的平面上以 $|\alpha\rangle$ 为法线进行反射，即 $O(a|\alpha\rangle+b|\beta\rangle)=a|\alpha\rangle-b|\beta\rangle$ 。类似地， $2|\psi\rangle\langle\psi|-I$ 在由 $|\alpha\rangle$ 和 $|\beta\rangle$ 定义的平面上以 $|\psi\rangle$ 为法线进行反射。并且两个反射的乘积是一个旋转！这告诉我们，对于任意的 $k$ ，状态 $G^{k}|\psi\rangle$ 将留在 $|\alpha\rangle$ 和 $|\beta\rangle$ 张成的空间里。同时这也给出了旋转角：令 $\cos \theta / 2=\sqrt{(N-M) / N}$ ，使得 $|\psi\rangle=\cos \theta / 2|\alpha\rangle+\sin \theta / 2|\beta\rangle$ 。如图 6－3 所示，构成 $G$ 的两个反射把 $|\psi\rangle$ 变为
$$ \begin{equation*} G|\psi\rangle=\cos \frac{3 \theta}{2}|\alpha\rangle+\sin \frac{3 \theta}{2}|\beta\rangle \tag{6.11} \end{equation*} $$
因此旋转角实际上是 $\theta$ 。由此，连续作用 $G$ 将使态变成
$$ \begin{equation*} G^{k}|\psi\rangle=\cos \left(\frac{2 k+1}{2} \theta\right)|\alpha\rangle+\sin \left(\frac{2 k+1}{2} \theta\right)|\beta\rangle \tag{6.12} \end{equation*} $$
总之，$G$ 是在 $|\alpha\rangle$ 和 $|\beta\rangle$ 张成的二维空间上的一个旋转，每次 $G$ 的作用把空间旋转 $\theta$ 角度。Grover迭代的反复作用把状态向量旋转到接近 $\beta$ 的位置。这时，通过对计算基上的测量，将以很高的概率得到叠加态 $|\beta\rangle$ 中的一个测量结果，也就是说，得到搜索问题的一个解。专题 6.1 给出了一个用来阐述搜索算法的例子，其中 $N=4$ 。
图 6－3 单次 Grover 迭代 $G$ 的作用：状态向量朝搜索问题的所有解的叠加态 $|\beta\rangle$ 旋转 $\theta$ 角度。开始时状态向量偏离了 $|\alpha\rangle \theta / 2$ 角度，$|\alpha\rangle$ 是一个与 $|\beta\rangle$ 正交的状态。Oracle 操作 $O$ 先以 $|\alpha\rangle$ 为法线进行反射，然后操作 $2|\psi\rangle\langle\psi|-I$ 以 $|\psi\rangle$ 为法线进行反射。图中 $|\alpha\rangle$ 和 $|\beta\rangle$ 稍加延长，以避免混乱（所有状态都应该是单位向量）。经过反复的 Grover 迭代，状态向量接近于 $|\beta\rangle$ ，此时在计算基上测量将以很高的概率输出搜索问题的一个解。算法具有可观的效率，因为 $\theta$ 差不多为 $\Omega(\sqrt{M / N})$ ，因此为把状态向量旋转到接近于 $|\beta\rangle$ 的状态，只需要对 $G$ 作用 $O(\sqrt{N / M})$ 次
习题 6.3 证明在 $|\alpha\rangle,|\beta\rangle$ 基下，我们可以把 Grover 迭代写为
$$ G=\left[\begin{array}{cc} \cos \theta & -\sin \theta \tag{6.13}\\ \sin \theta & \cos \theta \end{array}\right] $$
其中 $\theta$ 是一个在 0 到 $\pi / 2$ 之间的实数（出于简单起见，假定 $M \leqslant N / 2$ ，而这个限制可以马上被解除），它满足
$$ \begin{equation*} \sin \theta=\frac{2\sqrt{M(N-M)}}{N} \tag{6.14} \end{equation*} $$
为了旋转 $|\psi\rangle$ 使它接近 $|\beta\rangle$ ，Grover 迭代必须重复多少次？系统的初始态是 $|\psi\rangle=\sqrt{(N-M) / N}|\alpha\rangle+$ $\sqrt{M / N}|\beta\rangle$ ，所以通过大概 $\arccos (\sqrt{M / N})$ 次旋转可以把系统旋转到 $|\beta\rangle$ 。记 $C I(x)$ 为最接近实数 $x$ 的整数，按照惯例，我们向下取整，例如 $C I(3.5)=3$ 。从而，重复 Grover 迭代
$$ \begin{equation*} R=\mathrm{CI}\left(\frac{\arccos \sqrt{M / N}}{\theta}\right) \tag{6.15} \end{equation*} $$
次把状态 $|\psi\rangle$ 旋转到距离 $|\beta\rangle$ 为 $\theta / 2 \leqslant \pi / 4$ 的角度范围内。于是对状态在计算基上进行测量，将至少以一半的概率给出搜索问题的一个解。事实上，$M$ 和 $N$ 取特定值的时候可以达到高得多的成功概率。例如，当 $M \ll N$ 时，我们有 $\theta \approx \sin \theta \approx 2\sqrt{M / N}$ ，故最终状态的角度误差至多是 $\theta / 2 \approx \sqrt{M / N}$ ，给出最多为 $M / N$ 的错误概率。注意 $R$ 依赖于解的数目 $M$ ，但不依赖于解本身，因此如果我们知道 $M$ ，就可以使用上述的量子搜索算法。在 6.3 节，我们将说明在应用搜索算法的时候，如何去掉需要知道 $M$ 这个要求。
这里用一个清晰的例子来说明量子搜索算法在 $N=4$ 的搜索空间上如何运行。首先，有这样的 oracle，对 $x=x_{0}$ 有 $f\left(x_{0}\right)=1$ ，对其他的 $x$ ，有 $f(x)=0$ 。此 oracle 的电路是以下四种情况之一。
从左到右分别对应 $x_{0}=0,1,2,3$ ，上面两个量子比特表示查询位 $x$ ，底部的量子比特携带 oracle 的回答。初始阿达玛变换和一次 Grover 迭代 $G$ 的量子电路图如下。
初始时，上面两个量子比特处于状态 $|0\rangle$ ，底部量子比特处于 $|1\rangle$ 。虚线框中的量子门执行条件相位偏移操作 $2|00\rangle\langle 00|-I$ 。我们需要重复迭代 $G$ 多少次才能得到 $x_{0}$ ？由式（ 6.15 ），代入 $M=1$ ，我们发现需要的迭代次数少于 1 次。可以看到，因为在式（6.14）中有 $\theta=\pi / 3$ ，
所以在这个特殊的例子中只需要 1 次迭代就可以获得 $x_{0}$ 。在图 6－3 所示几何图形中，我们的初始状态为 $|\psi\rangle=(|00\rangle+|01\rangle+|10\rangle+|11\rangle) / 2$ ，距离 $\alpha$ 的角度为 $30^{\circ}$ ，一次旋转 $\theta=60^{\circ}$ 即可从状态 $|\psi\rangle$ 移到状态 $|\beta\rangle$ 。读者可以使用上述量子电路自己验证，执行一次 oracle 之后上面两个量子比特的测量结果会给出 $x_{0}$ 。相反，经典计算机或经典电路，尝试区分这 4 个oracle平均需要 2.25 次查询。
式（6.15）给出了量子搜索算法所调用的 oracle 次数的精确表达式，然而给出一个概括 $R$ 的本质行为的更简单的表达式也是有用的。由式（6.15）可知 $R \leqslant\lceil\pi / 2 \theta\rceil$ ，因此 $\theta$ 的一个下界将给出 $R$ 的一个上界。暂且假设 $M \leqslant N / 2$ ，我们有
$$ \begin{equation*} \frac{\theta}{2} \geqslant \sin \frac{\theta}{2}=\sqrt{\frac{M}{N}} \tag{6.16} \end{equation*} $$
由此可导出需要的迭代次数的一个优雅的上界
$$ \begin{equation*} R \leqslant\left\lceil\frac{\pi}{4} \sqrt{\frac{N}{M}}\right\rceil \tag{6.17} \end{equation*} $$
也就是说，必须执行 $R=O(\sqrt{N / M})$ 次 Grover 迭代（因此 oracle 调用也需要同样的次数）才能以高的概率得到搜索问题的一个解，这是对经典算法所需要的 $O(N / M)$ 次 oracle 调用的平方加速。对 $M=1$ 的量子搜索算法总结如下。
输入：（1）执行变换 $O|x\rangle|q\rangle=|x\rangle|q \oplus f(x)\rangle$ 的黑盒 oracle $O$ ，其中对除 $x_{0}$ 外的所有 $0 \leqslant x < $ $2^{n}$ ，有 $f(x)=0$ ，而 $f\left(x_{0}\right)=1$ ；（2）处于 $|0\rangle$ 状态的 $n+1$ 个量子比特。
输出：$x_{0}$ 。
运行时间：$O\left(\sqrt{2^{n}}\right)$ 次操作，以 $O(1)$ 概率成功。
步骤：
1.$|0\rangle^{\otimes n}|0\rangle$
初始态
2.$\rightarrow \frac{1}{\sqrt{2^{n}}} \sum_{x=0}^{2^{n}-1}|x\rangle\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right]$
对前 $n$ 个量子比特作用 $H^{\otimes n}$ ，对最后一个量子比特执行 $H X$
3.$\rightarrow[(2|\psi\rangle\langle\psi|-I) O]^{R} \frac{1}{\sqrt{2^{n}}} \sum_{x=0}^{2^{n}-1}|x\rangle\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right] \quad$ 运行 Grover 迭代 $R \approx\left\lceil\pi \sqrt{2^{n}} / 4\right\rceil$ 次
$$ \approx\left|x_{0}\right\rangle\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right] $$
4.$\rightarrow x_{0}$
对前 $n$ 个量子比特进行测量
习题6.4 像上面那样，对多解情况（ $1 < M < N / 2$ ）给出具体的步骤。
当超过一半的元素是搜索问题的解，即 $M \geqslant N / 2$ 时，会发生什么？根据表达式 $\theta=\arcsin$（ $2\sqrt{M(N-M)} / N)$（对比式（6.14）），我们看到当 $M$ 从 $N / 2$ 变为 $N$ 时，$\theta$ 会减小。因而当
$M \geqslant N / 2$ 时，搜索算法所需要的迭代次数会随 $M$ 增加。直观上，一个搜索算法有这样的性质是荒唐的：我们希望当解的数目增加时，求解应该变得容易。至少有两种解决这个问题的方法。若事先知道 $M$ 大于 $N / 2$ ，就随机从搜索空间取一个元素，并用 oracle 检查它是否为一个解。这种方法的成功概率至少为一半，并且只需要调用 oracle一次。它的缺点是我们可能事先不知道解的数目 $M$ 。
在不知道是否 $M \geqslant N / 2$ 的情形，可以使用另一种方法。这种方法本身就很有趣，并且有助于简化对搜索问题中解的量子计数算法的分析，这会在 6.3 节给出。其思路是通过增加 $N$ 个不是解的元素到搜索空间中，来使搜索空间的元素数量加倍。因而，在新的搜索空间中，少于一半的元素是解。这可以通过增加一个单量子比特 $|q\rangle$ 到搜索索引中实现，以把要搜索的元素的数目加倍到 $2 N$ 。构造一个新的增广 oracle $O^{\prime}$ ，它对一个元素进行标记，仅当这个元素是搜索问题的解且附加比特被置为 0 。在习题 6.5 中将解释如何通过调用一次 $O$ 来构造 $O^{\prime}$ 。新的搜索问题在 $2 N$ 项中只有 $M$ 个解，因此运行基于新的 oracle $O^{\prime}$ 的搜索算法，至多需要对 $O^{\prime}$ 进行 $R=\pi / 4\sqrt{2 N / M}$次调用，因而完成搜索需要对 $O$ 进行 $O(\sqrt{N / M})$ 次调用。
习题 6.5 证明通过调用一次 $O$ ，并使用一些基本量子门和附加量子比特 $|q\rangle$ 可以构造增广 oracle $O^{\prime}$ 。
量子搜索算法用途广泛，后面的几节会介绍其中的一部分。该算法的巨大功效来源于我们没有对搜索问题假定任何特别的结构。这是基于黑盒 oracle 的问题提法带来的巨大好处，只要方便，在本章剩下的部分我们就采用这种观点。当然，在实际应用中，我们必须懂得如何实现 oracle，在我们考虑的每个实际问题中，我们都会给出实现 oracle 的具体描述。
习题 6.6 验证专题 6.1 第 2 个图中虚线框里的门电路完成条件相移操作 $2|00\rangle\langle 00|-I$ ，相差一个不重要的全局相位因子。
量子搜索算法的正确性很容易验证，但是如何凭空想出这样一个算法绝不是显然的事情。在这一节中，我们将描述一种启发性方法，从中可以＂推导＂出量子搜索算法，希望可以为量子算法的设计技巧带来一些直观的认识。作为一个有用的附带结果，我们将得到一个确定性量子搜索算法。因为我们的目的是得到灵感而不是通用性，为简单起见，假设搜索问题恰好有一个解，我们记为 $x$ 。
我们的方法包含两步。首先，我们猜想一个可用于求解搜索问题的哈密顿量。更准确地说，我们找一个哈密顿量 $H$ ，它依赖于解 $x$ 和初始状态 $|\psi\rangle$ ，即量子系统根据 $H$ 进行演化，在设定时间内从初始状态 $|\psi\rangle$ 演化到状态 $|x\rangle$ 。当我们找到这个哈密顿量和初始状态后，就可以进人第二步，尝试用一个量子电路去模拟哈密顿量的演化行为。令人惊奇的是，遵循这个过程，很快能导出量子搜索算法！在之前对量子电路的通用性研究中，问题 4.3 里，我们已经见过这个两阶段的过程，现在它对于量子搜索的研究也是有用的。
假设算法的初始状态是 $|\psi\rangle$ 。我们等一下会对 $|\psi\rangle$ 进行约束，但在完全理解算法的动态过程
之前，为了方便先令 $|\psi\rangle$ 是不确定的。量子搜索的目标是将 $|\psi\rangle$ 转变成 $|x\rangle$ 或近似的结果。让我们来猜一下什么样的哈密顿量可以做到这样的演化过程。最简单地，我们猜测哈密顿量完全由 $|x\rangle$和 $|\psi\rangle$ 来构造。因此，哈密顿量一定是 $|\psi\rangle\langle\psi|,|x\rangle\langle x|,|\psi\rangle\langle x|,|x\rangle\langle\psi|$ 这些项的和。也许最简单的选择是以下两个哈密顿量：
$$ \begin{align*} H & =|x\rangle\langle x|+|\psi\rangle\langle\psi| \tag{6.18}\\ H & =|\psi\rangle\langle x|+|x\rangle\langle\psi| \tag{6.19} \end{align*} $$
事实上这两个哈密顿量都可以导出量子搜索算法！不过，我们暂且仅限于分析式（6.18）的哈密顿量。回忆 2.2.2 节中，经过时间 $t$ 之后，初始状态为 $|\psi\rangle$ 的量子系统，根据哈密顿量 $H$ 演化以后的状态为
$$ \begin{equation*} \exp (-\mathrm{i} H t)|\psi\rangle \tag{6.20} \end{equation*} $$
直观上看起来很好：对于很小的 $t$ ，演化的结果是将 $|\psi\rangle$ 变成 $(I-\mathrm{i} t H)|\psi\rangle=(1-\mathrm{i} t)|\psi\rangle-\mathrm{i} t\langle x \mid \psi\rangle|x\rangle$ 。即，$|\psi\rangle$ 稍微地向 $|x\rangle$ 所在的方向发生偏转。让我们实际来做一下完整的分析，确定是否存在这样一个 $t$ ，使 $\exp (-\mathrm{i} H t)|\psi\rangle=|x\rangle$ 。显然，我们可以将分析限于由 $|x\rangle$ 和 $|\psi\rangle$ 张成的二维空间。由格拉姆－施密特过程，我们可以找到 $|y\rangle$ ，使得 $|x\rangle$ 和 $|y\rangle$ 组成空间的一组标准正交基，从而存在 $\alpha, \beta$ ，使得 $|\psi\rangle=\alpha|x\rangle+\beta|y\rangle$ ，并满足 $\alpha^{2}+\beta^{2}=1$ 。为了方便，我们选择 $|x\rangle$ 和 $|y\rangle$ 的相位使得 $\alpha$和 $\beta$ 为非负实数。在 $|x\rangle$ 和 $|y\rangle$ 基底下，我们有
$$ H=\left[\begin{array}{ll} 1 & 0 \tag{6.21}\\ 0 & 0 \end{array}\right]+\left[\begin{array}{cc} \alpha^{2} & \alpha \beta \\ \alpha \beta & \beta^{2} \end{array}\right]=\left[\begin{array}{cc} 1+\alpha^{2} & \alpha \beta \\ \alpha \beta & 1-\alpha^{2} \end{array}\right]=I+\alpha(\beta X+\alpha Z) $$
因此
$$ \begin{equation*} \exp (-\mathrm{i} H t)|\psi\rangle=\exp (-\mathrm{i} t)[\cos (\alpha t)|\psi\rangle-\mathrm{i} \sin (\alpha t)(\beta X+\alpha Z)|\psi\rangle] \tag{6.22} \end{equation*} $$
全局相因子 $\exp (-i t)$ 可以被忽略，经过简单的运算可以得到 $(\beta X+\alpha Z)|\psi\rangle=|x\rangle$ ，因此经过时间 $t$ 以后，系统的状态为
$$ \begin{equation*} \cos (\alpha t)|\psi\rangle-\mathrm{i} \sin (\alpha t)|x\rangle \tag{6.23} \end{equation*} $$
因此，在 $t=\pi / 2 \alpha$ 时刻，对系统的观测以概率 1 获得结果 $|x\rangle$ ，即我们找到了问题的一个解！不幸的是，观测时间依赖于 $\alpha$ ，即状态 $|\psi\rangle$ 在 $|x\rangle$ 方向的分量，从而依赖于 $|x\rangle$ ，也就是我们想要确定的量。一个明显的解决办法是尝试令 $\alpha$ 对于所有的 $|x\rangle$ 都相同，即选取 $|\psi\rangle$ 为均匀叠加态
$$ \begin{equation*} |\psi\rangle=\frac{\sum_{x}|x\rangle}{\sqrt{N}} \tag{6.24} \end{equation*} $$
这样的选择使得对于所有 $x$ 都有 $\alpha=1 / \sqrt{N}$ ，因此观测时间 $t=\pi \sqrt{N} / 2$ 并不依赖于对 $x$ 的了解。进一步地，状态式（6.24）有明显的优势，即我们已经知道使用阿达玛变换便可以很容易地制备出这个态。
我们现在知道哈密顿量（式（6.18））可以使 $|\psi\rangle$ 旋转至 $|x\rangle$ 。那么是否可以找到一个量子电路来模拟这个哈密顿量，从而得到量子搜索算法呢？使用 4.7 节的方法，我们看到模拟 $H$ 的一个自然的方法是，对短时间增量 $\Delta t$ ，交替模拟哈密顿量 $H_{1} \equiv|x\rangle\langle x|$ 和 $H_{2} \equiv|\psi\rangle\langle\psi|$ 。如图 6－4 和图 6－5 所示，这些哈密顿量用第 4 章的方法很容易模拟。
图 6－4 用两次 oracle 调用，实现操作 $\exp (-\mathrm{i}|x\rangle\langle x| \Delta T)$ 的电路
图 6－5 对式（6.24）中的 $|\psi\rangle$ ，实现操作 $\exp (-\mathrm{i}|\psi\rangle\langle\psi| \Delta t)$ 的电路
习题 6.7 验证图 6－4 和图 6－5 中的电路分别实现操作 $\exp (-\mathrm{i}|x\rangle\langle x| \Delta t)$ 和 $\exp (-\mathrm{i}|\psi\rangle\langle\psi| \Delta t)$ ，其中 $|\psi\rangle$ 如式（6.24）所示。
在量子模拟中 oracle 的调用次数取决于为了获取合理精度而使用的时间步长的大小。假设我们用的模拟步长为 $\Delta t$ ，可达到 $O\left(\Delta t^{2}\right)$ 的精度。则所需要的步数为 $t / \Delta t=\Theta(\sqrt{N} / \Delta t)$ ，于是累计误差为 $O\left(\Delta t^{2} \times \sqrt{N} / \Delta t\right)=O(\Delta t \sqrt{N})$ 。为了得到合理的高成功概率，需要将误差控制到 $O(1)$ ，这意味着我们必须选择 $\Delta t=\Theta(1 / \sqrt{N})$ ，这会导致 oracle 的调用次数为 $O(N)$ ——而这并不比经典算法好！如果我们用更精确的方法，比如精度为 $O\left(\Delta t^{3}\right)$ ，来进行量子模拟会怎么样呢？这样累计误差为 $O\left(\Delta t^{2} \sqrt{N}\right)$ ，为了得到合理的高成功概率，我们需要选择 $\Delta t=\Theta\left(N^{-1 / 4}\right)$ ，于是 oracle 的总调用次数为 $O\left(N^{3 / 4}\right)$ ，这比经典算法有明显提升，尽管结果仍然没有像 6.1 节所述的量子搜索算法那样好。一般来说，使用更精确的模拟技术，会导致模拟过程中所需调用 oracle次数的减少。
习题 6.8 假设模拟步的精度为 $O\left(\Delta t^{r}\right)$ 。证明以合理的精度模拟 $H$ 所需调用 oracle 的次数为 $O\left(N^{r / 2(r-1)}\right)$ 。注意当 $r$ 增大时，$N$ 的指数趋向于 $1 / 2$ 。
我们用 4.7 节的量子模拟的一般结果分析了式（6.18）哈密顿量的量子模拟的精度。当然，在这个例子中处理的是特定的哈密顿量，不是一般的。这提示我们，具体计算一个模拟步 $\Delta t$ 时间的结果而不是基于一般性的分析，也许是有意义的。对于任意特定的模拟方法，我们都可以这样做——虽然计算出模拟步结果的过程是有点乏味，但本质上是很直接的计算。显然起点是具体计算最低阶模拟技术的作用，即计算 $\exp (-\mathrm{i}|x\rangle\langle x| \Delta t) \exp (-\mathrm{i}|\psi\rangle\langle\psi| \Delta t)$ 或 $\exp (-\mathrm{i}|\psi\rangle\langle\psi| \Delta t) \exp (-\mathrm{i}|x\rangle\langle x| \Delta t)$的一个或全部。两种情况结果本质上是一样的。我们将重点关注 $U(\Delta t) \equiv \exp (-\mathrm{i}|\psi\rangle\langle\psi| \Delta t) \exp ($
$-\mathrm{i}|x\rangle\langle x| \Delta t)$ 的情况。显然 $U(\Delta t)$ 的作用只在由 $|x\rangle\langle x|$ 和 $|\psi\rangle\langle\psi|$ 张成的空间中是非平凡的，因此我们把讨论范围限制在该空间，并在基 $|x\rangle,|y\rangle$ 中讨论，其中 $|y\rangle$ 的定义如前所述。注意到在该表示中，$|x\rangle\langle x|=(I+Z) / 2=(I+\hat{z} \cdot \vec{\sigma}) / 2$ ，其中 $\hat{z} \equiv(0,0,1)$ 是沿 $z$ 方向的单位向量，而 $|\psi\rangle\langle\psi|=(I+\vec{\psi} \cdot \vec{\sigma}) / 2$ ，其中 $\vec{\psi}=\left(2 \alpha \beta, 0,\left(\alpha^{2}-\beta^{2}\right)\right) ~($ 注意这是布洛赫向量表示法，详见 4.2 节）。经过简单的计算，除去一个无关紧要的全局相位因子，可以得到
$$ \begin{align*} U(\Delta t)= & \left(\cos {}^{2}\left(\frac{\Delta t}{2}\right)-\sin {}^{2}\left(\frac{\Delta t}{2}\right) \vec{\psi} \cdot \hat{z}\right) I \\ & -2\mathrm{i} \sin \left(\frac{\Delta t}{2}\right)\left(\cos \left(\frac{\Delta t}{2}\right) \frac{\vec{\psi}+\hat{z}}{2}+\sin \left(\frac{\Delta t}{2}\right) \frac{\vec{\psi} \times \hat{z}}{2}\right) \cdot \vec{\sigma} \tag{6.25} \end{align*} $$
习题 6.9 验证式（6.25）（提示：参看习题4.15）。
式（6.25）表明 $U(\Delta t)$ 是布洛赫球面上的一个旋转，以 $\vec{r}$ 为旋转轴，$\vec{r}$ 定义如下：
$$ \begin{equation*} \vec{r}=\cos \left(\frac{\Delta t}{2}\right) \frac{\vec{\psi}+\hat{z}}{2}+\sin \left(\frac{\Delta t}{2}\right) \frac{\vec{\psi} \times \hat{z}}{2} \tag{6.26} \end{equation*} $$
转过的角度为 $\theta$ ，定义为
$$ \begin{equation*} \cos \left(\frac{\theta}{2}\right)=\cos {}^{2}\left(\frac{\Delta t}{2}\right)-\sin {}^{2}\left(\frac{\Delta}{2}\right) \vec{\psi} \cdot \hat{z} \tag{6.27} \end{equation*} $$
将 $\vec{\psi} \cdot \hat{z}=\alpha^{2}-\beta^{2}=(2 / N-1)$ 代人化简得
$$ \begin{equation*} \cos \left(\frac{\theta}{2}\right)=1-\frac{2}{N} \sin {}^{2}\left(\frac{\Delta t}{2}\right) \tag{6.28} \end{equation*} $$
注意 $\vec{\psi} \cdot \vec{r}=\hat{z} \cdot \vec{r}$ ，因此 $|\psi\rangle\langle\psi|$ 和 $|x\rangle\langle x|$ 在布洛赫球面上以 $\vec{r}$ 为轴心的圆上。总而言之，$U(\Delta t)$ 的作用如图 6－6 所示，将 $|\psi\rangle\langle\psi|$ 绕 $\vec{r}$ 轴进行旋转，每次转过一个角度 $\theta$ 。当 $|\psi\rangle\langle\psi|$ 已经旋转至足够接近 $|x\rangle\langle x|$ 时，我们终止这个过程。因为我们考虑的是量子模拟的情况，所以起初我们假想 $\Delta t$很小，但式（6.28）表明一个聪明的做法是令 $\Delta t=\pi$ ，以使旋转的角度 $\theta$ 最大化。这样的话我们可以得到 $\cos \left(\frac{\theta}{2}\right)=1-2 / N$ ，当 N 很大时，$\theta \approx 4 / \sqrt{N}$ ，找到解 $|x\rangle$ 所需要调用 oracle的次数是 $O(\sqrt{N})$ ，正如原始的量子搜索算法一样。
确实，若我们令 $\Delta t=\pi$ ，那么这个＂量子模拟＂实际上等同于原始的量子搜索算法，因为量子模拟中的算子是 $\exp (-\mathrm{i} \pi|\psi\rangle\langle\psi|)=I-2|\psi\rangle\langle\psi|$ 和 $\exp (-\mathrm{i} \pi|x\rangle\langle x|)=I-2|x\rangle\langle x|$ ，除一个全局相移因子外与 Grover 迭代的步骤是等同的。这样看来，图 6－2 和图 6－3 所示量子搜索算法的电路只是图 6－4 和图 6－5 所示模拟电路当 $\Delta t=\pi$ 时的简化。
习题 6.10 证明通过适当选取 $\Delta t$ ，可以得到一个量子搜索算法，进行 $O(\sqrt{N})$ 次查询可以精确得到最终状态 $|x\rangle$ ，即算法的成功概率为 1 ，而不是一个更小的概率。
我们已经从量子模拟这个角度重新推导出了量子搜索算法。为什么这个方法可行呢？它可以用来寻找其他快速量子算法吗？我们不能以任何确定性的方式回答这个问题，不过下面的一些想
法或许是有趣的。所采用的基本过程包括 4 个方面：（1）明确需要求解的问题，包括所期望的量子算法的输人输出的描述；（2）猜测一个求解问题的哈密顿量，并验证它实际上可行；（3）找到一个过程来模拟这个哈密顿量；（4）分析模拟所需要的资源。这与传统方法有两方面的不同：我们猜测一个哈密顿量，而不是量子电路，并且在传统方法里并没有模拟步的类似物。这两点中更重要的是第一点。设计量子电路来求解一个问题有很大的自由度。尽管这种自由度是量子计算强大能力的部分来源，但它也使得找到好的电路相当困难。与之相比，确定一个哈密顿量是一个局限得多的问题，因此在求解问题的过程中自由度更小一些，但这些约束也许实际上会使我们更容易找到求解问题的有效量子算法。我们已经从量子搜索算法中看到了这点，也许还有更多的量子算法可以通过这种途径来发掘，但我们尚不知道。似乎可以肯定的是，＂量子算法看作量子模拟＂的观点为促进量子算法的发展提供了一个有用的新视角。
图 6－6 初始状态 $\vec{\psi}$ 围绕轴 $\vec{r}$ 旋转至最终态 $\hat{z}$ 的布洛赫球面图示
习题6.11（多解连续量子搜索）猜测一个哈密顿量用于求解有 $M$ 个解的连续时间搜索问题。
习题6.12（量子搜索的其他哈密顿量）假设
$$ \begin{equation*} H=|x\rangle\langle\psi|+|\psi\rangle\langle x| \tag{6.29} \end{equation*} $$
1.证明根据这个哈密顿量 $H$ 来演化，状态 $|\psi\rangle$ 旋转至状态 $|x\rangle$ 只需要 $O(1)$ 的时间。
2.说明如何进行哈密顿量 $H$ 的量子模拟，并确定以高概率获得解该模拟技术所需 oracle 的调用次数。
如果 $N$ 个元素中有 $M$ 个目标对象，我们可以多快地确定这个未知的 $M$ ？显然，在一台经典计算机上，需要对 oracle 进行 $\Theta(N)$ 次查询。在一台量子计算机上，结合 Grover 迭代和基于量子傅里叶变换的相位估计技术（见第 5 章），有可能可以更快地估计解的个数。这有一些重要的应用。首先，若我们能够很快地估计解的数目，那么就有可能很快地找到解，即使解的个数未知；因为我们可以先计算解的数目，然后用量子搜索算法去找到解。其次，量子计数使得我们可以判定解是否存在，这可以通过判定解的个数是否非 0 来完成。这有一些应用，比如 NP 完全问题的解，它们可以表述为某个搜索问题的解的存在性。
习题6.13 考虑计数问题的一个经典算法，该算法在搜索空间中均匀独立地采样 $k$ 次，令 $X_{1}, \cdots, X_{k}$表示 oracle 调用的结果，即当第 $j$ 次调用得到问题的一个解时，$X_{j}=1$ ，否则，$X_{j}=0$ 。算法返回 $S \equiv N \times \sum_{j} X_{j} / k$ 作为解的个数的估计值。证明 $S$ 的标准差为 $\Delta S=\sqrt{M(N-M) / k}$ 。证明要至少以 $3 / 4$ 的概率估计 $M$ ，并保持误差在 $\sqrt{M}$ 以内，则必须有 $k=\Omega(N)$ 次 oracle 调用。
习题6.14 证明任意经典计数算法，若要以至少 $3 / 4$ 的概率估计 $M$ ，并保持误差在 $c \sqrt{M}$ 以内 （ $c$ 是一个确定的常数），则必须对 oracle 进行 $\Omega(N)$ 次调用。
量子计数是应用 5.2 节的相位估计过程来估计 Grover 迭代算子 $G$ 的特征值，进而使得我们可以确定搜索问题中解的个数 $M_{\circ}$ 假设 $|a\rangle$ 和 $|b\rangle$ 是在由 $|\alpha\rangle$ 和 $|\beta\rangle$ 张成的空间中 $G$ 的两个特征向量。设 $\theta$ 为 $G$ 作用下旋转的角度。由式（6.13），我们可以看到对应的特征值为 $\mathrm{e}^{\mathrm{i} \theta}$ 和 $\mathrm{e}^{\mathrm{i}(2 \pi-\theta)}$ 。便于分析，假设 oracle已经如 6.1 节所述被扩展，将搜索空间扩展到 $2 N$ ，并确保 $\sin {}^{2}(\theta / 2)=M / 2 N$ 。
用于量子计数的相位估计电路如图 6－7 所示。该电路的功能是估计 $\theta$ 精确至 $m$ 位，成功概率至少为 $1-\epsilon$ 。如每一个相位估计算法一样，第一个寄存器包含 $t \equiv m+\lceil\log (2+1 / 2 \epsilon)\rceil$ 个量子比特，而第二个寄存器包含 $n+1$ 个量子比特，足以在扩展后的搜索空间中实现 Grover 迭代。使用阿达玛变换将第二个寄存器的状态初始化为所有可能输人的均匀叠加态 $\sum_{x}|x\rangle_{\circ}$ 。如 6.1 节所述，这个态是特征态 $|a\rangle$ 和 $|b\rangle$ 的叠加，因此由 5.2 节中的结果，图 6－7 中的电路以至少 $1-\epsilon$ 的概率给出 $\theta$ 或 $2 \pi-\theta$ 的估计，精度在 $|\Delta \theta| \leqslant 2^{-m}$ 之内。进一步，对 $2 \pi-\theta$ 与 $\theta$ 在同一精度水平上的估计显然是等价的，因此相位估计算法以至少 $1-\epsilon$ 的概率确定 $\theta$ ，精度在 $2^{-m}$ 以内。
图 6－7 在量子计算机上执行近似量子计数的电路图
利用 $\sin {}^{2}(\theta / 2)=M / 2 N$ 和对 $\theta$ 的估计，我们可以估计解的数目 $M$ 。这样估计的误差 $\Delta M$会有多大呢？
$$ \begin{align*} \frac{|\Delta M|}{2 N} & =\left|\sin {}^{2}\left(\frac{\theta+\Delta \theta}{2}\right)-\sin {}^{2}\left(\frac{\theta}{2}\right)\right| \tag{6.30}\\ & =\left(\sin \left(\frac{\theta+\Delta \theta}{2}\right)+\sin \left(\frac{\theta}{2}\right)\right)\left|\sin \left(\frac{\theta+\Delta \theta}{2}\right)-\sin \left(\frac{\theta}{2}\right)\right| \tag{6.31} \end{align*} $$
计算结果表明 $|\sin ((\theta+\Delta \theta) / 2)-\sin (\theta / 2)| \leqslant|\Delta \theta| / 2$ ，且由基本的三角不等式可以得到 $\mid \sin ((\theta+$ $\Delta \theta) / 2)|\leqslant \sin (\theta / 2)+|\Delta \theta| / 2$ ，因此
$$ \begin{equation*} \frac{|\Delta M|}{2 N} < \left(2 \sin \left(\frac{\theta}{2}\right)+\frac{|\Delta \theta|}{2}\right) \frac{|\Delta \theta|}{2} \tag{6.32} \end{equation*} $$
代人 $\sin {}^{2}(\theta / 2)=M / 2 N$ 和 $|\Delta \theta| \leqslant 2^{-m}$ ，我们可以得到最终的误差估计
$$ \begin{equation*} |\Delta M| < \left(\sqrt{2 M N}+\frac{N}{2^{m+1}}\right) 2^{-m} \tag{6.33} \end{equation*} $$
举一个例子，设取 $m=\lceil n / 2\rceil+1, ~ \epsilon=1 / 6$ ，则有 $t=\lceil n / 2\rceil+3$ ，从而算法需要进行 $\Theta(\sqrt{N})$ 次 Grover 迭代，进而 oracle 的调用次数为 $\Theta(\sqrt{N})$ 。由式（6.33）可知精确度为 $|\Delta M| < \sqrt{M / 2}+1 / 4=$ $O(\sqrt{M})$ 。将这个结果与习题 6.14 进行比较，其中表明经典计算机要达到同样的精度需要 $O(N)$次 oracle 调用。
事实上，刚才提到的例子还有另一个作用，确定搜索问题的解是否存在，即 $M=0$ 或 $M \neq 0$ 。若 $M=0$ ，则有 $|\Delta M| < 1 / 4$ ，从而算法必须以至少 $5 / 6$ 的概率给出估计 0 。反之，若 $M \neq 0$ ，则容易验证算法至少以 $5 / 6$ 的概率估计出 $M$ 不为 0 。
量子计数的另一个应用是找到解个数 $M$ 未知情况下搜索问题的解。如 6.1 节所述，应用量子搜索算法的难点在于重复 Grover 迭代的次数，式（6.15），依赖于知道解的个数 $M$ 。这个问题可以在一定程度上被解决，先使用基于相位估计的量子计数算法，以高精度估计 $\theta$ 和 $M$ ，然后再应用 6.1 节中的量子搜索算法，重复 Grover 迭代的次数由式（6.15）决定，其中的 $\theta$ 和 $M$ 替换成通过相位估计得来的值，$R$ 就可以确定下来了。这种情况下角度误差最多为 $\pi / 4(1+|\Delta \theta| / \theta)$ ，因此像之前一样取 $m=\lceil n / 2\rceil+1$ ，则角误差最多为 $\pi / 4 \times 3 / 2=3 \pi / 8$ ，相应的搜索算法成功概率至少为 $\cos {}^{2}(3 \pi / 8)=1 / 2-1 / 2\sqrt{2} \approx 0.15$ 。若以此精度获得 $\theta$ 的概率为 $5 / 6$ ，如前面的例子所示，那么获得搜索问题一个解的概率就是 $5 / 6 \times \cos {}^{2}(3 \pi / 8) \approx 0.12$ ，这个概率通过重复计数－搜索组合过程多次很快可以逼近1。
量子搜索也许可以被用于加速求解在复杂性类 NP（3.2.2 节）中的问题。在 6.1.1节中我们已经看到因子分解问题是如何被加速的。这里，我们说明如何利用量子搜索求解哈密顿回路问题 （ HC ）。回顾一下，一个图的哈密顿回路是遍历该图所有顶点的一个简单回路。 HC 问题即确定给定的图中是否存在哈密顿回路。这个问题属于 NP 完全问题，通常认为（未被证明）在经典计算机上是难解的。
求解 HC 的一个简单的算法是遍历所有可能的点的排序：
1.生成每一种可能的点的排序 $\left(v_{1}, \cdots, v_{n}\right)$ 。允许重复，这样方便分析且不会影响实质结果。
2.对每一种生成的排序，检测它是否是图的哈密顿回路。若不是，检测下一个排序。
一共有 $n^{n}=2^{n \log n}$ 种可能的排序需要被搜索，最坏情况下这个算法需要进行 $2^{n \log n}$ 次哈密顿回路的性质检测。的确，任何 NP 中的问题都可以以类似的方法来求解：规模为 $n$ 的问题如果有 $\omega(n)$ 比特给定的证据，$\omega(n)$ 是 $n$ 的多项式，那么搜索所有 $2^{\omega(n)}$ 个可能的证据就会找到一个解（若解存在的话）。
量子搜索算法可以用来加快搜索速度，从而加速这个算法。特别地，我们用 6.3 节描述的算法确定搜索问题的解是否存在。令 $m \equiv\lceil\log n\rceil$ 。算法的搜索空间将表示成一个 $m n$ 量子比特的串，每个 $m$ 量子比特的块被用于存放单个顶点的索引。因此，我们可以写出计算基 $\left|v_{1}, \cdots, v_{n}\right\rangle$ ，其中每个 $\left|v_{i}\right\rangle$ 用对应的 $m$ 个量子比特来表示，一共是 $n m$ 个量子比特。搜索算法的 oracle须用如下变换：
$$ O\left|v_{1}, \cdots, v_{n}\right\rangle= \begin{cases}\left|v_{1}, \cdots, v_{n}\right\rangle & \text { 若 } v_{1}, \cdots, v_{n} \text { 不是一个哈密顿回路 } \tag{6.34}\\ -\left|v_{1}, \cdots, v_{n}\right\rangle & \text { 若 } v_{1}, \cdots, v_{n} \text { 是一个哈密顿回路 }\end{cases} $$
当图给定时，这样的 oracle 是很容易设计和实现的。首先用一个多项式规模的经典电路识别哈密顿回路，进而把它转换成一个可逆电路，也是多项式规模的，计算变换 $\left(v_{1}, \cdots, v_{n}, q\right) \rightarrow$ $\left(v_{1}, \cdots, v_{n}, q \oplus f\left(v_{1}, \cdots, v_{n}\right)\right)$ ，其中 $f\left(v_{1}, \cdots, v_{n}\right)=1$ ，若 $v_{1}, \cdots, v_{n}$ 是一个哈密顿回路，否则为 0 。用量子计算机实现相应的电路，使最后一个量子比特开始处于状态 $(|0\rangle-|1\rangle) / \sqrt{2}$ 就得到需要的变换。我们在这里不具体讨论细节，除了要注意一个关键点：oracle 需要的门的个数是 $n$的多项式的，这可由哈密顿回路可以被多项式规模的经典电路识别这一事实直接得到。应用确定解是否存在的搜索算法变型（见 6.3 节），我们看到，判定是否存在哈密顿回路需要调用 oracle $O\left(2^{m n / 2}\right)=O\left(2^{n\lceil\log n\rceil / 2}\right)$ 次。当存在时，再结合计数－搜索算法可以找到一个这样的回路，作为问题的一个证据。
总结如下：
－经典算法需要 $O\left(p(n) 2^{n[\log n]}\right)$ 次操作确定哈密顿回路是否存在，其中多项式因子 $p(n)$ 主要是实现 oracle 的开销，即判定一个候选路径是否为是哈密顿回路的门的个数。决定算法所需资源的核心要素是 $2^{n\lceil\log n\rceil}$ 中的幂。经典算法是确定性的，即成功概率为 1 。
－量子算法需要 $O\left(p(n) 2^{n\lceil\log n\rceil / 2}\right)$ 次操作确定哈密顿回路是否存在。同样地，多项式 $p(n)$ 主要是实现 oracle 的开销。决定算法所需资源的核心要素是 $2^{n\lceil\log n\rceil / 2}$ 中的幂。存在一个常数的出错概率（如 $1 / 6$ ），重复 $r$ 次可以被减少至 $1 / 6^{r}$ 。
－渐进地，量子算法需要的操作数目是经典算法的平方根。
假设有人给你一个包含一千种花名的清单，并问你＂Perth Rose＂在清单的什么位置。如果这一花名在清单中恰好出现一次，且清单没有明显的排序规律，那么你需要平均查找 500 次才能找到＂Perth Rose＂。这种数据库搜索问题可以用量子搜索算法来加速吗？确实，量子搜索算法有时也称为数据库搜索算法，但它的效用性在该应用上是有限的，并且依赖于特定的假设。本节我们
来看一下，在非常类似于经典计算机的场景下，量子搜索算法如何在概念上用于搜索非结构化的数据库。我们描述的框架将阐明用一台量子计算机去搜索经典数据库需要消耗多少资源。
假设我们有一个数据库包含 $N \equiv 2^{n}$ 个元素，每个元素的长度为 $l$ 比特。我们给它们编号为 $d_{1}, \cdots, d_{N}$ 。我们想要去确定一个特定的 $l$ 比特串 $s$ 是否在数据库中。经典计算机求解这个问题，可以分为两部分，如图 6－8 所示。一个是中央处理单元，或者叫 CPU，利用较小的临时存储对数据进行处理。第二部分是大的内存，把数据库存放在 $2^{n}$ 个块中，每块含 $l$ 比特。假设内存是被动的，即它本身不可以处理数据。允许的是从内存中加载数据（LOAD）到 CPU，将 CPU 的数据存储（STORE）到内存中，以及在 CPU 中处理数据。当然，经典内存计算机可能有不同的设计，但这种 CPU－内存的划分是一种流行和常见的架构。
$N l$ 比特内存
STORE
图 6－8 由独立中央处理单元（CPU）和内存组成的经典计算机上的数据库搜索。在内存上只允许直接进行两种操作——个内存单元可以被加载（LOAD）进 CPU，或者 CPU 中的数据可以存人（STORE）内存中
为了找到给定的串 $s$ 在数据库中的哪个位置，最有效的经典算法如下。首先，在 CPU 中对数据库建立一个 $n$ 比特的索引。我们假设 CPU 的空间足以存放 $n \equiv\lceil\log N\rceil$ 个比特的索引。索引从 0 开始，每次迭代增加 1 。在每次迭代中，数据库中与该索引对应的元素会被加载进 CPU 中，然后和目标串进行比较。如果是一样的，算法输出索引值并且终止。否则，算法继续增大索引值。显然，在最坏情况下算法需要从内存中加载数据 $2^{n}$ 次，并且在这种计算模型下，这也是可能的最有效的算法了。
量子计算机上对应的算法效率如何呢？再者，尽管量子加速是可能的，这样的算法有多少用处呢？我们先阐明加速是可能的，然后再回到算法用途的问题。假设我们的量子计算机包含两个单元，CPU 和内存，就像经典计算机一样。设 CPU 含 4 个寄存器：（1）一个初始化为 $|0\rangle$ 的 $n$ 量子比特的＂索引寄存器＂；（2）一个初始化为 $|s\rangle$ 的 $l$ 量子比特的寄存器，并且在整个计算中维持这个态；（3）一个初始化为 $|0\rangle$ 的 $l$ 量子比特的＂数据＂寄存器；（4）一个初始化为 $(|0\rangle-|1\rangle) / \sqrt{2}$的 1 量子比特的寄存器。
内存单元可以用以下两种方式之一来实现。最简单的是量子内存，包含 $N=2^{n}$ 个 $l$ 量子比
$l$ 经典比特的单元，每个单元包含数据库元素 $d_{x}$ 。不过，与传统经典内存不同，它可以用一个处于多值叠加的索引 $x$ 进行寻址。这个量子索引，允许从内存中加载叠加的单元数据。内存存取按如下方式工作：若 CPU 的索引寄存器处于状态 $|x\rangle$ ，数据寄存器处于状态 $|d\rangle$ ，则第 $x$ 个内存单元的内容 $d_{x}$ 被加载进数据寄存器：$|d\rangle \rightarrow\left|d \oplus d_{x}\right\rangle$ ，其中加是按位模 2 加。首先，我们看看如何利用该能力执行量子搜索算法，然后讨论如何在物理上构造这种内存。
实现量子搜索算法的关键部分在于 oracle 的实现，它必须翻转在内存中定位 $s$ 的索引的相
位。假设 CPU 处于状态
$$ \begin{equation*} |x\rangle|s\rangle|0\rangle \frac{|0\rangle-|1\rangle}{\sqrt{2}} \tag{6.35} \end{equation*} $$
使用LOAD操作，使计算机处于状态
$$ \begin{equation*} |x\rangle|s\rangle\left|d_{x}\right\rangle \frac{|0\rangle-|1\rangle}{\sqrt{2}} \tag{6.36} \end{equation*} $$
现在，第 2 和第 3 寄存器进行比较，若它们是相同的，那么对第 4 寄存器进行比特翻转；否则不做改变。该操作的效果是
$$ |x\rangle|s\rangle\left|d_{x}\right\rangle \frac{|0\rangle-|1\rangle}{\sqrt{2}} \rightarrow \begin{cases}-|x\rangle|s\rangle\left|d_{x}\right\rangle \frac{|0\rangle-|1\rangle}{\sqrt{2}} & \text { 若 } d_{x}=s \tag{6.37}\\ |x\rangle|s\rangle\left|d_{x}\right\rangle \frac{|0\rangle-|1\rangle}{\sqrt{2}} & \text { 若 } d_{x} \neq s\end{cases} $$
然后通过再次执行LOAD操作使数据存储器恢复至状态 $|0\rangle$ 。oracle的总体作用使寄存器 $2, ~ 3, ~ 4$ 不受影响，并且和第 1 寄存器没有纠缠。因此，总的效果是将寄存器 1 的状态由 $|x\rangle$ 变为 $-|x\rangle$ ，若 $d_{x}=s$ ，否则不受影响。用这样的方式实现 oracle，我们可以应用量子搜索算法确定 $s$ 在数据库中的位置，只使用 $O(\sqrt{N})$ 次 LOAD操作，而相比之下，经典算法需要 $N$ 次LOAD操作。
为了使 oracle 在叠加的情况下也能正确工作，看起来似乎内存也需要是量子的。事实上，如上所述，在一些条件下内存可以以经典方式实现，并且这样看起来更容易抵抗噪声的影响。但是一个量子寻址机制仍然是需要的，图 6－9 给出了如何做到这点的示意图。操作的原理是，把量子索引的二进制编码态（其中 0 到 $2^{n}-1$ 由 $n$ 个量子比特表示）转化成寻址经典数据库的一元编码 （其中 0 到 $2^{n}-1$ 由具有 $2^{n}$ 个可能位置的单个探头的位置表示）。数据库的改变是在探头与其位置不相关的自由度上做出，然后逆转二进制到一元编码的过程，在数据寄存器留下希望的内容。
有量子搜索算法用于搜索经典数据库的实例吗？有两个不同的方面需要说明。首先，实际中的数据库通常不是无结构的。一些简单的数据库，像我们在本节讨论的例子中那个包含花名的数据库，也许是依照字母序组织的，这样对于一个 $N$ 元数据库，使用二分查找便可以在 $O(\log (N))$时间内确定元素的位置。然而，某些数据库也许需要复杂得多的结构；另外，尽管存在一些复杂的技术能将经典搜索进行优化，但是对于足够复杂和意料之外的查询，预先知道数据库的结构也许不能带来什么帮助，这样的问题实质上可以被看作我们讨论的无结构数据库搜索问题。
其次，对于一台可以被用于搜索经典数据库的量子计算机，量子寻址方案是需要的。我们描述的方案需要 $O(N \log N)$ 个量子开关，这与将用于存放数据库的硬件数量大致相同。也许将来有一天，这些量子开关会变得与经典内存单元一样简单和便宜，但如果不是那样，建造量子计算机来执行量子搜索，与用分布在内存单元中的经典计算硬件相比，可能就不够经济。
基于这些考虑，似乎量子搜索算法的主要应用将不在经典数据库搜索。反而，也许会被用于寻找困难问题的解，例如前一节所讨论的哈密顿回路问题，旅行商问题和可满足性问题。
图 6－9 带有 5 量子比特寻址机制的 32 经典内存单元的示意图。每一个圈表示一个开关，由圈内标识的量子比特进行寻址。例如，当 $\left|x_{4}\right\rangle=|0\rangle$ 时，相应的开关把输人量子比特接通到左边；当 $\left|x_{4}\right\rangle=|1\rangle$时，开关把输人量子比特接通到右边。若 $\left|x_{4}\right\rangle=(|0\rangle+|1\rangle) / \sqrt{2}$ ，则取两条路径的均衡叠加。数据寄存器的量子比特从树顶进人，并按路径下达数据库，根据内存单元的内容改变自身的状态。量子比特然后回到一个确定的位置，并携带检索的信息。物理上，这可以使用比如单光子作为数据寄存器量子比特来实现，它们可以用非线性干涉仪（见第 7 章）来控制。经典数据库可以是一片简单的塑料薄膜，其中＂0＂（以白色方块表示）让光无变换地透过，而＂ 1 ＂（带阴影的方块）把光的极性改变 $90^{\circ}$
我们证明了量子计算机只需调用 oracle $O(\sqrt{N})$ 次，就可以搜索 $N$ 个元素的数据集。现在我们证明没有量子算法可以用少于 $\Omega(\sqrt{N})$ 的查询次数完成此任务，因此所给出的算法是最优的。
假设算法的初始状态为 $|\psi\rangle$ 。为了简便，我们证明搜索问题只有一个解 $x$ 时的复杂度下界。为了找到 $x$ ，我们可以使用 oracle $O_{x}=I-2|x\rangle\langle x|$ ，它把解 $|x\rangle$ 前面的相位变成 -1 ，而其他状态保持不变。我们假设算法从状态 $|\psi\rangle$ 开始，作用 oracle $O_{x} k$ 次，并在查询操作之间穿插西变换 $U_{1}, U_{2}, \cdots, U_{k}$ 。定义
$$ \begin{align*} \left|\psi_{k}^{x}\right\rangle & \equiv U_{k} O_{x} U_{k-1} O_{x} \cdots U_{1} O_{x}|\psi\rangle \tag{6.38}\\ \left|\psi_{k}\right\rangle & \equiv U_{k} U_{k-1} \cdots U_{1}|\psi\rangle \tag{6.39} \end{align*} $$
即，$\left|\psi_{k}\right\rangle$ 是施加西操作 $U_{1}, U_{2}, \cdots, U_{k}$ 后的结果状态，没有用到 oracle。令 $\left|\psi_{0}\right\rangle=|\psi\rangle$ 。我们的目标是给以下量定界：
$$ \begin{equation*} D_{k} \equiv \sum_{x}\left|\psi_{k}^{x}-\psi_{k}\right|^{2} \tag{6.40} \end{equation*} $$
为了方便简化公式，我们用符号 $\psi$ 代表 $|\psi\rangle$ 。直观地，$D_{k}$ 是经由 oracle 作用 $k$ 步引起的偏差的度量，如果这个量很小，则所有的状态 $\left|\psi_{k}^{x}\right\rangle$ 大致上是相同的，那么就不可能以很高的概率正确地识别出 $x$ 。证明的策略是说明两件事：（a）$D_{k}$ 的上界不会超过 $O\left(k^{2}\right)$ ；（b）为区分 $N$ 个不同项，$D_{k}$ 必须是 $\Omega(N)$ 的。结合这两个结果给出所期望的下界。
首先，我们用归纳法证明 $D_{k} \leqslant 4 k^{2}$ 。对于 $k=0$ 时，$D_{k}=0$ ，显然成立。注意到
$$ \begin{align*} D_{k+1} & =\sum_{x}\left|O_{x} \psi_{k}^{x}-\psi_{k}\right|^{2} \tag{6.41}\\ & =\sum_{x}\left|O_{x}\left(\psi_{k}^{x}-\psi_{k}\right)+\left(O_{x}-I\right) \psi_{k}\right|^{2} \tag{6.42} \end{align*} $$
使用不等式 $|b+c|^{2} \leqslant|b|^{2}+2|b||c|+|c|^{2}$ ，代人 $b \equiv O_{x}\left(\psi_{k}^{x}-\psi_{k}\right)$ 和 $c \equiv\left(O_{x}-I\right) \psi_{k}=$ $-2\left\langle x \mid \psi_{k}\right\rangle|x\rangle$ ，得到
$$ \begin{equation*} D_{k+1} \leqslant \sum_{x}\left(\left|\psi_{k}^{x}-\psi_{k}\right|^{2}+4\left|\psi_{k}^{x}-\psi_{k}\right| |\left.\left\langle x \mid \psi_{k}\right\rangle|+4|\left\langle\psi_{k} \mid x\right\rangle\right|^{2}\right) \tag{6.43} \end{equation*} $$
对不等号右边第二项应用柯西－施瓦茨不等式，并注意 $\sum_{x}\left|\left\langle x \mid \psi_{k}\right\rangle\right|^{2}=1$ ，得到
$$ \begin{align*} D_{k+1} & \left.\leqslant D_{k}+4\left(\sum_{x} | \psi_{k}^{x}-\psi_{k}^{2}\right) |^{2}\right)^{\frac{1}{2}}\left(\sum_{x^{\prime}}\left|\left\langle\psi_{k} \mid x^{\prime}\right\rangle\right|^{2}\right)^{\frac{1}{2}}+4 \tag{6.44}\\ & \leqslant D_{k}+4\sqrt{D_{k}}+4\tag{6.45} \end{align*} $$
由归纳假设 $D_{k} \leqslant 4 k^{2}$ ，我们得到
$$ \begin{equation*} D_{k+1} \leqslant 4 k^{2}+8 k+4=4(k+1)^{2} \tag{6.46} \end{equation*} $$
归纳完成。
为了完成证明，我们需要证明：仅当 $D_{k}$ 是 $\Omega(N)$ 的，才能以高概率成功。假设 $\left|\left\langle x \mid \psi_{k}^{x}\right\rangle\right|^{2} \geqslant 1 / 2$对于所有 $x$ 成立，则成功得到解的概率至少是 $1 / 2$ 。将 $|x\rangle$ 替换成 $\mathrm{e}^{\mathrm{i} \theta}|x\rangle$ 不会改变成功概率，因此不失一般性，我们假设 $\left\langle x \mid \psi_{k}^{x}\right\rangle=\left|\left\langle x \mid \psi_{k}^{x}\right\rangle\right|$ ，因此
$$ \begin{equation*} \left|\psi_{k}^{x}-x\right|^{2}=2-2\left|\left\langle x \mid \psi_{k}^{x}\right\rangle\right| \leqslant 2-\sqrt{2} \tag{6.47} \end{equation*} $$
$\sum_{x}\left|x-\psi_{k}\right|^{2}$ ，则有
$$ \begin{align*} D_{k} & =\sum_{x}\left|\left(\psi_{k}^{x}-x\right)+\left(x-\psi_{k}\right)\right|^{2} \tag{6.48}\\ & \geqslant \sum_{x}\left|\psi_{k}^{x}-x\right|^{2}-2\sum_{x}\left|\psi_{k}^{x}-x\right|\left|x-\psi_{k}\right|+\sum_{x}\left|x-\psi_{k}\right|^{2} \tag{6.49}\\ & =E_{k}+F_{k}-2\sum_{x}\left|\psi_{k}^{x}-x\right|\left|x-\psi_{k}\right| \tag{6.50} \end{align*} $$
应用柯西－施瓦茨不等式可以得到 $\sum_{x}\left|\psi_{k}^{x}-x\right|\left|x-\psi_{k}\right| \leqslant \sqrt{E_{k} F_{k}}$ ，因此有
$$ \begin{equation*} D_{k} \geqslant E_{k}+F_{k}-2\sqrt{E_{k} F_{k}}=\left(\sqrt{F_{k}}-\sqrt{E_{k}}\right)^{2} \tag{6.51} \end{equation*} $$
在习题 6.15 中将会证明 $F_{k} \geqslant 2 N-2\sqrt{N}$ 。再结合 $E_{k} \leqslant(2-\sqrt{2}) N$ 可以得到 $D_{k} \geqslant c N$ 对于足够大的 $N$ 成立，$c$ 是不超过 $(\sqrt{2}-\sqrt{2-\sqrt{2}})^{2} \approx 0.42$ 的常量。因为 $D_{k} \leqslant 4 k^{2}$ ，这表明
$$ \begin{equation*} k \geqslant \sqrt{c N / 4} \tag{6.52} \end{equation*} $$
总的来说，若想以至少一半的概率找到搜索问题的解，则必须进行 $\Omega(\sqrt{N})$ 次 oracle 查询。
习题 6.15 使用柯西－施瓦茨不等式证明对于任意归一化状态向量 $|\psi\rangle$ 和 $N$ 个标准正交向量 $|x\rangle$ ，
$$ \begin{equation*} \sum_{x}|\psi-x|^{2} \geqslant 2 N-2\sqrt{N} \tag{6.53} \end{equation*} $$
习题 6.16 假设解为 $x$ 的概率是均匀的，现在只要求平均出错概率小于 $1 / 2$ ，而不要求对所有的 $x$ 。证明仍然需要 $O(\sqrt{N})$ 次查询。
这个结果，即量子搜索算法实质上是最优的，既让人兴奋又让人失望。令人兴奋的是它告诉我们，对于这个问题，至少我们已经发挥了量子力学的极限，没有进一步提升的可能。令人失望的是，我们或许曾希望用量子搜索算法会取得比平方根更大的加速，可能只用 $O(\log N)$ 次 oracle查询完成对 $N$ 元空间的搜索。如果这样的算法存在，那么 NP 完全问题将能被量子计算机有效解决，因为它可以使用大致 $\omega(n)$ 次 oracle 查询，搜索所有 $2^{\omega(n)}$ 个可能的证据，其中 $\omega(n)$ 是证据的比特长度。不幸的是，这样的算法是不存在的。这对算法设计者来说是有用的信息，因为它表明简单的基于搜索的方法对于求解 NP 完全问题是不可行的。
我们在这里冒昧地发表一点看法。许多研究者相信，NP 完全问题困难性的本质在于它们的解空间本质上是无结构的，因此求解这些问题（相差一个多项式量级因子）的最好方法就是采取搜索方法。如果接受了这个观点，那么对于量子计算来说是一个坏消息，意味着量子计算机能有效求解的问题类——BQP，并不包含 NP 完全问题。当然，这仅仅是一个观点，也许 NP 完全问题包含某些未知的结构使得它们在量子计算机上可以有效求解，甚至是在经典计算机上。能够说明这一点的一个很好的例子是素因子分解问题，被认为属于 NPI 类，即 P 和 NP 完全问题之间的一个复杂性类。素因子分解问题的有效量子求解的关键是，对问题中＂隐含＂结构的利用——可
归约为求阶问题。即便揭示了这种惊人的结构，人们还是没有利用起来开发出更有效的经典算法去求解因子分解问题，尽管在量子机制下这种结构可以被用来设计有效的因子分解算法！也许类似的结构隐藏在 NPI 类的其他问题中，比如图同构问题，甚至是 NP 完全问题。
习题6.17（多目标搜索的最优性）假设搜索问题有 $M$ 个解，证明需要使用 $O(\sqrt{N / M})$ 次 oracle来找到一个解。
我们以量子搜索算法的推广来结束这一章，它有助于深刻理解量子计算能力的边界。在本章开始的时候，我们把搜索问题描述为找到一个 $n$ 比特的整数 $x$ 使函数 $f:{0,1}^{n} \rightarrow{0,1}$ 满足 $f(x)=1$ 。与此相关的是判定性问题，判定是否存在 $x$ 使得 $f(x)=1$ 。求解这个判定性问题一样困难，可以表述为计算一个布尔函数 $F(X)=X_{0} \vee X_{1} \vee \cdots \vee X_{N-1}$ ，其中 $\vee$ 表示二进制 OR 操作，$X_{k} \equiv f(k)$ ，$X$ 表示集合 $\left\{X_{0}, X_{1}, \cdots, X_{N-1}\right\}$ 。更一般地，我们可以计算 OR 之外的函数，比如 $F(X)$ 可以是 AND，PARITY（模 2 求和），或者 MAJORITY $(F(X)=1$ 当且仅当有超过一半的 $X_{k}=1$ ）。一般情况下，我们可以考虑 $F$ 是任意的布尔函数。给定计算 $f$ 的 oracle，经典的或量子的计算机可以多快地计算这些函数（用查询次数来度量）？
如果不知道函数 $f$ 的一些性质，回答这种问题似乎是困难的，但事实上即使在＂黑盒＂模型下，可以确定的东西还是很多，其中 oracle 完成任务的方式是不成问题的，复杂性用所需 oracle的查询次数来度量。在前面的章节中，搜索算法的分析说明了得到该复杂度的一种方法，但另一种更有效的获得查询复杂度的方法是多项式方法，我们接下来会简要描述。
让我们从一些有用的定义开始。确定性查询复杂度 $D(F)$ 是指在经典计算机上确定性地计算 $F$ 所需 oracle 的最少查询次数。量子情形下的对应物，$Q_{E}(F)$ ，表示在量子计算机上确定性地计算 $F$ 所需 oracle 的最少查询次数。因为量子计算机的输出具有固有的概率特性，一个更意义的量是有界误差复杂度 $Q_{2}(F)$ ，即量子计算机的输出至少以 $2 / 3$ 的概率与 $F$ 相同所需 oracle 的最少查询次数。（ $2 / 3$ 可以是任意的数——这个概率只要离 $1 / 2$ 的距离是有下界的，就可以通过重复调用使概率提升至接近 1 ）。还有一个相关的度量是零误差复杂性 $Q_{0}(F)$ ，即在如下情况下 oracle的最少查询次数：要求量子计算机产生的输出要么一定等于 $F$ ，要么以小于 $1 / 2$ 的概率不给出一个确定的结果。所有这些界必须对所有 oracle 函数 $f$ 都成立（或者换句话说，$F$ 的所有输入 $X$ ）。注意到 $Q_{2}(F) \leqslant Q_{0}(F) \leqslant Q_{E}(F) \leqslant D(F) \leqslant N$ 。
多项式方法基于布尔函数的最小次数多线性多项式表示的性质。下面考虑的多项式都是 $X_{k} \in{0,1}$ 的函数，由于 $X_{k}^{2}=X_{k}$ ，因此是多线性的。一个多项式 $p: R^{N} \rightarrow R$ ，若 $p(X)=F(X)$对于所有的 $X \in{0,1}^{N}$ 成立（其中 $R$ 表示全体实数），则称其可以表示 $F$ 。这样的多项式 $p$ 总是存在的，因为我们可以明确地构造一个合适的候选者：
$$ \begin{equation*} p(X)=\sum_{Y \in{0,1}^{N}} F(Y) \prod_{k=0}^{N-1}\left[1-\left(Y_{k}-X_{k}\right)^{2}\right] \tag{6.54} \end{equation*} $$
最小阶的 $p$ 是唯一的，这一结论作为习题 6.18 留给读者。 $F$ 这种表示的最小阶，记为 $\operatorname{deg}(F)$ ，是 $F$ 复杂性的一个有用度量。比如，已知 $\operatorname{deg}(O R), \operatorname{deg}(A N D), \operatorname{deg}$（PARITY）都等于 $N_{\circ}$ 事实上，大多数函数的最小阶都是 $N$ 。进一步地，已证明
$$ \begin{equation*} D(F) \leqslant 2\operatorname{deg}(F)^{4} \tag{6.55} \end{equation*} $$
这个结果为确定性经典算法计算大部分布尔函数确立了一个复杂度上界。将这个概念扩展，若一个多项式满足 $|p(X)-F(X)| \leqslant 1 / 3$ 对于所有 $X \in{0,1}^{N}$ 成立，我们称多项式 $p$ 近似计算 $F$ ，用 $\widetilde{\operatorname{deg}}(F)$ 表示近似多项式的最小阶。这样的度量对于随机经典算法很重要，并且后面会看到，在描述量子情形的时候也很重要。已知有 $\widetilde{\operatorname{deg}}($ PARITY $)=N$ ，
$$ \begin{equation*} \widetilde{\operatorname{deg}}(\mathrm{OR}) \in \Theta(N) \quad \text { 和 } \quad \widetilde{\operatorname{deg}}(\mathrm{AND}) \in \Theta(\sqrt{N}) \tag{6.56} \end{equation*} $$
和
$$ \begin{equation*} D(F) \leqslant 216\widetilde{\operatorname{deg}}(F)^{6} \tag{6.57} \end{equation*} $$
式（6.55）和式（6.57）的界是本书写作时的最好结果；它们的证明超出了本书的范围，不过你可以在＂背景资料与延伸阅读＂中找到更多的相关信息。一般认为更紧的界是可能的，但对于我们的目的而言，已经足够了。
习题 6.18 证明布尔函数 $F(X)$ 的最小阶多项式表示法是唯一的。
习题6.19 证明 $P(X)=1-\left(1-X_{0}\right)\left(1-X_{1}\right)\left(1-X_{2}\right) \cdots\left(1-X_{N-1}\right)$ 表示 OR。
多项式在描述量子算法的结果时自然产生。我们写出对 oracle $O$ 做了 $T$ 次查询的量子算法 $\mathcal{Q}$ 的输出为
$$ \begin{equation*} \sum_{k=0}^{2^{n}-1} c_{k}|k\rangle \tag{6.58} \end{equation*} $$
我们将证明振幅 $c_{k}$ 是关于变量 $X_{0}, X_{1}, \cdots, X_{N-1}$ 的阶不超过 $T$ 的多项式。任何算法 $\mathcal{Q}$ 可用如图 6－10 所示量子电路实现。在第一次 oracle 查询之前的状态 $\left|\psi_{0}\right\rangle$ 可写作
$$ \begin{equation*} \left|\psi_{0}\right\rangle=\sum_{i j}\left(a_{i 0 j}|i\rangle|0\rangle+a_{i 1 j}|i\rangle|1\rangle\right)|j\rangle \tag{6.59} \end{equation*} $$
其中，第一个部分对应 $n$ 量子比特的 oracle 查询，接下来的单量子比特保存 oracle 的查询结果，最后 $m-n-1$ 个量子比特是 $\mathcal{Q}$ 的工作比特。进行 oracle 查询之后，我们得到状态
$$ \begin{equation*} \left|\psi_{1}\right\rangle=\sum_{i j}\left(a_{i 0 j}|i\rangle\left|X_{i}\right\rangle+a_{i 1 j}|i\rangle\left|X_{i} \oplus 1\right\rangle\right)|j\rangle \tag{6.60} \end{equation*} $$
但因为 $X_{i}$ 要么为 0 要么为 1 ，我们可以将其重写为
$$ \begin{equation*} \left|\psi_{1}\right\rangle=\sum_{i j}\left[\left(\left(1-X_{i}\right) a_{i 0 j}+X_{i} a_{i 1 j}\right)|i 0\rangle+\left(\left(1-X_{i}\right) a_{i 1 j}+X_{i} a_{i 0 j}\right)|i 1\rangle\right]|j\rangle \tag{6.61} \end{equation*} $$
注意到在状态 $\left|\psi_{0}\right\rangle$ 中，计算基矢态的振幅关于 $X$ 的多项式次数为 0 ，而在 $\left|\psi_{1}\right\rangle$ 中相应的次数为 1 （与 $X$ 呈线性）。一个重要的观察结果是，在 oracle 前后的西操作不会改变这些多项式的次数，但每一次 oracle 调用只会使阶最多增加 1 。因此 $T$ 次查询以后，振幅是阶不超过 $T$ 的多项式。进一步，最终输出式（6.58）用计算基去测量，产生结果 $k$ 的概率为 $P_{k}(X)=\left|c_{k}\right|^{2}$ ，是 $X$ 的次数不超过 $2 T$ 的实多项式。
图 6－10 进行 $T$ 次 oracle $O$ 调用的量子算法的一般量子电路。 $U_{0}, U_{1}, U_{2}, \cdots, U_{T}$ 是 $m$ 个量子比特上的任意西操作，oracle 作用在 $n+1$ 个量子比特上
得到结果1的概率 $P(X)$ 的阶最多也是 $2 T$ ，因为它是多项式 $P_{k}(X)$ 的一个子集和。在 $\mathcal{Q}$ 百分之百产生正确答案的情形中，必须有 $P(X)=F(X)$ ，从而 $\operatorname{deg}(F) \leqslant 2 T$ ，因此有
$$ \begin{equation*} Q_{E}(F) \geqslant \frac{\operatorname{deg}(F)}{2} \tag{6.62} \end{equation*} $$
在 $\mathcal{Q}$ 以有界差错概率给出答案的情形中，$P(X)$ 近似表示 $F(X)$ ，且有 $\widetilde{\operatorname{deg}}(F) \leqslant 2 T$ ，从中我们推导出
$$ \begin{equation*} Q_{2}(F) \geqslant \frac{\widetilde{\operatorname{deg}}(F)}{2} \tag{6.63} \end{equation*} $$
结合式（6.55）和式（6.62），我们有
$$ \begin{equation*} Q_{E}(F) \geqslant\left[\frac{D(F)}{32}\right]^{1 / 4} \tag{6.64} \end{equation*} $$
类似地，结合式（6.57）和式（6.63），我们有
$$ \begin{equation*} Q_{2}(F) \geqslant\left[\frac{D(F)}{13824}\right]^{1 / 6} \tag{6.65} \end{equation*} $$
这意味着，使用黑盒计算布尔函数的时候，量子算法比经典算法，最好的情况下只有多项式加速，甚至很多时候多项式加速都不可能（因为对很多函数 $\operatorname{deg}(F)$ 是 $\Omega(N)$ 的）。另一方面，已知对于 $F=\mathrm{OR}, D(F)=N$ ，并且随机经典查询复杂度为 $R(F) \in \Theta(N)$ ，再结合式（6.63）和式（6.56），和量子搜索算法的已知性能，可知 $Q_{2}(F) \in \Theta(\sqrt{N})$ 。这个平方根加速正是量子搜索算法所达到
的，并且多项式方法表明，这个结果或许可以推广到一类略为广泛的问题上，但若没有关于黑盒 oracle 函数 $f$ 的结构的额外信息，对经典算法的指数加速是不可能的。
习题6.20 从无差错计算函数的量子电路的输出，构造 $O R$ 的多项式表示，由此证明 $Q_{0}(O R) \geqslant$ $N$ 。
问题6.1（找最小值）像6.5节中那样，假设 $x_{1}, \cdots, x_{N}$ 是存放在内存中的一个数据集。证明只需要在量子计算机上进行 $O(\log (N) \sqrt{N})$ 次内存操作，即可以至少一半的概率找到列表中的最小元素。
问题6.2（推广的量子搜索）令 $|\psi\rangle$ 表示一个量子态，并定义 $U_{|\psi\rangle} \equiv I-2|\psi\rangle\langle\psi|$ ，即 $U_{|\psi\rangle}$ 给状态 $|\psi\rangle$ 一个 -1 的相位，并且使那些与 $|\psi\rangle$ 正交的状态不变。
1.假设我们有一个量子电路实现西操作 $U$ ，使得 $U|0\rangle^{\otimes n}=|\psi\rangle$ 。解释如何实现 $U_{|\psi\rangle}$ 。
2.令 $\left|\psi_{1}\right\rangle=|1\rangle,\left|\psi_{2}\right\rangle=(|0\rangle-|1\rangle) / \sqrt{2},\left|\psi_{3}\right\rangle=(|0\rangle-\mathrm{i}|1\rangle) / \sqrt{2}$ 。假设一个未知的 oracle $O$ 从 $U_{\left|\psi_{1}\right\rangle}, U_{\left|\psi_{2}\right\rangle}, U_{\left|\psi_{3}\right\rangle}$ 中选取。给出一个量子算法，仅使用 oracle 1 次就可以识别出这个 oracle。（提示：考虑超密编码。）
3.研究：更一般地，给定 $k$ 个状态 $\left|\psi_{1}\right\rangle, \cdots,\left|\psi_{k}\right\rangle$ ，和一个从集合 $U_{\left|\psi_{1}\right\rangle}, \cdots, U_{\left|\psi_{k}\right\rangle}$ 中选取的未知的 oracle $O$ ，需要使用该 oracle $O$ 多少次才能以高概率识别它？
问题6.3（数据库检索）给定一个量子 oracle，对 $n$ 量子比特查询（以及一个查询结果存储比特）$|k, y\rangle$ ，返回 $\left|k, y \oplus X_{k}\right\rangle$ 。证明仅使用 $N / 2+\sqrt{N}$ 次查询，就可以以很高的概率，获得 $X$ 的全部 $N=2^{n}$ 个比特。这意味着对任意 $F$ ，有一个一般的上界 $Q_{2}(F) \leqslant N / 2+\sqrt{N}$ 。
问题6.4（量子搜索和密码学）量子搜索潜在地可以用于加速密钥搜索。主要思想是在可能的解密密钥空间中进行搜索，每次搜索之后验证该密钥，看解密的信息是否合理。解释为什么这样的方法对于 Vernam 密码（见 12.6 节）不起作用。什么时候会对如 DES 这样的密码系统起作用？（想要了解 DES，可以参见［MvOV96］或［Sch96a］。）
量子搜索算法：对于一个有 $N \equiv 2^{n}$ 个元素 $M$ 个解的搜索问题，制备状态 $\sum_{x}|x\rangle$ 然后重复 $G \equiv H^{\otimes n} U H^{\otimes n} O$ 共 $O(\sqrt{N / M})$ 次，其中 $O$ 是搜索 oracle，作用是：若 $|x\rangle$ 是一个解，则 $|x\rangle \rightarrow-|x\rangle$ ，否则不变，而 $U$ 使得 $|0\rangle \rightarrow-|0\rangle$ 但对其他计算基矢态不变。测量以高概率得到搜索问题的一个解。
量子计数算法：假设一个搜索问题解的数目 $M$ 未知。 $G$ 有特征值 $\exp ( \pm \mathrm{i} \theta)$ ，其中 $\sin {}^{2}(\theta / 2)=$ $M / N$ 。基于傅里叶变换的相位估计的过程允许我们只使用 $O(\sqrt{N})$ 次 oracle 就能以高精度估计 $M$ 。反过来，量子计数使得我们可以确定一个给定的搜索问题是否有解；若有解的话找到其中一个解，即使在解的数目未知的情况下。
多项式界：对于全函数 $F$ 的计算问题（与之相对的还有部分函数，或者叫承诺问题），量子算法比起经典算法不会有超过多项式的加速。特别地，$Q_{2}(F) \geqslant[D(F) / 13824]^{1 / 6}$ 。此外，量子搜索算法的性能是最优的：它是 $\Theta(\sqrt{N})$ 的。
量子搜索算法与更多进一步发展及详细阐述归功于 Grover ${ }^{[G r o 96, ~ G r o 97]}$ 。Boyer，Brassard，Høyer和 Tapp ${ }^{[8 B H T 98]}$ 写了一篇有影响力的文章，文章中他们讨论了搜索问题存在多个解的情形，并且简述了量子计数算法，后来被 Brassard，Høyer 和 Tapp ${ }^{[8 H T 98]}$ 进行了细化，Mosca ${ }^{[\text {Mos } 98]}$ 也从相位估计的角度研究了该算法。Grover 迭代可以被理解为两次反射的乘积，由 Aharonov ${ }^{[A h a 99 b]}$ 首先在一篇综述中指出。连续时间哈密顿量（式（6.18））首先由 Farhi 和 Gutmann ${ }^{[F G 98]}$ 进行研究，从与我们在 6.2 节中的描述非常不同的一个角度。Bennett，Bernstein，Brassard 和 Vazirani ${ }^{[B B B V 97]}$ 证明 Grover 算法是最优的基于 oracle 的搜索算法。我们给出的证明是基于 Boyer，Brassard，Høyer和 Tapp ${ }^{[8 B H T 98]}$ 的结果。Zalka ${ }^{[Z a l 99]}$ 精炼了这个证明，指出量子捜索算法是渐进和精确的最优。
估计量子算法能力的多项式方法由 Beals，Buhrman，Cleve，Mosca 和 de Wolf ${ }^{\left[\mathrm{BBC}^{+} 98\right]}$ 引入量子计算领域。Mosca 的博士论文［Mos99］中也进行了精彩的讨论， 6.7 节的很多讨论也基于此。该节中引用的很多结果未给出证明；其中，式（6.55）归功于文献［ $\mathrm{BBC}^{+} 98$ ］中提及的 Nisan 和 Smolensky，但是尚末发表，式（6.56）由 Paturi ${ }^{[P a t 92]}$ 的理论导出，而式（6.57）由 $\left[\mathrm{BBC}^{+} 98\right]$ 导出。一个比式（6.65）更好的界在 $\left[\mathrm{BBC}^{+} 98\right]$ 中给出，但是需要如块敏感度复杂性（block sensitivity）等概念，超出了本书的范围。一个完全不同的给量子黑盒算法定界的方法，基于对纠缠的讨论，由 Ambainis ${ }^{[A m b 00]}$ 给出。
问题 6.1 来自于 Dürr 和 Høyer ${ }^{[\mathrm{DH} 96]}$ ，问题 6.3 来自于 van Dam ${ }^{[\text {［van98a］。 }}$