第3章Grover — 振幅増幅

この章の目標

3.1 問題 — 構造のない探索

$N = 2^n$ 個の候補のうち、条件を満たすもの（マークされた解 $w$）を探したい。手がかりは「候補 $x$ を入れると当たりかどうか答えるオラクル」だけ。古典では平均 $N/2$ 回聞くしかありません。Groverはこれを約 $\frac{\pi}{4}\sqrt{N}$ 回にします。$N = 100$万なら、50万回 → 約785回です。

Deutsch-Jozsaと違い、答えそのものが欲しいので「1点にピークを立てる」必要があります。1回の干渉では足りず、少しずつ振幅を答えに寄せる操作を反復する——これが振幅増幅です。

3.2 反復の中身 — 符号反転と「平均まわりの反転」

初期状態は一様重ね合わせ $|s\rangle = \frac{1}{\sqrt N}\sum_x |x\rangle$。Grover反復 $G$ は2手の組み合わせです：

Grover反復
  1. オラクル $O$: 解の振幅の符号を反転（第1章の位相オラクル）。
  2. 拡散演算子 $D = 2|s\rangle\langle s| - I$: すべての振幅を「振幅の平均値 $\mu$ のまわりで反転」する： $$a_x \;\longmapsto\; 2\mu - a_x \qquad \mu = \frac{1}{N}\sum_x a_x$$

拡散の式 $2\mu - a_x$ は「$\mu$ からの距離を保って反対側へ移す」操作です。なぜこれが増幅になるか、$N = 4$、解 $w = 11$ で実際に算数してみます：

例: $N = 4$ は1回で確率1

初期振幅：$(+\tfrac12, +\tfrac12, +\tfrac12, +\tfrac12)$

オラクル：解 $|11\rangle$ の符号を反転 → $(+\tfrac12, +\tfrac12, +\tfrac12, -\tfrac12)$

拡散：平均 $\mu = \frac{\frac12 \cdot 3 - \frac12}{4} = \frac14$。各振幅を $2\mu - a = \tfrac12 - a$ に： 非解 $\tfrac12 \to 0$、解 $-\tfrac12 \to 1$。結果 $(0, 0, 0, 1) = |11\rangle$。

測定すれば確率1で解が出ます。オラクル1回。古典は最悪3回・平均2.25回なので、最小サイズでも既に勝っています。

直観: マイナスに落とした振幅だけが平均の「反対側」に跳ぶ

オラクル後、非解の振幅は平均のわずかに上、解の振幅は（符号反転で）平均のはるか下にいます。平均まわりの反転で、非解は少し下がり、解は大きく上に跳ね上がる——符号反転（位相の刻印）を、拡散が振幅の差に変換する。第1章で「符号だけでは読めない」と学びましたが、Groverの拡散はまさに符号を読み出し可能な大きさに変える干渉装置です。なお $D = H^{\otimes n}(2|0\rangle\langle 0| - I)H^{\otimes n}$ と書けるので（演習3-3）、実装は $H$ 層と「全ゼロだけ符号反転」のオラクル風ゲートで済みます。

3.3 回転の絵と最適回数 — 回しすぎ注意

反復を重ねたときの一般論は、2次元の絵で完全に記述できます。解の状態 $|w\rangle$ と「非解の一様重ね合わせ $|r\rangle$」が張る平面の中で、状態は常に単位ベクトルであり、

事実（Groverの回転）

初期状態 $|s\rangle$ は $|r\rangle$ から角度 $\theta$（$\sin\theta = \frac{1}{\sqrt N}$、解が $M$ 個なら $\sqrt{M/N}$）の位置にあり、Grover反復1回はこの平面内の角度 $2\theta$ の回転である。$k$ 回後、解の測定確率は $$P_k = \sin^2\big((2k + 1)\theta\big)$$ 最適な反復回数は $(2k+1)\theta \approx \frac{\pi}{2}$ となる $k_{\text{opt}} \approx \frac{\pi}{4}\sqrt{N/M}$。

重要な帰結が2つ：

実験3: 振幅増幅を回す（N = 16）

「オラクル」→「拡散」の順にボタンを押して、振幅（符号付き）が変わる様子を追ってください。1反復ごとに解（橙）の確率が上がり、3反復（$k_{\text{opt}} = \lfloor\frac{\pi}{4}\sqrt{16}\rfloor = 3$）で最大、4反復目から下がることを確認しましょう。「自動で1反復」は2手をまとめて実行します。

