格罗夫算法

格罗弗算法（英語：Grover's algorithm）是一種量子算法，於1996年由電腦科學家洛夫·格罗弗提出。假設現在有一個未知的函數，格罗弗算法只需測試此未知的函數次，其中為此未知函數的定义域的大小，即可以很高的概率找到一特定的輸入值，此輸入值能使此未知函數輸出特定的值。 同樣的問題在經典運算下，需要至少做 次測試（因為在最壞的情況下，可能第個定義域裡的值才是正確答案）。在格罗弗發表他的算法前後，Bennett, Bernstein, Brassard, 和 Vazirani 在相近的時間證明了，任何量子算法解決此問題都最少需要對此未知的函數做 次測試，因此格罗弗算法是渐进最优的。 非局域隱變量量子計算機已經被證明可以在最多 步內實現在N個條目的數據庫裡的搜索，這比格罗弗算法的 還快，然而這些搜索算法並不能使量子計算機在多項式時間內解決NP-Complete 問題。 不像其他的量子算法可能會比相應的經典算法有指數級的加快，格罗弗算法二次方的加快，不過當很大時二次方的加快也相當可觀。格罗弗算法可以在大約 264次迭代內窮舉破解一個128比特的對稱密鑰，在大約 2128次迭代內窮舉破解一個256比特的密鑰。因此，有人提倡對稱密鑰的長度應該加倍以因應未來的量子攻擊。 像其他的量子算法一樣，格罗弗算法是概率性的，意味著這個算法以小於1的概率給出正確答案。雖然實際上對於需要多少次重複才能給出正確的答案並沒有一個上界，但是期望的重複次數並不隨成長。在格罗弗發表此算法的原始論文中稱此算法為數據庫搜索算法，此說法至今仍普遍。此處數據庫相當於是一張存有未知函數的所有輸出值的表，以對應的輸入值為索引。