本页使用了标题或全文手工转换

Grover算法

维基百科,自由的百科全书
跳到导航 跳到搜索

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

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

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

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

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

應用[编辑]

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

設定[编辑]

考慮一個未排序有個條目的數據庫,此算法需要一個由n = log2 N 個量子比特所組成的維狀態空間H

算法步驟[编辑]

Grover算法的量子电路表示

下面代表了所有狀態的均勻態疊加

为Grover扩散算子,

其中 为使 的唯一值。

循环 次。

参见[编辑]

參考資料[编辑]

  1. ^ Bennett C.H.; Bernstein E.; Brassard G.; Vazirani U. The strengths and weaknesses of quantum computation. SIAM Journal on Computing英语SIAM Journal on Computing. 1997, 26 (5): 1510–1523. arXiv:quant-ph/9701001. doi:10.1137/s0097539796300933. 
  2. ^ Aaronson, Scott. Quantum Computing and Hidden Variables (PDF). 
  3. ^ Daniel J. Bernstein. Grover vs. McEliece (PDF). 2010-03-03 [2019-06-12]. (原始内容 (PDF)存档于2010-10-10). 

外部链接[编辑]