格罗弗算法

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

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

${\displaystyle {\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}}}}$ 

或者可以简写为

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

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

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

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

${\displaystyle {\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}}}$ 

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

格罗弗算法的步骤如下

1. 构建量子叠加态

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

2. 做${\displaystyle p(N)}$ 次“格罗弗迭代”，具体操作如下

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

其中，${\displaystyle U_{s}}$ 被称为格罗弗扩散算子

3. 测量${\displaystyle |s\rangle }$ ，得到求得的结果

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

几何直观证明

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

代数证明

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

${\displaystyle |s\rangle =a|\omega \rangle +b|x\rangle }$ 

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

${\displaystyle 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}}.}$ 

${\displaystyle 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}}.}$ 

${\displaystyle 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}}.}$ 

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

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

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

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

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

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

作用在初始态上将会有

${\displaystyle [|\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)}}.}$ 

简短的计算表明，格罗弗算法将具有${\displaystyle O\left({\frac {1}{N}}\right)}$ 量级的误差.

• Amplitude amplification（英语：Amplitude amplification）
• 秀尔算法

• Davy Wybiral. Quantum Circuit Simulator. [2017-01-13]. （原始内容存档于2017-01-16）. 
• Craig Gidney. Grover’s Quantum Search Algorithm. 2013-03-05 [2019-06-12]. （原始内容存档于2020-11-17）. 
• François Schwarzentruber. Grover's algorithm. 2013-05-18 [2019-06-12]. （原始内容存档于2020-11-16）. 
• Alexander Prokopenya. Quantum Circuit Implementing Grover's Search Algorithm. Wolfram Alpha. [2019-06-12]. （原始内容存档于2020-11-20）. 
• Hazewinkel, Michiel (编), Quantum computation, theory of, 数学百科全书, Springer, 2001, ISBN 978-1-55608-010-4 
• Roberto Maestre. Grover's Algorithm implemented in R and C. 2018-05-11 [2019-06-12]. （原始内容存档于2021-10-17）.