正直な評価

「Groverでデータベース検索が高速化」という見出しには2つの罠があります。(1) 2次の高速化であって指数ではない。$N$ を倍にすれば量子側の手間も $\sqrt2$ 倍に増えます。(2) オラクルはタダではない。「$x$ が条件を満たすか」を判定する回路（ステップ2第6章の可逆回路）を毎反復実行するコストと、そもそも古典データを量子状態に載せるコスト（QRAM問題）を含めると、実務のデータ検索で勝つのは非常に困難というのが現状の理解です。Groverの真価は、SATのような判定回路が小さく明示的に書ける探索問題への適用と、他のアルゴリズムの部品（振幅増幅サブルーチン）としての汎用性にあります。

演習3

問 3-1ウォームアップ

数列 $(3, 3, 3, -1)$ を「平均まわりの反転」$a \mapsto 2\mu - a$ で変換せよ。次に $(0.4, 0.4, 0.4, 0.4, -0.4)$（$N = 5$ 相当の練習）でも実行せよ。

解答を見る

1つ目：$\mu = \frac{3+3+3-1}{4} = 2$。変換後 $(1, 1, 1, 5)$。2つ目：$\mu = \frac{0.4 \times 4 - 0.4}{5} = 0.24$。変換後 $(0.08, 0.08, 0.08, 0.08, 0.88)$。マイナスに沈んでいる項ほど大きく跳ね上がる——拡散の算数はこれだけです。まず数字に慣れてから式に行くのがこの章の順路です。

問 3-2ウォームアップ

$N = 8$、解1個でGrover反復を2回手計算せよ（振幅は分数のまま追うこと）。各反復後の解の確率を求め、$P_k = \sin^2((2k+1)\theta)$（$\sin\theta = \frac{1}{\sqrt8}$）と一致することを確認せよ。

解答を見る

初期：全振幅 $\frac{1}{2\sqrt2}$。1回目：オラクルで解 $-\frac{1}{2\sqrt2}$。$\mu = \frac{6 \cdot \frac{1}{2\sqrt2}}{8} = \frac{3}{8\sqrt2} \cdot 2 = \frac{3}{4} \cdot \frac{1}{2\sqrt2}$……分数で整理すると：非解 $\to \frac{1}{4\sqrt2}$、解 $\to \frac{5}{4\sqrt2}$。解の確率 $P_1 = \frac{25}{32} \approx 0.781$。2回目：オラクルで解 $-\frac{5}{4\sqrt2}$、$\mu = \frac{7 \cdot \frac{1}{4\sqrt2} - \frac{5}{4\sqrt2}}{8} = \frac{2}{32\sqrt2} = \frac{1}{16\sqrt2}$。非解 $\to \frac{1}{8\sqrt2} - \frac{1}{4\sqrt2} = -\frac{1}{8\sqrt2}$、解 $\to \frac{1}{8\sqrt2} + \frac{5}{4\sqrt2} = \frac{11}{8\sqrt2}$。$P_2 = \frac{121}{128} \approx 0.945$。式でも $\theta = \arcsin\frac{1}{\sqrt8} \approx 20.7°$、$P_1 = \sin^2(62.1°) \approx 0.781$、$P_2 = \sin^2(103.5°) \approx 0.945$ ✓。3回目は $\sin^2(144.9°) \approx 0.33$ に下がることも式から読めます（$N = 8$ の最適は2回）。

問 3-3基本

拡散演算子が $D = H^{\otimes n}\,(2|0\cdots0\rangle\langle 0\cdots0| - I)\,H^{\otimes n}$ と書けることを示せ。ヒント: $H^{\otimes n}|0\cdots0\rangle = |s\rangle$ と $H^{\otimes n}H^{\otimes n} = I$ を使う。中央の $2|0\rangle\langle 0| - I$ は回路としてはどんな操作か。

解答を見る

$H^{\otimes n}(2|0\rangle\langle 0| - I)H^{\otimes n} = 2(H^{\otimes n}|0\rangle)(\langle 0|H^{\otimes n}) - H^{\otimes n}H^{\otimes n} = 2|s\rangle\langle s| - I = D$ ✓。中央の演算子は「$|0\cdots0\rangle$ 以外の全成分の符号を反転」（グローバル位相を除けば「全ゼロだけ反転」と同じ）——つまり「$x = 0$ をマークする位相オラクル」で、多制御Zゲートで組めます。Grover反復全体が「オラクル・$H$ 層・もう1つのオラクル・$H$ 層」という、既習部品の4段重ねであることが分かります。

