格羅弗算法

格羅弗算法（Grover's algorithm）是一種量子演算法，於1996年由電腦科學家洛夫·格羅弗提出。假設現在有一個未知的函數，格羅弗算法只需測試此未知的函數$O(\sqrt{N})$次，其中$N$為此未知函數的定義域的大小，即可以很高的機率找到一特定的輸入值，此輸入值能使此未知函數輸出特定的值。

同樣的問題在經典運算下，需要至少做 $O(N)$ 次測試（因為在最壞的情況下，可能第$N$個定義域裡的值才是正確答案）。在格羅弗發表他的演算法前後，Bennett, Bernstein, Brassard, 和 Vazirani 在相近的時間證明了，任何量子演算法解決此問題都最少需要對此未知的函數做 $\Omega(\sqrt{N})$ 次測試，因此格羅弗算法是漸進最優的。

非局域隱變量量子計算機已經被證明可以在最多 $O(\sqrt[3]{N})$ 步內實現在N個條目的資料庫裡的搜索，這比格羅弗算法的 $O(\sqrt{N})$ 還快，然而這些搜索算法並不能使量子計算機在多項式時間內解決NP-Complete 問題。

不像其他的量子演算法可能會比相應的經典演算法有指數級的加快，格羅弗算法二次方的加快，不過當$N$很大時二次方的加快也相當可觀。格羅弗算法可以在大約 264次迭代內窮舉破解一個128比特的對稱密鑰，在大約 2128次迭代內窮舉破解一個256比特的密鑰。因此，有人提倡對稱密鑰的長度應該加倍以因應未來的量子攻擊。

像其他的量子演算法一樣，格羅弗算法是機率性的，意味著這個演算法以小於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\rang=(-1)^{f(x)}|x\rang$$

事實上，一般構建另一種酉算子 $U_f$，如下所示

$$U_f|x\rang|y\rang=|x\rang|y\oplus f(x)\rang$$

一般將 $U_f$ 作用在態矢量和 $|-\rang$ 的疊加態上，以實現相回傳(Phase Kickback)，具體流程如下

$$\begin{align} <pre> U_f|x\rang|-\rang&=U_f|x\rang\left[\frac{|0\rang-|1\rang}{\sqrt{2}}\right]\\ &={\begin{cases} \frac{1}{\sqrt{2}}(|x\rang|1\rang-|x\rang|0\rang) &{\text{for }}x=\omega\\ \frac{1}{\sqrt{2}}(|x\rang|0\rang-|x\rang|1\rang) &{\text{for }}x\neq \omega\end{cases}}\\ &=(-1)^{f(x)}|x\rang|-\rang </pre> \end{align}$$

與一般的 $U_\omega$ 相比， $U_f$ 使用了一個輔助的qubit。

## 演算法步驟

格羅弗算法的步驟如下

- 構建量子疊加態

$$|s\rangle = H^{\otimes N}|0\rang^{\otimes N} = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle$$

- 做$p(N)$次「格羅弗迭代」，具體操作如下

- 將$U_\omega$作用在$|s\rang$上
- 將$U_s = 2 |s\rangle \langle s| - I$ 作用在$|s\rang$上

其中，$U_s$被稱為格羅弗擴散算子

- 測量$|s\rang$，得到求得的結果

一般而言，$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\rang,|\omega\rang$為基，其中$\omega$為解。寫作

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

在這種表示下，我們可以將$U_s$和$U_\omega$表示為

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

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

$$U_sU_\omega = \begin{bmatrix} -1 & 0 \\ 2/\sqrt{N} & 1 \end{bmatrix} \begin{bmatrix} -1 & -2/\sqrt{N} \\ 0 & 1 \end{bmatrix} <pre> = </pre> \begin{bmatrix} 1 & 2/\sqrt{N} \\ -2/\sqrt{N} & 1-4/N \end{bmatrix}.$$

我們可以通過設$t = \arcsin(1/\sqrt{N})$，將上式改寫為（所謂Jordan form）

$U_sU_\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_sU_\omega)^r = M \begin{bmatrix} e^{2rit} & 0 \\ 0 & e^{-2rit}\end{bmatrix} M^{-1}.$$

注意到，我們的目的是區別解以及其他一般的數據，而為了達到這個目的，我們使$|x\rang,|\omega\rang$的振幅差別越大越好，換言之，要使得2rt和−2rt的差別足夠大，便有$2rt \approx \pi/2$, 或 $r = \pi/4t = \pi/4\arcsin(1/\sqrt{N}) \approx \pi\sqrt{N}/4$. 這樣以來，就有

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

作用在初始態上將會有

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

簡短的計算表明，格羅弗算法將具有$O\left (\frac{1}{N} \right)$量級的誤差.