グローバーのアルゴリズム
なお、(下に示す量子回路のように)補助量子ビットシステムを使う場合には、演算子 U ω {\displaystyle U_{\omega }} の定義は異なるものになる。この場合の演算子は、メインシステムの f ( x ) {\displaystyle f(x)} の値(0か1)に応じて反転させる制御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 .}
で表現される。
グローバーのアルゴリズムは最適であることが知られている。つまり、データベースにUωのみを用いてアクセスするようなどんなアルゴリズムも、グローバーのアルゴリズムと同じかそれ以上の回数だけUωを作用させなければならない。この結果は量子計算の限界を理解する上で重要である。 もし、グローバーの探索問題がlogN回Uω適用することで解くことができるとすれば、NP問題をグローバーの探索問題に帰着させることで、NPがBQPに含まれることが示される。グローバーのアルゴリズムが最適であることは、NPはBQPに含まれないことを示唆している(ただし証明しているわけではない)。
k個の条件に該当するデータがある場合、π(N/k)/4も最適である。
が成り立つ。したがって、1回目の繰り返しでは次にように計算される。
U ω | s ⟩ = ( I − 2 | ω ⟩ ⟨ ω | ) | s ⟩ = | s ⟩ − 2 | ω ⟩ ⟨ ω | s ⟩ = | s ⟩ − 2 N | ω ⟩ , U s ( | s ⟩ − 2 N | ω ⟩ ) = ( 2 | s ⟩ ⟨ s | − I ) ( | s ⟩ − 2 N | ω ⟩ ) = 2 | s ⟩ ⟨ s | s ⟩ − | s ⟩ − 4 N | s ⟩ ⟨ s | ω ⟩ + 2 N | ω ⟩ = 2 | s ⟩ − | s ⟩ − 4 N ⋅ 1 N | s ⟩ + 2 N | ω ⟩ = N − 4 N | s ⟩ + 2 N | ω ⟩ .