問 3-4基本

$N = 2^{20} \approx 10^6$、解1個のとき、(a) 最適反復回数、(b) 古典の期待クエリ数、(c) 反復数を最適の2倍にしたときの成功確率、をそれぞれ求めよ。

解答を見る

(a) $k_{\text{opt}} \approx \frac{\pi}{4}\sqrt{2^{20}} = \frac{\pi}{4} \cdot 1024 \approx 804$ 回。(b) 平均 $N/2 \approx 52$万回。(c) $(2k+1)\theta \approx \pi$ となり $P \approx \sin^2\pi = 0$。2倍回すと成功確率はほぼゼロ——「多めにやっておけば安心」が通用しない、$\sin^2$ の振動の帰結です。解の個数 $M$ が未知だと $k_{\text{opt}}$ が決められないという実務上の問題があり、$M$ を推定しながら回す拡張（量子カウンティング。位相推定の応用！）が存在します。

問 3-5基本

解が $M$ 個（$M \ll N$）あるとき $\sin\theta = \sqrt{M/N}$ で、最適反復は約 $\frac{\pi}{4}\sqrt{N/M}$ 回になる。$N = 2^{20}$ で解が1024個なら何回か。解が多いほど楽になる理由を直観で述べよ。

解答を見る

$\sqrt{N/M} = \sqrt{2^{20}/2^{10}} = 2^5 = 32$、$k_{\text{opt}} \approx \frac{\pi}{4} \cdot 32 \approx 25$ 回。直観：初期状態が既に解の部分空間と $\sin\theta = \sqrt{M/N}$ の重なりを持っており、$M$ が大きいほど出発点から解に「近い」ので、回すべき角度が少なくて済む。古典でも解が多ければ早く見つかる（期待 $N/M$ 回）ので、優位は常に2次（$\sqrt{N/M}$ vs $N/M$）です。

問 3-6考え方

「オラクルは1回で全 $x$ の判定を終えているのだから、オラクル直後に測定すればよいのでは？」——この発想が失敗する理由を述べ、拡散演算子が果たしている役割を第2章の $H^{\otimes n}$ と比較せよ。

解答を見る

オラクル直後の確率分布は一様のまま（符号は確率に出ない——第1章）。測っても $\frac{1}{N}$ でしか当たらず、古典の乱択と同じです。拡散は符号の刻印を振幅の差に変換する干渉装置で、役割はDJの $H^{\otimes n}$ と同じ「第3幕」。違いは、DJが1回の干渉で確率1に持ち込める（符号パターンが全会一致 vs 真っ二つという極端な構造を持つ）のに対し、探索では1回の干渉で動かせる振幅が $O(1/\sqrt N)$ しかないため、「刻む→畳む」を $O(\sqrt N)$ 回積み重ねる必要があること。問題の構造が弱いほど干渉の回数で稼ぐ——3幕構成の「反復版」という位置づけです。

問 3-7考え方

次の主張を評価せよ：「Groverアルゴリズムを使えば、$2^{128}$ 通りの鍵空間を持つAES-128の総当たりが $2^{64}$ 回で済む。よって量子コンピュータの登場でAES-128は即座に無意味になる」。技術的に正しい部分と、実務的に誇張されている部分を切り分けよ。

解答を見る

正しい部分：鍵判定回路はオラクルとして構成可能で、クエリ数が $O(2^{64})$ になるのは理論的に正当。だからNISTの耐量子基準でも「対称鍵は鍵長を倍に（AES-256へ）」が推奨されます。誇張の部分：(1) $2^{64}$ 回の逐次的なGrover反復（並列化で割れない——$\sqrt N$ の下界は逐次クエリの話）は、1反復1マイクロ秒でも約58万年。(2) 各反復でAES全体の可逆回路を誤りなく実行する必要があり、エラー訂正込みの資源は天文学的。結論：「原理的に2次の脅威があるので鍵長で余裕を持たせる」が正確で、「即座に無意味」は誇張。一方、Shorが効く公開鍵暗号（RSA・楕円曲線）は多項式時間で崩れるため深刻度が質的に違う——この対比は第6・7章で完成させます。

理解チェックリスト