格羅弗算法

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