グローバー探索アルゴリズム

探索を「振幅の幾何」で捉える

グローバー探索アルゴリズム（Grover's algorithm, 1996）は、整列も索引もない「非構造探索」を二次的に高速化する量子アルゴリズムです。N 個の候補の中から、条件を満たす解を探す問題を考えます。古典的には候補を1つずつ判定するしかなく、最悪 N 回・平均 N/2 回の判定が必要です。グローバー法は、オラクル（正解かどうかを判定する黒箱）の呼び出しをおよそ √N 回に抑えます。N = 100万 なら100万回が約1000回に減る計算です。

鍵は、量子状態を確率振幅（複素数の重み）のベクトルとして扱い、正解に対応する振幅だけを反復的に大きくしていく「振幅増幅」です。ここでは、その内部動作を「2次元平面上のベクトルの回転」という幾何として正確に導出します。前提となる重ね合わせ・測定・確率振幅の基礎は、本記事内で必要分を都度補いながら進めます。

舞台設定：一様重ね合わせとオラクル

探索空間を N = 2ⁿ とし、n 量子ビットで各候補に基底状態 |x> を割り当てます。条件を満たす解の集合を W、その個数を M（まずは M = 1 を想定）とします。

出発点は、全候補に等しい振幅を与えた一様重ね合わせです。各基底の振幅は 1/√N になります。

|s> = (1/√N) Σ_x |x>        （x は 0 .. N-1 の全候補）

  ・各候補の確率振幅はすべて 1/√N
  ・この時点で測定すると、どの候補も確率 1/N で等確率

判定はオラクル U_f が担います。オラクルは解 x（x が W に属する）に対してのみ位相を反転する演算子です。

U_f |x> = -|x>     （x が解のとき）
U_f |x> =  |x>     （x が解でないとき）

  → 解の基底の「振幅の符号」だけをマイナスにする（位相キック）

グローバー反復：位相反転と拡散の2段

1回のグローバー反復 G は、次の2つの演算子の積です。

G = D · U_f

  ① U_f : 解の振幅の符号を反転（オラクル）
  ② D   : 平均のまわりで全振幅を反転（拡散演算子, Diffusion）

拡散演算子 D は「平均のまわりでの反転（inversion about the mean）」を行います。全振幅の平均を μ とすると、各振幅 a を 2μ − a に写します。

拡散 D の作用（成分ごと）:  a_x  ->  2μ − a_x

  μ = (1/N) Σ_x a_x        （全振幅の平均）
  演算子表現:  D = 2|s><s| − I     （|s> は一様重ね合わせ）

この2段が振幅に何を起こすかを数値で追うと、増幅の直感が一気に鮮明になります。N = 4、解を1つ（M = 1）とした最初の1反復を示します。

N = 4 ではわずか1反復で解の確率が1に達します（0.5 → 1.0）。ポイントは U_f で解の振幅を平均より下へ落とし、2μ − a の反転で平均を挟んで大きく跳ね上げること。非解の振幅は平均のすぐ上にあるため反転でほぼ平均へ引き戻され、相対的に削られます。

なぜ計算量が「およそ √N」に減るのか

1反復で確率がどれだけ増えるかを見積もると、√N の由来が定量的に見えます。初期状態で解の振幅は 1/√N。振幅の1乗が伸びていく点が本質です。

1反復あたり、解の振幅は約 2/√N ずつ増える（初期の増分の目安）

  初期の解の振幅            : 1/√N
  必要な振幅（確率≈1）      : ほぼ 1
  1反復の増分              : おおよそ 2/√N

  → 必要反復数 ≈ 1 / (2/√N) = (√N)/2 のオーダー = O(√N)

古典探索が「確率 1/N を稼ぐのに N 件を舐める」のに対し、量子では確率ではなく振幅（√確率）が線形に増えるため、必要回数が √N のオーダーに落ちます。これが二次高速化の数理的な核心です。次節の幾何を使うと、この見積もりが厳密な形で正当化されます。

