グローバーのアルゴリズム
一般の場合では、 U ω {\displaystyle U_{\omega }} と U s {\displaystyle U_{s}} を作用させることで、目的の状態の二乗振幅は | ⟨ ω | s ⟩ | 2 = 1 N {\displaystyle \left|\langle \omega |s\rangle \right|^{2}={\tfrac {1}{N}}} から | ⟨ ω | U s U ω | s ⟩ | 2 = | 1 N ⋅ N − 4 N + 2 N | 2 = ( 3 N − 4 ) 2 N 3 = 9 ( 1 − 4 3 N ) 2 ⋅ 1 N {\displaystyle \left|\langle \omega |U_{s}U_{\omega }|s\rangle \right|^{2}=\left|{\tfrac {1}{\sqrt {N}}}\cdot {\tfrac {N-4}{N}}+{\tfrac {2}{\sqrt {N}}}\right|^{2}={\tfrac {(3N-4)^{2}}{N^{3}}}=9\left(1-{\tfrac {4}{3N}}\right)^{2}\cdot {\tfrac {1}{N}}} に増加する。
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} を探したい場合には、