Grover算法

Grover算法是一種量子算法，於1996年由計算機科學家 Lov Grover提出。假設現在有一個未知的函數，Grover算法只需對此未知的函數做 ${\displaystyle O({\sqrt {N}})}$ 次測試，其中${\displaystyle N}$為此未知函數的定义域的大小，即可以很高的概率找到一特定的輸入值，此輸入值能使此未知函數輸出特定的值。

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

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

不像其他的量子算法可能會比相應的經典算法有指數級的加快，Grover算法二次方的加快，不過當${\displaystyle N}$很大時二次方的加快也相當可觀。Grover算法可以在大約 2⁶⁴次迭代內窮舉破解一個128比特的對稱密鑰，在大約 2¹²⁸次迭代內窮舉破解一個256比特的密鑰。因此，有人提倡對稱密鑰的長度應該加倍以因應未來的量子攻擊。[3]

像其他的量子算法一樣，Grover算法是概率性的，意味著這個算法以小於1的概率給出正確答案。雖然實際上對於需要多少次重複才能給出正確的答案並沒有一個上界，但是期望的重複次數並不隨${\displaystyle N}$成長。在Grover發表此算法的原始論文中稱此算法為數據庫搜索算法，此說法至今仍普遍。此處數據庫相當於是一張存有未知函數的所有輸出值的表，以對應的輸入值為索引。

應用

雖然Grover算法的用處一直被認為是數據庫搜索，但是它也可以被認為是函數取反。

設定

考慮一個未排序有${\displaystyle N}$個條目的數據庫，此算法需要一個由n = log₂ N 個量子比特所組成的${\displaystyle N}$維狀態空間H。

算法步驟

Grover算法的量子电路表示

下面${\displaystyle |s\rangle }$代表了所有狀態的均勻態疊加

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

令

${\displaystyle U_{s}=2|s\rangle \langle s|-I}$

为Grover扩散算子，

${\displaystyle U_{\omega }=I-2|\omega \rangle \langle \omega |}$，

其中 ${\displaystyle \omega }$为使 ${\displaystyle f(x)=1}$ 的唯一值。

将 ${\displaystyle U_{s}\circ U_{\omega }}$ 循环 ${\displaystyle O({\sqrt {N}})}$次。

参见

• Amplitude amplification
• 秀爾演算法

參考資料

1. Bennett C.H.; Bernstein E.; Brassard G.; Vazirani U. . SIAM Journal on Computing. 1997, 26 (5): 1510–1523 [2019-06-12]. arXiv:quant-ph/9701001. doi:10.1137/s0097539796300933. （原始内容存档于2016-03-06）.
2. Aaronson, Scott. (PDF). （原始内容存档 (PDF)于2020-12-03）.
3. Daniel J. Bernstein. (PDF). 2010-03-03 [2019-06-12]. （原始内容 (PDF)存档于2010-10-10）.

外部链接

• Davy Wybiral. . [2017-01-13]. （原始内容存档于2017-01-16）.
• Craig Gidney. . 2013-03-05 [2019-06-12]. （原始内容存档于2020-11-17）.
• François Schwarzentruber. . 2013-05-18 [2019-06-12]. （原始内容存档于2020-11-16）.
• Alexander Prokopenya. . Wolfram Alpha. [2019-06-12]. （原始内容存档于2020-11-20）.
• Hazewinkel, Michiel (编), , , Springer, 2001, ISBN 978-1-55608-010-4
• Roberto Maestre. . 2018-05-11.