tecktom.com

量子 Fourier 変換：周波数を基底に移すユニタリ

2026年10月15日10分で読めますAI生成教科書『虎の巻』第6部 第2章 量子 Fourier 変換と位相推定
目次
  1. 定義
  2. 積の形
  3. 巡回シフトを対角にする
  4. 木下の層

AI 生成・木下が未勉強

相対エントロピーから情報と物理を組み立てる　第6部 第2章 §6.2.1　★★★ QFT の定義と、出力が量子ビットごとの積に分かれること・巡回シフトを対角にすること

ユニタリ演算子 U^\hat U の固有値は絶対値が 11 なので、U^∣u⟩=e2πiφ∣u⟩\hat U| u \rangle =\mathrm{e}^{2\pi\mathrm{i}\varphi}| u \rangle と位相 φ∈[0,1)\varphi\in[0,1) だけで書くことができる。この位相を知りたい場面は量子計算の至る所にある。U^=e−iH^τ/ℏ\hat U=\mathrm{e}^{-\mathrm{i}\hat H\tau/\hbar} と取れば φ\varphi はエネルギー固有値そのもので、分子の基底エネルギーを求める量子化学の計算になる。U^\hat U を「yy を ayay に掛け替える」剰余の掛け算に取れば、φ\varphi の分母に aa の位数が現れ、それが次の章の Shor のアルゴリズムになる（第6部第3章）。ところが、位相は全体にかかる因子なので、∣u⟩| u \rangle だけをいくら測っても φ\varphi は見えない。

この章で組み立てる位相推定は、補助の量子ビットを tt 個用意し、U^\hat U を補助の量子ビットで制御して当てることで、見えない全体の位相を補助の量子ビットの相対的な位相に書き移す。書き移された状態は、整数 kk の上で e2πiφk\mathrm{e}^{2\pi\mathrm{i}\varphi k} と振動する波で、この波の周波数 φ\varphi を読むのが量子 Fourier 変換（QFT）である。したがって章の前半は QFT そのものを扱う。QFT は信号処理の離散 Fourier 変換と同じ行列だが、2n2^n 次元の行列を n(n+1)/2n(n+1)/2 個のゲートで実現でき、その理由は出力が量子ビットごとの積に分かれることにある。

後半では位相推定の成功確率を求め、φ\varphi が tt ビットで書き切れないときの「漏れ」を評価する。次に補助の量子ビット1個を使い回す Kitaev の方法を述べる。これは前の章で残した「GHZ 状態の位相はどの周期にいるかが曖昧になる」問題（第3部第8章）を、粗い桁から細かい桁へ段階的に決めることで解く方法でもある。最後に情報の側から見て、位相推定は U^\hat U を合わせて TT 回使って位相を 1/T1/T の精度で読む測定、すなわち Heisenberg 限界の測定であることを、量子 Fisher 情報と相互情報量で確かめる。

この章の記法を断っておく。量子ビットの Pauli 演算子は記法の正本どおり X,Y,ZX,Y,Z、恒等演算子は 1\mathbf 1 と書く。Hadamard ゲートは第3部・第6部第1章と同じく斜体の HH と書く（Hamiltonian は帽子つきの H^\hat H、Shannon エントロピーは引数つきの H(X)H(X) で分かれる）。nn 個の量子ビットの計算基底 ∣j1j2⋯jn⟩| j_1j_2\cdots j_n \rangle を2進数 j=j12n−1+j22n−2+⋯+jnj=j_12^{n-1}+j_22^{n-2}+\cdots+j_n と同一視して ∣j⟩| j \rangle とも書き、N=2nN=2^n とする。2進小数を 0.jljl+1⋯jm=jl/2+jl+1/4+⋯+jm/2m−l+10.j_lj_{l+1}\cdots j_m=j_l/2+j_{l+1}/4+\cdots+j_m/2^{m-l+1} と書く。対数は自然対数（nat）で、ビットに直すときは明示する。

定義

定義 6.2.1（量子 Fourier 変換）

N=2nN=2^n 次元の計算基底に対して

U^QFT∣j⟩=1N∑k=0N−1e2πijk/N∣k⟩(j=0,1,…,N−1)(6.2.1)\hat U_{\mathrm{QFT}}| j \rangle =\frac1{\sqrt N}\sum_{k=0}^{N-1}\mathrm{e}^{2\pi\mathrm{i} jk/N}| k \rangle \qquad(j=0,1,\dots,N-1)\tag{6.2.1}

で定まる線形演算子を量子 Fourier 変換と呼ぶ。行列で書けば (U^QFT)kj=ωjk/N(\hat U_{\mathrm{QFT}})_{kj}=\omega^{jk}/\sqrt N、ω=e2πi/N\omega=\mathrm{e}^{2\pi\mathrm{i}/N} である。

