格羅弗演算法

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