格罗弗算法

格罗弗算法（英語：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)}}.$