反復回数の幾何的解釈：2θ の回転

グローバー法の美しさは、全状態がたった2次元の平面内にとどまる点にあります。次の2つの直交ベクトルを定義します。

|W>  = (1/√M) Σ_{x が解}    |x>      （解だけの一様重ね合わせ）
|W⊥> = (1/√(N−M)) Σ_{x が非解} |x>   （非解だけの一様重ね合わせ）

  ・|W> と |W⊥> は直交（共通の基底を持たない）
  ・初期状態 |s> はこの2つの線形結合で書ける

初期状態 |s> を、この平面上で |W⊥> から測った角度 θ のベクトルとして表せます。

|s> = cosθ |W⊥> + sinθ |W>

  sinθ = √(M/N)      （解の振幅の合計 = √M · (1/√N)）
  M = 1 のとき sinθ = 1/√N なので、θ ≈ 1/√N（小さい角）

ここでグローバー反復 G = D·U_f は、この平面内での回転そのものになります。U_f は |W⊥> 軸に関する鏡映（解成分の符号反転）、D は |s> に関する鏡映で、2つの鏡映の合成は回転という幾何の定理から、G は状態を |W> の方向へ 1反復あたり 2θ だけ回すことが導けます。

G を k 回適用した後の状態:

  Gᵏ|s> = cos((2k+1)θ) |W⊥> + sin((2k+1)θ) |W>

  ・|W> 成分（= 解を測る確率振幅）は sin((2k+1)θ)
  ・回すたびに解の方向へ 2θ 近づく

解を測定する確率は |W> 成分の2乗、すなわち sin²((2k+1)θ) です。これを最大（=1）にしたいので、角度が π/2 になる回数を選びます。

(2k+1)θ ≈ π/2  を解いて

  k ≈ π/(4θ) − 1/2

  θ ≈ √(M/N) なので

  最適反復回数 k_opt ≈ (π/4)·√(N/M)

  M = 1 なら k_opt ≈ (π/4)√N ≈ 0.785 √N

各要素の対応関係を一望すると、幾何の描像が固まります。

一般化と限界：振幅増幅・最適性・複数解

平面回転の描像から、実務・試験で問われる論点が自然に導けます。

• 振幅増幅（Amplitude Amplification）への一般化：初期状態が一様重ね合わせ |s> でなくても、任意の準備演算子 A と「良い状態」を判定するオラクルがあれば、同じ「2つの鏡映＝回転」の構造で成功振幅を増幅できます。グローバー法はその特殊例です。
• 複数解（M > 1）：sinθ = √(M/N) なので解が多いほど θ が大きく、必要反復は (π/4)√(N/M) と少なくて済みます。ただし M が未知だと k_opt が決まらないため、解の個数を推定する量子カウント（位相推定の応用）や、反復回数をランダム化する手法を併用します。
• 最適性（下界）：任意の量子探索アルゴリズムはオラクル呼び出しが Ω(√N) 必要だと証明されており（BBBV 下界）、グローバー法はこの下界を定数倍まで達成する最適解です。これ以上の高速化は、問題に構造がない限り原理的に不可能です。

まとめ

グローバー探索アルゴリズムは、非構造探索を 「オラクルによる位相反転」＋「平均のまわりでの反転（拡散）」の反復で二次的に高速化する手法です。要点は3つ。(1) 測定確率が振幅の2乗である以上、振幅を線形に伸ばせば必要回数が √N オーダーに落ちること。(2) 全状態は解と非解が張る2次元平面にとどまり、1反復は角度 2θ（sinθ = √(M/N)）の回転として厳密に記述できること。(3) 成功確率は sin²((2k+1)θ) で、最適反復回数は約 (π/4)√(N/M)——回しすぎると下がるため回数管理が要ること。この幾何を押さえれば、二次加速の理由も、振幅増幅という一般枠組みへの拡張も、Ω(√N) という最適性の主張も、一本の絵の上で説明できるようになります。