グローバーのアルゴリズム
{ f ( x ) = 1 if D [ x ] = v , f ( x ) = 0 if D [ x ] ≠ v {\displaystyle {\begin{cases}f(x)=1&{\text{ if }}D[x]=v,\\f(x)=0&{\text{ if }}D[x]\neq v\end{cases}}}
である。以下では ω {\displaystyle \omega } を、 f ( ω ) = 1 {\displaystyle f(\omega )=1} を満たす値とし、次のようにふるまうユニタリ演算子 U ω {\displaystyle U_{\omega }} を自由にサブルーチンとして使えるとする。(このサブルーチンは、オラクルとも呼ばれる。)
{ U ω | x ⟩ = − | x ⟩ for x = ω , that is f ( x ) = 1 U ω | x ⟩ = | x ⟩ for x ≠ ω , that is f ( x ) = 0 {\displaystyle {\begin{cases}U_{\omega }|x\rangle =-|x\rangle &{\text{for }}x=\omega {\text{, that is }}f(x)=1\\U_{\omega }|x\rangle =|x\rangle &{\text{for }}x\neq \omega {\text{, that is }}f(x)=0\end{cases}}}
アルゴリズムの目的は、インデクス | ω ⟩ {\displaystyle |\omega \rangle } を特定することである。
典型的には、未整序データベースからの探索は、O(N)の計算時間を要する線型探索を用いなければならない。グローバーのアルゴリズムは、O(N)の計算時間しか消費せず、未整序データベース探索を行う量子アルゴリズムの中で最も速い。
このアルゴリズムは他の量子アルゴリズムがしばしば、古典アルゴリズムと比較して指数的な速度向上をもたらすのとは異なり、二次の速度向上しかもたらさない。しかし、Nが大きければ、二次の向上でもかなりの向上となる。たとえば、グローバーのアルゴリズムを共通鍵暗号の総当り攻撃に利用すると、128ビット鍵であれば2の繰り返しで、256ビット鍵であれば2の繰り返しで求めることができる。このため、将来の量子総当り攻撃に対して安全性を持たせるために、鍵長を2倍にすることが提案されている。
他の量子アルゴリズムと同じように、グローバーのアルゴリズムは正しい確率の高い解を与える、確率的アルゴリズムである。この解が正しくない確率は、このアルゴリズムを繰り返すことによって減少させることができる(確率的アルゴリズムでない、正しい確率が1の解を与える、決定的アルゴリズムについてはドイッチュ・ジョサのアルゴリズムを参照)。