第5章位相推定 — 固有値を読み出す万能機械
この章の目標
- 位相推定の回路を「キックバックの束 → 逆QFT」として理解する
- $n = 2$、$U = S$ の場合を手計算し、位相が2進小数として読めることを確かめる
- 固有状態が用意できなくても（重ね合わせでも）動く理由を理解する — Shorへの橋
5.1 問題設定
ユニタリ $U$ とその固有状態 $|u\rangle$ が与えられている：$U|u\rangle = e^{2\pi i \varphi}|u\rangle$（$0 \le \varphi < 1$）。固有値の位相 $\varphi$ を $n$ ビットの精度で推定せよ。使ってよい操作は、制御$U^{2^j}$（$U$ を $2^j$ 回掛ける操作の制御版）。
「固有値を測る」は一見地味ですが、これが量子アルゴリズム界の万能サブルーチンです。ステップ2問3-8で予告した通り、多くの問題（周期発見＝Shor、量子カウンティング、量子化学のエネルギー計算）が「うまい $U$ を作って位相推定に投げる」形に帰着します。
5.2 回路 — 部品はすべて既習
カウント |0⟩ ──[H]──────●────────────┐ ┌──[M]══
レジスタ |0⟩ ──[H]───●──┼────────────┤ 逆QFT ├──[M]══ → φ の2進小数
(n本) |0⟩ ──[H]─●─┼──┼────────────┤ ├──[M]══
│ │ │ └─────────┘
固有状態 |u⟩ ──────[U¹]─[U²]─[U⁴]───────────────────── （変化しない）第1幕：カウントレジスタ $n$ 本に $H$。第2幕：$j$ 番目のカウントビットを制御に、$U^{2^j}$ を固有状態レジスタへ。キックバック（ステップ2第3章）により、$j$ 番目のビットに位相 $e^{2\pi i \varphi 2^j}$ が乗ります： $$\bigotimes_{j=n-1}^{0} \frac{|0\rangle + e^{2\pi i \varphi 2^j}|1\rangle}{\sqrt2} \;=\; \frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1} e^{2\pi i \varphi k}\,|k\rangle$$ （積を展開すると $k$ の2進展開の各ビットから位相が集まり、合計 $\varphi k$ になります——演習5-2）。
この状態、どこかで見た形です。$\varphi = \frac{j_0}{2^n}$（ちょうど $n$ ビットで書ける値）なら、これは第4章のQFTの出力そのもの：$\mathrm{QFT}|j_0\rangle$。だから第3幕は当然、逆QFT（QFT回路を逆順・随伴で実行）： $$\mathrm{QFT}^{-1}\left(\frac{1}{\sqrt{2^n}}\sum_k e^{2\pi i \frac{j_0}{2^n} k}|k\rangle\right) = |j_0\rangle$$ 測定すれば確率1で $j_0$、すなわち $\varphi = 0.j_{n-1}\cdots j_0$（2進小数）がそのまま読めます。
$S|1\rangle = i|1\rangle = e^{2\pi i/4}|1\rangle$ なので固有状態 $|u\rangle = |1\rangle$、$\varphi = \frac14$。キックバック後のカウントレジスタは $$\frac{|0\rangle + e^{2\pi i \cdot \frac14 \cdot 2}|1\rangle}{\sqrt2} \otimes \frac{|0\rangle + e^{2\pi i \cdot \frac14}|1\rangle}{\sqrt2} = \frac{|0\rangle + (-1)|1\rangle}{\sqrt2} \otimes \frac{|0\rangle + i|1\rangle}{\sqrt2}$$ 成分で書くと $\frac12(1, i, -1, -i)$——これは $\mathrm{QFT}_4|1\rangle$（$\mathrm{QFT}_4$ の第1列、問4-1の隣の列）。逆QFTで $|01\rangle$、測定値 $1$。$\varphi = \frac{1}{2^2} = \frac14$ ✓。ステップ2問3-8の「Tを何回も掛けて位相を巻き取る」遊びが、逆QFTという読み出し装置を得て完成したのがこの回路です。
5.3 割り切れない位相と精度
$\varphi$ が $n$ ビットで書き切れない場合（例 $\varphi = 0.3$）、測定分布は「最も近い $n$ ビット値」を中心に集中します。理論的には最良近似値が出る確率は最低でも $\frac{4}{\pi^2} \approx 0.41$、±1隣まで含めればはるかに高確率。精度を1ビット上げたければカウントビットを1本増やす（そして $U$ の適用回数は倍になる）——精度は量子ビット数に対して指数的に向上します。実験5で分布のにじみ方を確認してください。
5.4 固有状態が用意できないときこそ本領 — Shorへの橋
固有状態レジスタに固有状態の重ね合わせ $\sum_u c_u|u\rangle$ を入れると、位相推定の出力は「確率 $|c_u|^2$ でどれかの $u$ が選ばれ、その $\varphi_u$ が読める」という結果になる（カウントレジスタと固有状態レジスタがエンタングルし、測定で一方に決まる）。
これが決定的に重要です。第6章のShorでは、目的のユニタリの固有状態を個別に用意することはできません。しかし扱いやすい状態（$|1\rangle$ など）が固有状態たちの一様な重ね合わせになっていることを利用して、「どれかの固有値がランダムに読める」で十分な設計にします。どの固有値が出てもそこから周期が復元できる——第4章の「オフセット不変性」と同じ精神です。
位相推定は誤り耐性のある（エラー訂正された）量子コンピュータ向けのアルゴリズムです。制御$U^{2^j}$ は $j$ が大きいと $U$ を膨大な回数コヒーレントに（干渉を保ったまま）適用する必要があり、現行のNISQ機ではノイズに埋もれます。量子化学で「位相推定でエネルギーが計算できる」という記述を見たら、それは将来の誤り耐性機の話で、現行機ではVQE（第7章）のような浅い回路の近似手法が使われている——という時代の区別が、ニュース読解では重要です。
演習5
$U = Z$（$Z|1\rangle = e^{2\pi i \cdot \frac12}|1\rangle$、$\varphi = \frac12$）、$n = 2$、固有状態 $|1\rangle$ で位相推定を手計算せよ。キックバック後の状態、逆QFT後の測定値、読み取れる $\varphi$ を答えよ。
解答を見る
キックバック後：$\frac{|0\rangle + e^{2\pi i \cdot \frac12 \cdot 2}|1\rangle}{\sqrt2} \otimes \frac{|0\rangle + e^{2\pi i \cdot \frac12}|1\rangle}{\sqrt2} = |+\rangle \otimes |-\rangle$。成分は $\frac12(1, -1, 1, -1) = \mathrm{QFT}_4|2\rangle$（問4-1！）。逆QFTで $|10\rangle$、測定値 $2$、$\varphi = \frac{2}{4} = \frac12$ ✓。$j = 1$ 側のビットは $e^{2\pi i} = 1$ で $|+\rangle$ のまま——「位相が一周して見えなくなる」のも2進小数の桁上がりとして正しい動作です。
キックバック後の積 $\bigotimes_j \frac{|0\rangle + e^{2\pi i \varphi 2^j}|1\rangle}{\sqrt2}$ を展開すると $\frac{1}{\sqrt{2^n}}\sum_k e^{2\pi i \varphi k}|k\rangle$ になることを、$n = 2$ で確かめよ。ヒント: $k = 2k_1 + k_0$ の2進展開。位相は $e^{2\pi i\varphi(2k_1 + k_0)}$ と掛け算で集まる。
解答を見る
$\frac{(|0\rangle + e^{2\pi i\varphi \cdot 2}|1\rangle)(|0\rangle + e^{2\pi i\varphi}|1\rangle)}{2}$ を展開：$|00\rangle$ の係数 $1 = e^{2\pi i\varphi \cdot 0}$、$|01\rangle$: $e^{2\pi i\varphi \cdot 1}$、$|10\rangle$: $e^{2\pi i\varphi \cdot 2}$、$|11\rangle$: $e^{2\pi i\varphi \cdot 3}$。確かに $\frac12\sum_k e^{2\pi i\varphi k}|k\rangle$ ✓。ビットごとの位相が掛け算され、指数の足し算として $\varphi k$ に集まる——第1章問1-3（テンソル積の積→指数の内積）とQFTの積表現（4.3節）と同じ計算パターンの三度目の登場です。
第3幕がなぜ $H^{\otimes n}$ ではなく逆QFTなのかを説明せよ。ヒント: $H^{\otimes n}$ が読める位相パターンは $(-1)^{s \cdot x}$ 型（±1のみ）。位相推定で現れるパターンは？
解答を見る
Deutsch-Jozsa/BVで刻まれる位相は $\pm 1$（1ビットの位相）で、これを読む干渉装置が $H^{\otimes n}$ でした。位相推定で刻まれるのは $e^{2\pi i\varphi k}$ という連続的な回転位相で、その周波数 $\varphi$ を読むにはフーリエ変換が必要です。$H^{\otimes n}$ は「QFTの $N = 2$ を並べたもの」であり、ビット間の位相関係（$CR_k$ が拾う部分）を見ません。刻んだ位相の「言語」に合わせて、読み出しの干渉装置を選ぶ——±1言語なら $H^{\otimes n}$、回転言語なら逆QFT。3幕構成の第3幕には設計の自由度があり、それがアルゴリズムの個性になっています。
$\varphi$ を誤差 $10^{-3}$ 以下で推定したい。カウントビットは何本必要か。また制御$U^{2^j}$ の最大の $j$ での $U$ の適用回数はいくらになるか。
解答を見る
$2^{-n} \le 10^{-3}$ より $n = 10$ 本（$2^{-10} \approx 0.98 \times 10^{-3}$）。最大の制御は $U^{2^9} = U^{512}$、つまり $U$ を512回コヒーレントに適用します。精度はビット数に指数的（1ビット追加で精度2倍）、コストは $U$ の適用回数として同じく指数的（合計 $2^n - 1$ 回）。「精度が欲しければ $U$ をたくさん回す」——ステップ2問3-8の巻き取りのイメージ通りです。
固有状態レジスタに $|u_0\rangle$ と $|u_1\rangle$（固有位相 $\varphi_0 \ne \varphi_1$）の重ね合わせ $\frac{|u_0\rangle + |u_1\rangle}{\sqrt2}$ を入れた。キックバック直後の全体状態を書き、(a) カウントレジスタ単独では「$\varphi_0$ の回転と $\varphi_1$ の回転の重ね合わせ」になっていること、(b) 測定でどちらか一方の $\varphi$ が確率 $\frac12$ で得られること、を説明せよ。
解答を見る
制御$U^k$ は固有状態を変えないので、全体は $$\frac{1}{\sqrt2}\Big(\big(\tfrac{1}{\sqrt{2^n}}\textstyle\sum_k e^{2\pi i\varphi_0 k}|k\rangle\big)|u_0\rangle + \big(\tfrac{1}{\sqrt{2^n}}\textstyle\sum_k e^{2\pi i\varphi_1 k}|k\rangle\big)|u_1\rangle\Big)$$ ——カウントレジスタと固有状態レジスタが「どの周波数か」でエンタングルした状態です。逆QFT後にカウントを測ると、$|u_0\rangle$ の枝からは $\varphi_0$ 付近、$|u_1\rangle$ の枝からは $\varphi_1$ 付近の値が出て、各枝の重み $\frac12$ で選ばれます（部分測定——ステップ1第5章）。2つの周波数が混ざって平均が出るのではなく、どちらか一方がクリーンに出るのがポイント。だから「固有状態を作れなくても、重ね合わせを入れてガチャを回せばよい」設計が成り立ちます（第6章で実戦投入）。
位相推定は「万能サブルーチン」と呼ばれるが、入力として何が必要かを整理せよ：(a) $U$ について何ができる必要があるか、(b) 固有状態レジスタに何を入れる必要があるか、(c) この2つの要件が「どんな問題でも位相推定に投げれば速くなる」を妨げる理由。
解答を見る
(a) 制御$U^{2^j}$ を効率よく（多項式ゲートで）実装できること。任意のユニタリの $2^j$ 乗は一般に指数コストですが、モジュラー累乗（第6章）のように「$U^{2^j}$ への近道」がある場合に限り効率化できます。(b) 固有状態そのもの、または有用な固有状態に十分な重みを持つ重ね合わせを効率よく用意できること。(c) この2条件を満たす $U$ を見つけること自体が難しく、そこにこそ問題の構造（周期性など）が要る——位相推定は「構造を固有値に翻訳できた問題」だけを高速化する装置であって、万能の加速器ではありません。Shorが偉大なのは、素因数分解をこの2条件を満たす形に翻訳しきった点にあります（次章）。