量子位相推定（QPE）

QPE が解く問題：固有位相の読み出し

量子位相推定（QPE: Quantum Phase Estimation）は、Shor の素因数分解や HHL 線形方程式ソルバの内部で共通して使われる基本サブルーチンです。解く問題は一言で言えば「ユニタリ演算 U の固有値の位相を、古典的に読めるビット列として取り出す」こと。ユニタリの固有値は必ず絶対値1の複素数なので e^{2πiφ}（0 ≤ φ < 1）の形をしており、この φ を推定するのが QPE です。

前提として、U の固有状態 |u> が1つ手元にあり、それを準備できるものとします。

U|u> = e^{2πiφ} |u>     （φ は 0 以上 1 未満の未知の実数）

φ は連続量ですが、QPE は有限個の量子ビットでその2進近似を返します。ここでのキモは「固有状態 |u> は測定しても位相の情報を吐き出さない」という点です。|u> を直接測っても、グローバル位相 e^{2πiφ} は観測不能だからです。QPE はこの隠れた位相を、別に用意した制御レジスタの振幅の周波数へ書き写し、それを読み出せる形に変換する巧妙な手続きです。前提となるユニタリと固有状態の考え方は /quantum/quantum-gates-circuits/ の内容を踏まえると読みやすくなります。

回路の骨格：2つのレジスタ

QPE の回路は2つのレジスタから成ります。

手続きは3段階です。各段で「何が起きているか」を追うのが理解の近道になります。

1. 重ね合わせ生成 : 制御レジスタ t 量子ビットにアダマール H を掛け、
   0..2^t-1 の全整数を等振幅で重ね合わせる。
2. 制御ユニタリ   : 制御ビット k を制御に U^{2^k} を適用（位相キックバック）。
   → 制御レジスタが (1/√2^t) Σ_x e^{2πi·φ·x} |x> になる。
3. 逆QFT + 測定   : 制御レジスタに逆QFT を掛け、φ に対応する基底へ集約して測定。

位相キックバック：φ を振幅の周波数に埋め込む

第2段の「制御 U^{2^k}」がなぜ位相を制御レジスタへ移すのか。ここが QPE で最も本質的な部分です。制御ユニタリは「制御ビットが |1> のときだけ標的に U を掛ける」ゲートですが、標的が U の固有状態のときは特別な振る舞いをします。

制御-U ( |1>_control ⊗ |u> ) = |1>_control ⊗ (U|u>)
                             = |1>_control ⊗ e^{2πiφ} |u>
                             = e^{2πiφ} |1>_control ⊗ |u>

固有状態には U を掛けても状態が変わらず、位相 e^{2πiφ} が係数として前に出るだけです。この位相は数式上どちらの因子にも属せますが、制御ビットが |1> のときにだけ付くので、実質的に制御ビット側の相対位相として作用します。これを位相キックバック（phase kickback）と呼びます。固有状態 |u> は最後まで変化せず、位相だけが制御レジスタへ「蹴り返される」わけです。

制御ビット k には U を 2^k 回、すなわち U^{2^k} を掛けます。固有状態に対して U^{2^k}|u> = e^{2πi·φ·2^k}|u> なので、制御ビット k の |1> 成分には位相 e^{2πi·φ·2^k} が乗ります。全ビットにわたる寄与を集めると、制御レジスタは次の状態になります。

(1/√2^t) Σ_{x=0}^{2^t-1} e^{2πi · φ · x} |x>

逆QFT：周波数を1つの基底に復調する

第2段を終えた制御レジスタの状態 (1/√2^t) Σ_x e^{2πi·φ·x}|x> を、量子フーリエ変換（QFT）の定義と見比べます。QFT は |j> を (1/√N)Σ_k e^{2πi·jk/N}|k> へ写す変換でした（N = 2^t）。両者を並べると、上の状態は基底 |φ·2^t> に QFT を掛けた出力とちょうど同じ形をしていることが分かります。

したがって逆QFT（QFT†）を掛ければ、周波数として散らばった位相情報が1つの基底状態に集約されます。QFT と逆QFT の作用の詳細は /quantum/quantum-fourier-transform/ を参照してください。

QFT† [ (1/√2^t) Σ_x e^{2πiφx} |x> ]  ──►  |round(φ · 2^t)>  （φ·2^t が整数の場合は厳密に）

