格罗弗算法

格罗弗算法（英语：Grover's algorithm）是一种量子算法，于1996年由计算机科学家洛夫·格罗弗提出。假设现在有一个未知的函数，格罗弗算法只需测试此未知的函数 $O({\sqrt {N}})$ 次，其中 $N$ 为此未知函数的定义域的大小，即可以很高的概率找到一特定的输入值，此输入值能使此未知函数输出特定的值。

同样的问题在经典运算下，需要至少做 $O(N)$ 次测试（因为在最坏的情况下，可能第 $N$ 个定义域里的值才是正确答案）。在格罗弗发表他的算法前后，Bennett, Bernstein, Brassard, 和 Vazirani 在相近的时间证明了，任何量子算法解决此问题都最少需要对此未知的函数做 $\Omega ({\sqrt {N}})$ 次测试，因此格罗弗算法是渐进最优的。^[1]

非局域隐变量量子计算机已经被证明可以在最多 $O({\sqrt[{3}]{N}})$ 步内实现在N个条目的数据库里的搜索，这比格罗弗算法的 $O({\sqrt {N}})$ 还快，然而这些搜索算法并不能使量子计算机在多项式时间内解决NP-Complete 问题。^[2]

不像其他的量子算法可能会比相应的经典算法有指数级的加快，格罗弗算法二次方的加快，不过当 $N$ 很大时二次方的加快也相当可观。格罗弗算法可以在大约 2⁶⁴次迭代内穷举破解一个128比特的对称密钥，在大约 2¹²⁸次迭代内穷举破解一个256比特的密钥。因此，有人提倡对称密钥的长度应该加倍以因应未来的量子攻击。^[3]

像其他的量子算法一样，格罗弗算法是概率性的，意味着这个算法以小于1的概率给出正确答案。虽然实际上对于需要多少次重复才能给出正确的答案并没有一个上界，但是期望的重复次数并不随 $N$ 成长。在格罗弗发表此算法的原始论文中称此算法为数据库搜索算法，此说法至今仍普遍。此处数据库相当于是一张存有未知函数的所有输出值的表，以对应的输入值为索引。

应用

虽然格罗弗算法的用处一直被认为是数据库搜索，但是它也可以被认为是函数取反。

设置

考虑一个有N个元素的无序数据集，我们设函数 ${\displaystyle f:\{0,1,\ldots ,N-1\}\to \{0,1\}}$ 。我们假设，在所有的下标x中，有且仅有一个下标x有 $f(x)=1$ ，我们记这个下标x为 $\omega$ ，并且称 $\omega$ 为这个搜索问题的解。而格罗弗算法的目标便是找到下标 $\omega$ 。为此，我们构建一个酉算子 $U_{\omega }$ ，如下

${\displaystyle {\begin{cases}U_{\omega }|x\rangle =-|x\rangle &{\text{for }}x=\omega \\U_{\omega }|x\rangle =|x\rangle &{\text{for }}x\neq \omega \end{cases}}}$

或者可以简写为

$U_{\omega }|x\rangle =(-1)^{f(x)}|x\rangle$

事实上，我们一般构建另一种酉算子 $U_{f}$ ，如下所示

$U_{f}|x\rangle |y\rangle =|x\rangle |y\oplus f(x)\rangle$

我们一般将 $U_{f}$ 作用在态矢量和 $|-\rangle$ 的叠加态上，以实现相回传(Phase Kickback)，具体流程如下

${\begin{aligned}U_{f}|x\rangle |-\rangle &=U_{f}|x\rangle \left[{\frac {|0\rangle -|1\rangle }{\sqrt {2}}}\right]\\&={\begin{cases}{\frac {1}{\sqrt {2}}}(|x\rangle |1\rangle -|x\rangle |0\rangle )&{\text{for }}x=\omega \\{\frac {1}{\sqrt {2}}}(|x\rangle |0\rangle -|x\rangle |1\rangle )&{\text{for }}x\neq \omega \end{cases}}\\&=(-1)^{f(x)}|x\rangle |-\rangle \end{aligned}}$

