振幅増幅と振幅推定

グローバー探索を一般化する

グローバー探索 は、一様重ね合わせから出発して「解の振幅の符号反転」と「平均のまわりでの反転（拡散）」を繰り返し、成功確率を二次的に押し上げるアルゴリズムでした。振幅増幅（Amplitude Amplification）は、この構造から「出発点が一様重ね合わせであること」という制約を外した一般枠組みです。

出発点を、任意の状態生成演算子 A が作る状態 |ψ> = A|0> とします。ここで測定して「良い状態（good）」が得られる確率を a とすると、|ψ> は良い部分 |good> と悪い部分 |bad> に直交分解できます。

|ψ> = A|0> = sinθ · |good> + cosθ · |bad>

  ・a = sin²θ  … 良い状態を測る確率（成功確率）
  ・|good>, |bad> は直交する正規化状態
  ・グローバーは A = H⊗n（一様重ね合わせ）、a = M/N の特殊例

グローバー法との違いは、良い状態の判定を「解かどうか」という探索オラクルに限らず、任意の述語で与えてよい点です。良い状態を選び出すオラクル S_χ（good なら位相を反転）と、状態 |ψ> に関する反転 S_ψ を組み合わせれば、探索と同じ「2つの鏡映＝回転」の幾何が再現できます。

増幅演算子 Q と回転角 2θ

振幅増幅の1反復は、次の演算子 Q で表されます。これがグローバー反復の一般化です。

Q = − A S_0 A† S_χ

  S_χ : 良い状態 |good> の位相を反転（good 判定オラクル）
  S_0 : |0> の位相を反転（S_0 = I − 2|0><0|）
  A S_0 A† : 状態 |ψ> に関する反転（inversion about |ψ>）

S_χ は |good> 軸に関する鏡映、A S_0 A† は |ψ> に関する鏡映です。2つの鏡映の合成は回転になるという幾何の定理から、Q は |bad>・|good> が張る2次元平面内で状態を 1反復あたり 2θ 回転させます。k 回適用した後の状態は、グローバーと同じ形になります。

Qᵏ |ψ> = sin((2k+1)θ) · |good> + cos((2k+1)θ) · |bad>

  良い状態を測る確率 = sin²((2k+1)θ)

成功確率を最大（≒1）にするには (2k+1)θ ≈ π/2 を選べばよく、最適反復回数は k ≈ (π/(4θ)) − 1/2 です。θ が小さいとき θ ≈ √a なので、k はおよそ (π/4)/√a。初期成功確率 a の平方根に反比例する回数で確率を1へ持ち上げられる、というのが振幅増幅の核心です。

振幅推定：QPE で成功確率を読む

振幅増幅は成功確率 a を大きくする手続きでしたが、振幅推定（Amplitude Estimation, QAE）は a そのものを測る手続きです。鍵は、増幅演算子 Q の固有値にあります。Q は2次元平面内の 2θ 回転なので、その固有値は次の複素単位数です。

Q の固有値 = exp(± i·2θ)     （sin²θ = a）

  → 固有値の「位相」に成功確率 a の情報が乗っている

位相に情報が乗っているなら、量子フーリエ変換 を用いた**量子位相推定（QPE）**でそれを取り出せます。手続きは次のとおりです。

1. m 量子ビットのカウントレジスタを H で一様重ね合わせにする
2. 制御-Q を Q^(2^0), Q^(2^1), ..., Q^(2^(m-1)) と適用（位相キックバック）
3. カウントレジスタに逆量子フーリエ変換を掛ける
4. 測定して整数 y を得る → θ の推定値 θ̃ = π·y / 2^m
5. ã = sin²(θ̃) を成功確率の推定値とする

これは ショアの位数発見 と同じ QPE の型です。ショアが「剰余べき乗の周期」を位相として読むのに対し、振幅推定は「成功確率 a」を Q の固有位相 2θ として読む、という違いだけです。

モンテカルロに対する二次高速化

振幅推定の実用的インパクトは、モンテカルロ積分・期待値推定の二次高速化です。両者の誤差スケーリングを対比すると差が一目で分かります。

古典モンテカルロで期待値を誤差 ε まで求めるには、中心極限定理により標本数が O(1/ε²) 必要です。振幅推定は誤差が評価回数 M に対して O(1/M) で縮むため、必要回数は O(1/ε)。同じ精度を得る手間が二乗ぶん軽くなります。

古典 MC :  誤差 ε に必要な標本数  N ~ 1/ε²
量子 QAE:  誤差 ε に必要な評価数  M ~ 1/ε

  例）ε を 1/100 にしたいとき
    古典: N は約 10,000 倍
    量子: M は約   100 倍   ← 二乗ぶん有利

なぜ効くかは、グローバー探索の加速理由と同じ「振幅と確率の非対称性」です。測定確率は振幅の2乗なので、振幅（＝ √確率）を線形に精密化できれば、確率の推定誤差は二乗のペースで縮みます。この非対称性が探索では反復回数 √N を、推定では標本数 1/ε を生みます。応用は金融のデリバティブ評価・リスク（VaR）計算、数値積分、分配関数の推定など、モンテカルロが主力の領域全般です。

QPE を使わない振幅推定

初期の振幅推定は上記のとおり QPE（したがって QFT と補助レジスタ）を要し、回路が深くなります。近年はQPE を用いない振幅推定が主流で、Q を作用させた状態を種々の反復回数 k で測定し、良い状態が出た頻度を古典側で sin²((2k+1)θ) にフィッティングして θ を最尤推定します。

これらは同じ「Q の固有位相 2θ を読む」目的を、QFT を後段の古典処理に置き換えて達成します。漸近的には正準版と同じ O(1/ε) 付近のスケーリングを保ちつつ、必要な量子ビット数と回路深さを削れるため、誤り耐性が限られる時代の橋渡しとして重視されています。

まとめ

振幅増幅と振幅推定は、グローバー探索の「2つの鏡映＝回転」という幾何を、探索の枠を超えて再利用する対の技法です。要点は3つ。(1) 振幅増幅は任意の状態生成 A と良い状態オラクルがあれば成功確率 a を約 (π/4)/√a 回で1へ押し上げる汎用ブースタで、グローバー法はその特殊例であること。(2) 振幅推定は増幅演算子 Q の固有位相が 2θ（sin²θ = a）である事実を使い、量子位相推定で a そのものを読む手続きで、ショアと同じ QPE の型に載ること。(3) その推定誤差は評価回数に対し O(1/M) で縮み、古典モンテカルロの O(1/√M) に対する二次高速化を与えるが、状態生成コストと誤り耐性という前提ゆえに実用は精度要求の高い領域に限られること。探索の √N、推定の 1/ε——いずれも「確率は振幅の2乗」という測定規則が生む同じ非対称性の現れだと押さえれば、両者を一本の絵の上で理解できます。