指数の符号は量子計算の慣例どおり ++ に取る（この本の流儀）。信号処理の離散 Fourier 変換 Xm=∑kxke−2πikm/NX_m=\sum_kx_k\mathrm{e}^{-2\pi\mathrm{i} km/N} とは符号が逆で、U^QFT\hat U_{\mathrm{QFT}} は逆離散 Fourier 変換に N\sqrt N を掛けたものに等しい（数値計算のライブラリなら ifft の出力の N\sqrt N 倍）。

U^QFT\hat U_{\mathrm{QFT}} がユニタリであることは、列どうしの内積を計算すれば分かる。jj 列と j′j' 列の内積は

1N∑k=0N−1e2πi(j′−j)k/N=δjj′\frac1N\sum_{k=0}^{N-1}\mathrm{e}^{2\pi\mathrm{i}(j'-j)k/N}=\delta_{jj'}

で、j≠j′j\neq j' のときは 11 の NN 乗根 e2πi(j′−j)/N≠1\mathrm{e}^{2\pi\mathrm{i}(j'-j)/N}\neq1 の等比数列の和なので 00 になる。この直交性は位相推定の全体で使う事実で、6.2.5 節では「周波数が 1/N1/N だけ違う2つの波の状態は直交し、1回で完全に見分けられる」という形で読み直す。n=1n=1 では U^QFT=12(111−1)=H\hat U_{\mathrm{QFT}}=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}=H で、QFT は Hadamard ゲートの nn 量子ビット版とみなすことができる。ただし n≥2n\ge2 では H⊗nH^{\otimes n} とは違う行列で、H⊗nH^{\otimes n} の成分が ±1\pm1 だけなのに対し、QFT は 11 の NN 乗根をすべて使う。

積の形

QFT の出力は、どの jj に対しても量子ビットごとの積に分かれる。これが QFT を少ないゲートで組める理由である。

命題 6.2.2（積の形 ★★★）

j=j1j2⋯jnj=j_1j_2\cdots j_n（2進）に対し

U^QFT∣j1⋯jn⟩=(∣0⟩+e2πi 0.jn∣1⟩)⊗(∣0⟩+e2πi 0.jn−1jn∣1⟩)⊗⋯⊗(∣0⟩+e2πi 0.j1j2⋯jn∣1⟩)2n/2.(6.2.2)\hat U_{\mathrm{QFT}}| j_1\cdots j_n \rangle =\frac{\bigl(| 0 \rangle +\mathrm{e}^{2\pi\mathrm{i}\,0.j_n}| 1 \rangle \bigr)\otimes\bigl(| 0 \rangle +\mathrm{e}^{2\pi\mathrm{i}\,0.j_{n-1}j_n}| 1 \rangle \bigr)\otimes\cdots\otimes\bigl(| 0 \rangle +\mathrm{e}^{2\pi\mathrm{i}\,0.j_1j_2\cdots j_n}| 1 \rangle \bigr)}{2^{n/2}}.\tag{6.2.2}

上から ll 番目の量子ビットの位相は 2π×0.jn−l+1⋯jn2\pi\times0.j_{n-l+1}\cdots j_n である。

証明

出力の添字を k=∑l=1nkl2n−lk=\sum_{l=1}^nk_l2^{n-l} と2進で書くと、e2πijk/N=∏l=1ne2πijkl/2l\mathrm{e}^{2\pi\mathrm{i} jk/N}=\prod_{l=1}^n\mathrm{e}^{2\pi\mathrm{i} jk_l/2^l} と積に分かれ、∑k=∑k1⋯∑kn\sum_k=\sum_{k_1}\cdots\sum_{k_n} なので

U^QFT∣j⟩=⨂l=1n12∑kl=01e2πijkl/2l∣kl⟩=⨂l=1n∣0⟩+e2πij/2l∣1⟩2.\hat U_{\mathrm{QFT}}| j \rangle =\bigotimes_{l=1}^n\frac{1}{\sqrt2}\sum_{k_l=0}^1\mathrm{e}^{2\pi\mathrm{i} jk_l/2^l}| k_l \rangle =\bigotimes_{l=1}^n\frac{| 0 \rangle +\mathrm{e}^{2\pi\mathrm{i} j/2^l}| 1 \rangle }{\sqrt2}.

e2πij/2l\mathrm{e}^{2\pi\mathrm{i} j/2^l} では j/2lj/2^l の整数部分が消え、小数部分 0.jn−l+1⋯jn0.j_{n-l+1}\cdots j_n だけが残る。

式 (6.2.2) で上の量子ビットほど jj の下の桁しか見ていないことに注意する。1番上の量子ビットの位相は 00 か π\pi（jnj_n だけで決まる）で、1番下の量子ビットは jj のすべての桁を細かい位相に書き込んでいる。この「細かい位相を読み出すと粗い桁から順に決まる」構造は、6.2.4 節の反復位相推定でそのまま使う。

巡回シフトを対角にする

