グローバー探索 — √N 回で見つける振幅増幅

N 個の候補から条件を満たす 1 個を、約 √N 回の試行で見つけ出す。グローバーのアルゴリズムの心臓部は振幅増幅 — 「符号の反転」と「平均まわりの反転」を交互に繰り返すだけの、驚くほど単純な反復です。正解の振幅がぐんぐん育つ様子を、実際の振幅シミュレーションで1ステップずつ動かします。

1. 問題設定 — オラクルという「答え合わせ回路」

候補は x = 0 〜 N−1 の N 個。そのうちただ1つの正解 ω だけが条件 f(ω)=1 を満たします。手がかりは一切なし — できるのは「x は正解？」と判定関数 f に聞くことだけ。古典計算機なら平均 N/2 回、最悪 N 回聞くしかありません。

量子版の f がオラクルです。オラクルは重ね合わせ状態を受け取り、正解の成分の符号だけを反転します（位相オラクル）：|ω⟩ → −|ω⟩。ここで大事なのは、符号を反転しただけでは測定確率は 1 ミリも変わらないこと（|−a|² = |a|²）。印は付いたのに見えない — この見えない印を「振幅の差」に変換するのが、次の拡散操作です。

注意 — 「データベース検索」の比喩の限界グローバーは既存のデータベースを魔法のように高速検索するわけではない。オラクルは「候補を受け取って検証する回路」であり、電話帳のような非構造データを引きたければ、まず全データを量子回路（QRAM）に載せる前処理が要る。そこに O(N) のコストがかかれば加速は帳消し。本領を発揮するのは SAT や暗号鍵の総当たりのように「1候補の検証は速いが、候補の数が爆発している」タイプの問題。

2. 振幅増幅を動かす — オラクルと拡散の反復

N = 16 の実振幅シミュレーションです。初期状態は H ゲートによる一様重ね合わせ（全部 1/√16 = 0.25）。① オラクル（正解の符号反転）→ ② 拡散（平均まわりの反転）を交互に押して、正解の振幅が育つのを確かめてください。そして最適回数（約3回）を過ぎても続けると何が起きるかも。

振幅増幅の反復 — N=16、正解はどれか1つ

正解の位置

オレンジ＝正解の振幅、青＝それ以外、緑の破線＝振幅の平均。右のグラフは正解を測定できる確率 P の推移（水色＝理論値 sin²((2k+1)θ)）。3回で P≈96%、4回目からは逆に減っていきます。「測定してみる」は現在の |振幅|² でくじ引きするデモ（実機では測定で状態が壊れるので1回勝負。ここでは何度でも試せます）。

最適反復回数　k_opt ≈ ⌊(π/4)√N⌋ 正解が M 個あるなら (π/4)√(N/M)。N=16 で 3 回、N=100万でも約 785 回で済む

POINT — 最適停止：回しすぎると戻ってくる振幅増幅は「押せば押すほど良い」反復ではない。後述のとおり各反復は角度 2θ の回転なので、正解の真上（P=100% 付近）を通り過ぎるとまた遠ざかる。√N に比例したちょうどいい回数で測定することまで含めてアルゴリズムである。

3. 拡散のからくり — 平均まわりの反転

拡散演算子は D = 2|s⟩⟨s| − I。数式は物々しいですが、やることは「各振幅 a を平均 m の反対側へ折り返す（a → 2m − a）」だけです。オラクルで1本だけ負にしておくと平均 m がわずかに下がり、その m を鏡にして全員を折り返すと — 負だった正解だけが大きく跳ね上がります。スローモーションでどうぞ。

平均まわりの反転 — 1反復で何が起きているか（N=8 でスロー再生）

再生速度

緑の破線＝振幅の平均 m。オラクルが正解を負にすると m が少し下がり、「平均まわりの折り返し」で正解だけ 2m + |a| まで伸びる。N=8 ならこの1反復だけで P が 12.5% → 78% に跳ぶ。

4. 幾何で見る — 2枚の鏡は回転になる

実は状態ベクトルはずっと、|ω⟩（正解）と |α⟩（正解以外の一様和）が張る2次元平面の中にいます。この平面で見ると：

オラクル ＝ |α⟩ 軸（横軸）に関する鏡映（|ω⟩ 成分の符号反転）
拡散＝初期状態 |s⟩ の方向に関する鏡映

そして幾何学の定理どおり、鏡映2回は回転1回。2枚の鏡のなす角が θ なら、1反復ごとに状態は正解軸へ角度 2θ ずつ回転します（sin θ = 1/√N）。

幾何的な見方 — 鏡映×2 ＝ 2θ の回転（N=16, θ≈14.5°）

縦軸＝正解 |ω⟩、横軸＝それ以外 |α⟩。赤い鏡（横軸）での鏡映がオラクル、緑の鏡（|s⟩ 方向）での鏡映が拡散。反復のたびに角度が (2k+1)θ と増え、90°（真上＝P=100%）に最も近づくのが k=3。その先は行き過ぎて P が下がる。

P(k) = sin²( (2k+1)θ )，　sin θ = 1/√N k 回反復後に正解を測定できる確率。山を越えると下りになる — だから最適停止が要る

5. 古典との勝負 — 「2乗の加速」の意味

古典の総当たりは平均 N/2 回、グローバーは約 (π/4)√N 回。N を大きくしながら差を見てみましょう。N=100万なら 50万回 vs 約785回 — 桁が2つ半違います。ただし √N は「指数的加速」ではありません。N が 100 倍になれば、グローバーの手間も 10 倍に増えます。

古典 N/2 vs グローバー (π/4)√N — 必要なオラクル呼び出し回数

データ数 N

縦軸を対数にする

赤＝古典の期待回数 N/2（最悪は N 回）、緑＝グローバー。線形軸では古典だけが爆発して見える。対数軸に切り替えると、どちらも増えてはいるが傾きが半分（指数が 1 → 1/2）であることが分かる。これが「2乗の加速」。

6. まとめ

オラクル：正解の振幅の符号だけを反転する「答え合わせ回路」。反転だけでは確率は変わらない。
拡散：全振幅を平均まわりで折り返す。オラクルの付けた「見えない印」を振幅の差に変換する。
幾何：2つの鏡映＝1反復あたり 2θ の回転。P(k) = sin²((2k+1)θ) で、約 (π/4)√N 回がピーク。
加速は2乗ぶん：N/2 → √N。しかも √N は証明済みの下界（BBBV定理）で、これ以上速い量子探索は存在しない。

一歩先へ — 振幅増幅の一般性と現実「オラクル＋拡散」の反復は探索専用の技ではない。成功確率 p で当たりを出す任意の量子サブルーチンに同じ反復を適用すると、O(1/√p) 回で成功確率をほぼ1にできる（振幅増幅）。グローバー探索は p = 1/N の特殊ケースにすぎず、最小値探索・衝突発見・モンテカルロ法の分散低減など広く応用が効く。一方で2乗加速は指数加速ほど強くなく、誤り訂正のオーバーヘッドを織り込むと実機で古典に勝てる規模はかなり大きい、という冷静な試算があることも覚えておきたい。