概述#
对于无结构的搜索问题，Grover 算法相较于经典算法从理论上提供了平方根级别的加速。
无结构搜索问题#
无结构搜索问题可以形式化为：
经典搜索问题：
Input: 问题的规模 \(n \in \mathbb{N} \)，一个能够执行函数 \(f: \{0,1\}^n \rightarrow \{0,1\}\) 的 Oracle.
Output: 一个满足 \(f(\mathbf{x})=1\) 的string \(\mathbf{x}\).
这个问题可以有一些变体，例如我们可以先验设定问题解的数量（不存在解，只有唯一解，存在多个解等）。
限制函数的输入域为 \(\mathbb{Z}_{2^n}\) 并不会缩小或特化问题适用的范围，但可以帮助我们简化问题。对于任意的 \(N \in \mathbb{Z}_{2^n}\) 和任意函数 \(f: \mathbb{Z}_N \rightarrow \{0, 1\}\)，我们可以将 \(\mathbb{Z}_N\) 嵌入到 \(\mathbb{Z}_{2^n}\,|\, n = [\log_2 N]\) 中，并规定超出范围的输入返回0。
很容易想象到，在经典计算机上求解此问题，在最坏的情形下，需要调用Oracle \(2^n\) 次（遍历整个问题空间，理论上界）。但量子计算机上执行的 Grover 算法能够提供平方根级的加速，将调用次数的理论上界减少至 \(2^{n-1}\)。
Grover 算法#
我们此处设定问题解的数量是有限的。Grover算法需要两个寄存器：寄存器1包含 \(n\) 个量子比特，用于存储数据信息；寄存器2包含一个量子比特，用以存储条件函数 \(f(x)\) 的值。首先将寄存器1中的量子比特制备至最大叠加态（利用 \(H^{\otimes n}\)），寄存器2制备到 \(\ket{-}\) 态。因此，整个系统初始处于量子态： $$ \ket{\Phi_0} = \frac{1}{\sqrt{N}} \sum_{\mathbf{x}\in \{0,1\}^n} \ket{\mathbf{x}} \otimes \ket{-} $$
Grover算法使用一个酉算符 \(U_f\) 实现搜索算法中的函数 \(f\)，定义为： $$ U_f : \mathcal{H}^n \otimes \mathcal{H}^1 \rightarrow \mathcal{H}^n \otimes \mathcal{H}^1 $$ $$ U_f \ket{\mathbf{x}}\ket{y} = \ket{\mathbf{x}} \ket{f(\mathbf{x}) \oplus y} = \ket{\mathbf{x}} X^{f(\mathbf{x})} \ket{y} $$
基于此，我们可以定义无结构搜索问题的量子版本：
量子搜索问题：
Input: 问题的规模 \(n \in \mathbb{N} \)，一个能够实现上述 \(U_f\) 的 Oracle。 \(M=|f^{-1}(1)|, M>0\)
Output: 一个满足 \(f(\mathbf{x})=1\) 的string \(\mathbf{x}\).
我们下面说明，直接测量寄存器1即可得到结果。寄存器1的量子态可以写为： $$ \ket{s} = \frac{1}{\sqrt{N}} \sum_{\mathbf{x}\in \{0,1\}^n} \ket{\mathbf{x}} $$
我们设定： $$ \ket{s_0} = \frac{1}{\sqrt{N}} \sum_{\mathbf{x}\in \{0,1\}^n, f(\mathbf{x})=0} \ket{\mathbf{x}} $$ $$ \ket{s_1} = \frac{1}{\sqrt{N}} \sum_{\mathbf{x}\in \{0,1\}^n, f(\mathbf{x})=1} \ket{\mathbf{x}} $$ $$ \theta = \arcsin{\sqrt{M/N}} $$
那么我们可以将寄存器1的量子态写为： $$ \ket{s} = \sqrt{\frac{N-M}{N}} \ket{s_0} + \sqrt{\frac{M}{N}} \ket{s_1} = \cos{\theta}\ket{s_0} + \sin{\theta} \ket{s_1} $$
在 \(\mathcal{H}^n\) 的计算基上测量 \(\ket{s}\)，就可以得到获得满足 \(f(\mathbf{x})=1\) 的 \(\mathbf{x}\) 的概率： $$ p = \sin^2{\theta} = \frac{M}{N} $$ 这代表了正确得到搜索问题解的概率，相比经典策略并没有提供任何优势。
为了找出可能存在的量子优势，我们需要一种称为“振幅放大”的技术，这可以提高目标态 \(\ket{s_1}\) 的振幅从而增大获得正确答案的概率。振幅放大操作需要利用一种称为 Grover 迭代器的酉算符 \(G\)，定义为： $$ G (\cos{\alpha}\ket{s_0} + \sin{\alpha} \ket{s_1}) = \cos{(\alpha+2\theta)}\ket{s_0} + \sin{(\alpha + 2 \theta)} \ket{s_1}, \forall \alpha \in \mathbb{R} $$
对寄存器1施加 \(k \in \mathbb{N_0}\) 次Grover迭代器，就可以得到： $$ G^k \ket{s} = \cos{(2k+1)\theta} \ket{s_0} + \sin{(2k+1)\theta} \ket{s_1} $$
至此，我们可以描述出 Grover 算法的整个流程（只考虑寄存器1）。首先，我们制备出初始的最大叠加态 \(\ket{s}\)，然后对 \(\ket{s}\) 施加 \(k\) 次 Grover迭代器，最后在 \(\mathcal{H}^n\) 的计算基上测量 \(\ket{s}\) 得到结果。Grover迭代器的施加次数 \(k\) 取决于 \(2(k+1)\theta\) 与 \(\pi/2\) 的接近程度，这会让得到正确解的概率最大化。
自然的我们会提出几个问题：
- Grover 迭代器怎么具体实现？特别是我们在算法输入中只给定了一个实现 \(U_f\) 操作的 Oracal。
- Grover 迭代器的最小次数是多少？我们自然希望量子线路越短越好。
- 量子方案相较于经典方案的优势在哪里？
我们将在以下几节的内容中一一给出答案。