ステップ2,3の繰り返しの回数である。理屈を抜きにすれば、グローバーのアルゴリズムで行う操作はこれだけで、非常にシンプルである。次に、グローバーのアルゴリズムがなぜ上手くいくのか、幾何学的な説明を行う。(他にも係数の平均操作に着目する説明もあり、例えば[3]を参照してほしい。張られる2次元平面を考える。次のように表せるので、この2次元平面内のベクトルであることがわかる。|\beta\rangle\]とかける。これを図示すると、以下のようになる。0に近い正の数になっていることが多い。-|\beta\rangle\))。\(\theta\)だけの回転が行われることになる。|\beta\rangle\]となっている。係数が増えることになる。測定した時に解が出力される確率が高まることを意味する。以上が、グローバーのアルゴリズムが解を上手く探索できる理由である。オラクルを呼ぶ回数がどれくらいになるのか評価してみよう。これが計算量を決めることになる。\right)\]の時である。\(R\)の上限を評価しよう。\frac{1}{2}\]となる。動作することが分かった。用いて実装してみよう。qubitでグローバーのアルゴリズムを実装し、動作を確認してみよう。全てのビットにアダマールゲートを作用させることで作れる。位相(-1)をつける演算子を作る。ゲートを作用させる演算子」として実装できる。U_wオラクルの作用を確認すると、確かに最後の成分(\(|1\cdots1\rangle\))だけ位相が反転していることが分かる。以下の式が成り立つことを使う。位相(-1)を全ての状態に付与する。一回だけ作用させて確率分布の変化を見てみよう。全部1の状態(一番右側)の確率が少し大きくなっている。解の状態を得ることができた。対する解出力確率の振る舞いをチェックしてみる。確率1でtarget状態が得られている。確率の\(k\)依存性は、「幾何学的な説明」の箇所で見たように、サイン関数になっている。量子ビット数についてどのように振る舞うか見てみよう。比例していることがわかる。解答例もアップロードされている。