Fourier 変換の役目は、平行移動を位相の掛け算に変えることである。計算基底の巡回シフト S^∣j⟩=∣j+1 mod N⟩\hat S| j \rangle =| j+1\bmod N \rangle を考えると、

S^ U^QFT∣k⟩=1N∑je2πijk/N∣j+1⟩=e−2πik/N U^QFT∣k⟩(6.2.3)\hat S\,\hat U_{\mathrm{QFT}}| k \rangle =\frac1{\sqrt N}\sum_j\mathrm{e}^{2\pi\mathrm{i} jk/N}| j+1 \rangle =\mathrm{e}^{-2\pi\mathrm{i} k/N}\,\hat U_{\mathrm{QFT}}| k \rangle\tag{6.2.3}

となり、QFT の列 U^QFT∣k⟩\hat U_{\mathrm{QFT}}| k \rangle は S^\hat S の固有ベクトルで、固有値は e−2πik/N\mathrm{e}^{-2\pi\mathrm{i} k/N} である。周期 rr の関数を足し合わせた状態は「rr だけずらしても変わらない」状態なので、その QFT は周波数 N/rN/r の倍数のところにだけ重みを持つ。次の章ではこの事実を位相推定の言葉で言い直し、周期を読み出す。

例題 6.2.1　2量子ビットの QFT ★★

オリジナルn=2n=2（N=4N=4）の QFT を考える。

  1. (1) U^QFT\hat U_{\mathrm{QFT}} の行列を書き、H⊗HH\otimes H と違うことを確かめよ。
  2. (2) U^QFT∣01⟩\hat U_{\mathrm{QFT}}| 01 \rangle を定義 (6.2.1) から計算し、積の形 (6.2.2) と一致することを確かめよ。
解答

(1) ω=e2πi/4=i\omega=\mathrm{e}^{2\pi\mathrm{i}/4}=\mathrm{i} なので、成分は ijk/2\mathrm{i}^{jk}/2 で

U^QFT=12(11111i−1−i1−11−11−i−1i),H⊗H=12(11111−11−111−1−11−1−11).\hat U_{\mathrm{QFT}}=\frac12\begin{pmatrix}1&1&1&1\\1&\mathrm{i}&-1&-\mathrm{i}\\1&-1&1&-1\\1&-\mathrm{i}&-1&\mathrm{i}\end{pmatrix},\qquad H\otimes H=\frac12\begin{pmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{pmatrix}.

QFT には虚数 ±i\pm\mathrm{i} の成分があり、2つは違う。各行の長さは 11 で、異なる行の内積は 00 になっている。

(2) ∣01⟩=∣j=1⟩| 01 \rangle =| j=1 \rangle なので、定義から U^QFT∣1⟩=12(∣0⟩+i∣1⟩−∣2⟩−i∣3⟩)\hat U_{\mathrm{QFT}}| 1 \rangle =\frac12(| 0 \rangle +\mathrm{i}| 1 \rangle -| 2 \rangle -\mathrm{i}| 3 \rangle )。積の形では j1=0j_1=0、j2=1j_2=1 で、上の量子ビットの位相は 2π×0.j2=2π×12=π2\pi\times0.j_2=2\pi\times\frac12=\pi、下の量子ビットの位相は 2π×0.j1j2=2π×14=π/22\pi\times0.j_1j_2=2\pi\times\frac14=\pi/2 なので

12(∣0⟩−∣1⟩)⊗(∣0⟩+i∣1⟩)=12(∣00⟩+i∣01⟩−∣10⟩−i∣11⟩).\frac12(| 0 \rangle -| 1 \rangle )\otimes(| 0 \rangle +\mathrm{i}| 1 \rangle )=\frac12\bigl(| 00 \rangle +\mathrm{i}| 01 \rangle -| 10 \rangle -\mathrm{i}| 11 \rangle \bigr).

∣00⟩,∣01⟩,∣10⟩,∣11⟩| 00 \rangle ,| 01 \rangle ,| 10 \rangle ,| 11 \rangle を ∣0⟩,∣1⟩,∣2⟩,∣3⟩| 0 \rangle ,| 1 \rangle ,| 2 \rangle ,| 3 \rangle と読めば定義の結果と一致する。出力はもつれておらず、2つの量子ビットの積になっている。

木下の勉強ステータス

木下はまだこの記事を勉強していません。

AI（Claude）が書いた教材を、木下が勉強しながら公開しています。式と数値は検算していますが、誤りが残っているかもしれません。誤りのご指摘・削除のご依頼をいただければ直します。 連絡先：support@tecktom.com

目次

この記事が含まれている連載

連載AI生成教科書『虎の巻』授業とは別に、分野をまたいで気になったことを AI（Claude）が教材にし、木下が勉強しながら公開しています。上の段は AI が書いた本文、下の段は木下が勉強したあとに書いた文です。1787本の記事・木下 智貴
← AI生成教科書『虎の巻』の記事一覧へ