φ が 2^t の逆数の整数倍でぴったり表せる（φ = j/2^t）とき、逆QFT の出力は基底 |j> に確率1で集まり、測定すれば j が得られて φ = j/2^t が厳密に読めます。位相キックバックが「周期 1/φ の波を書き込む変調」、逆QFT が「その波を1点に立ち上げる復調」だと捉えると、役割分担が明快になります。

精度と補助量子ビット数：本質は φ が割り切れない場合

現実の φ は一般に j/2^t の形にぴったり収まりません。このとき逆QFT の出力は単一の基底に集中せず、φ に最も近い j/2^t の周辺に山を作った確率分布になります。測定すると最良推定（最も近い t ビット値）が最大確率で出ますが、隣接値が出る確率も残ります。

そこで、追加の補助量子ビットを制御レジスタに足して成功確率を底上げします。上位 n ビットを 1 - ε 以上の確率で正しく得たい場合、必要な制御レジスタ幅 t は次の見積もりで与えられます。

t = n + ceil( log2( 2 + 1/(2ε) ) )

追加分 ceil(log2(2 + 1/(2ε))) が「裾の確率をどこまで削るか」を決めるバッファです。例えば上位10ビットを 99%（ε = 0.01）の確率で当てたいなら、追加は ceil(log2(2 + 50)) = ceil(log2(52)) = 6 ビットで、合計 t = 16 量子ビットになります。目的の精度 n に対し、成功確率を上げるコストは追加ビット数の対数でしか増えない、という点が重要です。

Shor と HHL での役割

QPE 単体は「位相を読む」だけの部品ですが、対象のユニタリ U を差し替えることで様々なアルゴリズムの中核になります。

Shor の位数発見では、U を剰余乗算ユニタリ U|y> = |a·y mod N> に取ります。この U の固有位相はちょうど s/r（r は求めたい位数、s は整数）になるため、QPE で s/r を読み、連分数展開で分母 r を復元します。素因数分解が QPE の一適用例に帰着する全体像は /quantum/shor-factoring-algorithm/ で扱っています。ここで固有状態 |u_s> を事前に用意できない問題は、|1> が全固有状態の一様重ね合わせになっている事実で回避され、どの s が出ても連分数で r に辿り着けます。

HHL 線形方程式ソルバでは、U = e^{iAt}（A は解きたい連立方程式の係数行列、エルミート）を対象にします。A の固有値 λ_j が U の固有位相 λ_j t/(2π) として現れるので、QPE で各固有値をレジスタに書き出します。その値を条件付き回転で逆数 1/λ_j に変換し、最後に逆QPE で位相レジスタを掃除する——これが A x = b を量子的に解く骨格です。QPE は「行列の固有値を計算基底の数値として取り出す」役目を担います。

実機での制約

理論上のゲート数は穏当でも、実機での QPE には固有の壁があります。最大のコストは制御 U^{2^k} の実装です。k が制御レジスタの最上位に近づくと U を 2^k 回相当（U^{2^{t-1}} は約 2^{t-1} 回分）適用する必要があり、素朴に展開すると回路深さが位相ビット数に対して指数的に膨らみます。Shor のように U を繰り返し二乗法で効率実装できる特別な構造がなければ、この段が支配的になります。

反復位相推定（Iterative Phase Estimation, IPE）は、制御レジスタを1量子ビットに縮め、位相の各桁を最下位から順に測定・古典フィードバックしながら求める変種です。回路幅を t から1へ落とせるため、補助量子ビットに乏しい NISQ 機での QPE 実装ではしばしばこちらが選ばれます。精度と成功確率のトレードオフは基本の QPE と同じ枠組みで整理できます。

まとめ

量子位相推定の要点は次の4点に集約されます。第一に、QPE はユニタリ U の固有状態 |u> に対し固有位相 φ（U|u> = e^{2πiφ}|u>）をビット列として読み出す基本サブルーチンで、位相キックバックで φ を制御レジスタの振幅の周波数に埋め込むこと。第二に、その周波数を逆QFTで1つの計算基底へ復調し、測定で φ の2進近似を得ること。第三に、制御レジスタ t ビットは t ビット精度を与えるが成功確率は約 4/π^2 にとどまり、上位 n ビットを 1-ε で当てるには t = n + ceil(log2(2 + 1/(2ε))) の補助量子ビットが要ること。第四に、U を差し替えることで Shor の位数発見（位相 s/r）や HHL（固有値の逆数化）の中核になり、実機では制御 U^{2^k} の深さとコヒーレンス時間の競合が主なボトルネックになること。