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