グローバーのアルゴリズム
初期状態を以下の様に用意する: | s ⟩ = 1 N ∑ x = 1 N | x ⟩ {\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=1}^{N}|x\rangle }
次にしめす"Grover iteration"を r ( N ) {\displaystyle r(N)} 回繰返す。関数 r ( N ) {\displaystyle r(N)} は漸近的に O ( N ) {\displaystyle O({\sqrt {N}})} である関数であり、詳細は後述する。 演算子 U ω {\displaystyle U_{\omega }} を適用する。 演算子 U s {\displaystyle U_{s}} を適用する。
状態Ωを観測する。観測の結果は、Nが十分に大きければ、1に近い確率でλωとなり、 ω {\displaystyle \omega } を得ることができる。
このアルゴリズムにおいては、データベースは明示的に表されておらず、代わりに、インデクスによってデータで評価するためにオラクルを呼び出す。データベース全体をデータごとに読み込み、それをインデクスを使って評価できる形式に変換することは、グローバーの検索よりもはるかに時間がかかる場合がある。これを考えると、グローバーのアルゴリズムは、方程式や制約充足問題を解くための方法であると見ることができる。このようなアプリケーションでは、オラクルは制約を満たすかどうかをチェックする方法であり、検索アルゴリズムとは無関係に動作する。一方、従来の検索アルゴリズムでは、検索アルゴリズムを制約のチェック方法と合わせて考慮することで総当たりを回避して最適化を行うことが良くある。グローバーのアルゴリズムではこれらが分離しているため、アルゴリズムの最適化が妨げられる。グローバーのアルゴリズムの使用に関するこれらおよびその他の考慮事項は、Viamontes、Markov、およびHayesによる論文で説明されている。
U ω : a | ω ⟩ + b | s ⟩ ↦ [ | ω ⟩ | s ⟩ ] [ − 1 − 2 / N 0 1 ] [ a b ] {\displaystyle U_{\omega }:a|\omega \rangle +b|s\rangle \mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}}
よって、 { | ω ⟩ , | s ⟩ } {\displaystyle \{|\omega \rangle ,|s\rangle \}} を基底とすると(ただし,これらは直交していないし、全体の空間の基底にはなっていない)、 U ω {\displaystyle U_{\omega }} を作用させてから U s {\displaystyle U_{s}} を作用させるという動作 U s U ω {\displaystyle U_{s}U_{\omega }} は、次の行列で表せる。
U s U ω = [ − 1 0 2 / N 1 ] [ − 1 − 2 / N 0 1 ] = [ 1 2 / N − 2 / N 1 − 4 / N ] {\displaystyle U_{s}U_{\omega }={\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}={\begin{bmatrix}1&2/{\sqrt {N}}\\-2/{\sqrt {N}}&1-4/N\end{bmatrix}}}