グローバーのアルゴリズムとは、N個の要素をもつ未整序データベースの中から指定された値を検索する探索問題を解くための量子コンピュータのアルゴリズムであり、O(N1/2)のオーダーの計算量と、O(logN)のオーダー（ランダウの記号も参照）の記憶領域
を消費する。1996年にロブ・グローバー（英語版）によって開発された。典型的には、未整序データベースからの探索は、O(N)の計算時間を要する線型探索を用いなければならない。グローバーのアルゴリズムは、O(N1/2)の計算時間しか消費せず、未整序データベース探索を行う量子アルゴリズムの中で最も速い[1]。
このアルゴリズムは他の量子アルゴリズムがしばしば、古典アルゴリズムと比較して指数的な速度向上をもたらすのとは異なり、二次の速度向上しかもたらさない。しかし、Nが大きければ、二次の向上でもかなりの向上となる。たとえば、グローバーのアルゴリズムを共通鍵暗号の総当り攻撃に利用すると、128ビット鍵であれば264の繰り返しで、256ビット鍵であれば2128の繰り返しで求めることができる。このため、将来の量子総当り攻撃に対して安全性を持たせるために、鍵長を2倍にすることが提案されている[2]。
他の量子アルゴリズムと同じように、グローバーのアルゴリズムは正しい解を高い確率で与える確率的アルゴリズムである。この解が正しくない確率は、このアルゴリズムを繰り返すことによって減少させることができる（確率的アルゴリズムでない、正しい確率が1の解を与える、決定的アルゴリズムについてはドイッチュ・ジョサのアルゴリズムを参照）。 グローバーのアルゴリズムの目的は普通「データベース探索」とされるが、「逆関数の導出」と言うとより正確かもしれない。おおざっぱにいうと、y=f(x)という量子コンピュータで処理できる関数があったとして、このアルゴリズムを使うとあるyを与えるxの値を計算することができる。データベース探索は、データベースをインデックスxに対してデータyを与える関数と考えれば、逆関数を求めることと同値である。
応用
N個のデータを持つデータベースを考える。データベースの中から、何らかの検索条件を満たすデータを探し出す問題を考えよう。グローバーのアルゴリズムは、 N {\displaystyle N} 次元の状態空間 H {\displaystyle {\mathcal {H}}} を必要とする。これは n = ⌈ log 2 N ⌉ {\displaystyle n=\lceil \log _{2}N\rceil } 量子ビットあれば満され、基底状態は 。 1 ⟩ , 。 2 ⟩ , … , 。 N ⟩ {\displaystyle |1\rangle ,|2\rangle ,\ldots ,|N\rangle }
と書ける。これらの固有値 { λ 1 , λ 2 , ⋯ , λ N } {\displaystyle \{\lambda _{1},\lambda _{2},\cdots ,\lambda _{N}\}} は全て異なるとする。
f {\displaystyle f} を、データベースのインデクス x ∈ { 1 , 2 , … , N } {\displaystyle x\in \{1,2,\ldots ,N\}} を入力すると、検索条件を満たしているか否かを判定する関数とする。例えば、値 v {\displaystyle v} に対して D [ x ] = v {\displaystyle D[x]=v} となる x {\displaystyle x} を探したい場合には、 { 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 } を特定することである。
なお、（下に示す量子回路のように）補助量子ビット
システムを使う場合には、演算子 U ω {\displaystyle U_{\omega }} の定義は異なるものになる。この場合の演算子は、メインシステムの f ( x ) {\displaystyle f(x)} の値（０か１）に応じて反転させる制御NOTによって { U ω 。 x ⟩ 。 y ⟩ = 。 x ⟩ 。 ¬ y ⟩ for x = ω , that is f ( x ) = 1 , U ω 。 x ⟩ 。 y ⟩ = 。 x ⟩ 。 y ⟩ for x ≠ ω , that is f ( x ) = 0 , {\displaystyle {\begin{cases}U_{\omega }|x\rangle |y\rangle =|x\rangle |\neg y\rangle &{\text{for }}x=\omega {\text{, that is }}f(x)=1,\\U_{\omega }|x\rangle |y\rangle =|x\rangle |y\rangle &{\text{for }}x\neq \omega {\text{, that is }}f(x)=0,\end{cases}}}あるいは、 U ω 。 x ⟩ 。 y ⟩ = 。 x ⟩ 。 y ⊕ f ( x ) ⟩ . {\displaystyle U_{\omega }|x\rangle |y\rangle =|x\rangle |y\oplus f(x)\rangle .}
で表現される。
。 s ⟩ {\displaystyle |s\rangle } を、全ての状態の一様な重ね合わせ 。 s ⟩ = 1 N ∑ x = 0 N − 1 。 x ⟩ {\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle }
とし、演算子 U s {\displaystyle U_{s}} を U s = 2 。
