グローバーのアルゴリズム
グローバーのアルゴリズムとは、N個の要素をもつ未整序データベースの中から指定された値を検索する探索問題を解くための量子コンピュータのアルゴリズムであり、O(N)のオーダーの計算量と、O(logN)のオーダー(ランダウの記号も参照)の記憶領域を消費する。1996年にロブ・グローバー(英語版)によって開発された。
代数的な解析をするには、 U s U ω {\displaystyle U_{s}U_{\omega }} を繰り返し適用したときに何が起こるかを見る必要がある。これは、行列の固有値解析によって見ることができる。アルゴリズムの計算の間、状態は常に s {\displaystyle s} と ω {\displaystyle \omega } の線形結合で表されるいることに注意する。そこで、 { | s ⟩ , | ω ⟩ } {\displaystyle \{|s\rangle ,|\omega \rangle \}} によって張られる空間において、 U s {\displaystyle U_{s}} と U ω {\displaystyle U_{\omega }} の動作は次のように表すことができる。
U s : a | ω ⟩ + b | s ⟩ ↦ [ | ω ⟩ | s ⟩ ] [ − 1 0 2 / N 1 ] [ a b ] {\displaystyle U_{s}:a|\omega \rangle +b|s\rangle \mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}}
| 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 | s ⟩ ⟨ s | − I {\displaystyle U_{s}=2\left|s\right\rangle \left\langle s\right|-I}
とする。この演算子は、グローバーの拡散演算子と呼ばれている。
グローバーのアルゴリズムの流れは以下の通りである。