与一般的 $U_{\omega }$ 相比， $U_{f}$ 使用了一个辅助的qubit。

算法步骤

格罗弗算法的量子电路表示

格罗弗算法的步骤如下

构建量子叠加态

|s\rangle =H^{\otimes N}|0\rangle ^{\otimes N}={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle

2. 做

p(N)

次“格罗弗迭代”，具体操作如下

将 $U_{\omega }$ 作用在 $|s\rangle$ 上
将 $U_{s}=2|s\rangle \langle s|-I$ 作用在 $|s\rangle$ 上

其中，

U_{s}

被称为格罗弗扩散算子

3. 测量

|s\rangle

，得到求得的结果

一般而言， $p(N)$ 的值会很大程度上影响得到正确结果的概率，且并不是 $p(N)$ 越大得到正确结果的概率越大。分析表明最优的 $p(N)$ 有 $p(N)\leq {\Big \lceil }{\frac {\pi }{4}}{\sqrt {N}}{\Big \rceil }$ ，因而格罗弗算法的复杂度为 ${\mathcal {O}}({\sqrt {N}})$

正确性证明

几何直观证明

格罗弗算法使用的技巧为振幅减枝(Amplitude amplification)，实则是通过将其他态的振幅转移为解的振幅，而是在测量时使得坍塌为解的概率增加。具体如下

代数证明

考虑，我们将态矢量改为以 $|x\rangle ,|\omega \rangle$ 为基，其中 $\omega$ 为解。写作

$|s\rangle =a|\omega \rangle +b|x\rangle$

在这种表示下，我们可以将 $U_{s}$ 和 $U_{\omega }$ 表示为

U_{s}:a|\omega \rangle +b|x\rangle \mapsto [|\omega \rangle \,|x\rangle ]{\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.

U_{\omega }:a|\omega \rangle +b|x\rangle \mapsto [|\omega \rangle \,|x\rangle ]{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.

$U_{s}U_{\omega }={\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}={\begin{bmatrix}1&2/{\sqrt {N}}\\-2/{\sqrt {N}}&1-4/N\end{bmatrix}}.$

我们可以通过设 $t=\arcsin(1/{\sqrt {N}})$ ，将上式改写为（所谓Jordan form）

$U_{s}U_{\omega }=M{\begin{bmatrix}e^{2it}&0\\0&e^{-2it}\end{bmatrix}}M^{-1}$ where $M={\begin{bmatrix}-i&i\\e^{it}&e^{-it}\end{bmatrix}}.$

作用r次 $U_{s}$ $U_{\omega }$ 则将得到

$(U_{s}U_{\omega })^{r}=M{\begin{bmatrix}e^{2rit}&0\\0&e^{-2rit}\end{bmatrix}}M^{-1}.$

注意到，我们的目的是区别解以及其他一般的数据，而为了达到这个目的，我们使 $|x\rangle ,|\omega \rangle$ 的振幅差别越大越好，换言之，要使得2rt和−2rt的差别足够大，便有 $2rt\approx \pi /2$ , 或 $r=\pi /4t=\pi /4\arcsin(1/{\sqrt {N}})\approx \pi {\sqrt {N}}/4$ . 这样以来，就有

$(U_{s}U_{\omega })^{r}=M{\begin{bmatrix}i&0\\0&-i\end{bmatrix}}M^{-1}.$

作用在初始态上将会有

$[|\omega \rangle \,|x\rangle ](U_{s}U_{\omega })^{r}{\begin{bmatrix}0\\1\end{bmatrix}}\approx [|\omega \rangle \,|x\rangle ]M{\begin{bmatrix}i&0\\0&-i\end{bmatrix}}M^{-1}{\begin{bmatrix}0\\1\end{bmatrix}}=|\omega \rangle {\frac {1}{\cos(t)}}-|x\rangle {\frac {\sin(t)}{\cos(t)}}.$