グローバー探索：振幅を1つに集める
N 個の候補の振幅を「目印反転 → 平均まわりの反転」で 1 つに増幅し、約 √N 回で当たりが見つかる様子を体感します。
16
11
0.9 s
反復回数 t
—
当たりの測定確率 |aw|²
—
最適反復回数 ≈ ⌊π√N / 4⌋
—
古典の平均探索回数
—
状態ベクトルの回転（探索平面の2D投影）
各候補の振幅（高さ=振幅、当たりは緑、目印反転で負になると下向き）
探したいのは N 個の中のたった 1 つ「当たり w」。古典コンピュータは 1 個ずつ確かめ、平均で N/2 回、最悪 N 回かかります。
グローバーのアルゴリズムは、全候補を同じ振幅で重ね合わせた状態から、次の 2 ステップを繰り返します。
① オラクル（目印反転）…当たりの振幅だけ符号を反転（下向きに）。
② 拡散（平均まわりの反転）…全振幅を「平均値」を軸に折り返す。すると下を向いていた当たりだけが大きく持ち上がる。
この組を 約 √N 回繰り返すと、当たりの測定確率がほぼ 1 になります。ボタンで 1 反復ずつ進め、振幅が 1 つに集まる様子を確かめましょう。
グローバーのアルゴリズムは、全候補を同じ振幅で重ね合わせた状態から、次の 2 ステップを繰り返します。
① オラクル（目印反転）…当たりの振幅だけ符号を反転（下向きに）。
② 拡散（平均まわりの反転）…全振幅を「平均値」を軸に折り返す。すると下を向いていた当たりだけが大きく持ち上がる。
この組を 約 √N 回繰り返すと、当たりの測定確率がほぼ 1 になります。ボタンで 1 反復ずつ進め、振幅が 1 つに集まる様子を確かめましょう。
いま何が起きている？
ここがポイント
- 測定確率 = |振幅|² ── 振幅そのものではなく、その2乗が「測って当たりが出る確率」。
- 1反復 = オラクル + 拡散 ── 目印反転だけでは確率は変わらない。平均まわりの反転で初めて増幅される。
- 各反復で当たりの振幅は一定角 2θ ずつ回転 ── 状態ベクトルは2次元平面内をくるくる回り、当たり軸に近づく。
- 増幅は √N 回がベスト ── やり過ぎると行き過ぎて確率が下がる（過回転）。古典の N 回に対し二次の高速化。