第4章量子フーリエ変換 — 周期を見る眼鏡
この章の目標
- QFTの定義を理解し、$N = 2$（$= H$）と $N = 4$ を手計算できるようになる
- 「周期 $r$ の重ね合わせ → QFT → $N/r$ の倍数にピーク」を $N = 8$ で確かめる
- QFT回路が $O(n^2)$ ゲートで組めることを知る（万能の高速化でない理由も含めて）
4.1 定義 — 離散フーリエ変換の量子版
信号処理のDFT/FFTと数学的中身は同じです。違いはデータの置き場所：数列を配列に持つ代わりに、振幅として持ちます。
$N = 2^n$ 次元の基底状態 $|j\rangle$（$j = 0, \dots, N-1$ を整数として読む）に対し $$\mathrm{QFT}\,|j\rangle = \frac{1}{\sqrt N}\sum_{k=0}^{N-1} e^{2\pi i \frac{jk}{N}}\,|k\rangle$$ 一般の状態には線形に拡張する（振幅の列 $\{a_j\}$ がそのままDFTされる）。
$\omega = e^{2\pi i/N}$（1の原始 $N$ 乗根）と書けば、行列は $\mathrm{QFT}_{kj} = \frac{1}{\sqrt N}\omega^{jk}$。最小の例で感触を掴みます：
$N = 2$: $\omega = e^{i\pi} = -1$ なので $\mathrm{QFT}_2 = \frac{1}{\sqrt2}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} = H$。 アダマールはQFTの最小ケース——第2章までの「$H$ で畳む」は、実は「QFTで畳む」の特別な場合だったわけです。
$N = 4$: $\omega = i$ なので $$\mathrm{QFT}_4 = \frac{1}{2}\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{pmatrix}$$ 第 $j$ 列は「速度 $j$ で複素平面を回る回転子」を並べたもの。行き先の $|k\rangle$ の振幅は「入力と速度 $k$ の回転子の相関」です。
4.2 何の役に立つか — 周期のピーク検出
QFTの使いどころはただ一つと言ってよい：振幅に隠れた周期を、測定できるピークに変換することです。周期 $r$ ごとに等間隔で立っている重ね合わせ（オフセット $b$、$m = N/r$ 本） $$|\psi\rangle = \frac{1}{\sqrt m}\sum_{t=0}^{m-1} |b + tr\rangle$$ にQFTを掛けると、素直な計算（演習4-3と同じ型の等比和）により：
$r$ が $N$ を割り切るとき、QFT後の状態は $$\frac{1}{\sqrt r}\sum_{s=0}^{r-1} e^{2\pi i \frac{bs \cdot m}{N} \cdot \text{(位相)}}\,\Big|s \cdot \frac{N}{r}\Big\rangle$$ の形になる。すなわち測定結果は必ず $\frac{N}{r}$ の倍数（$r$ 通りに等確率）。オフセット $b$ は位相（＝測定に出ない）にしか現れない。
測定で $s \cdot \frac{N}{r}$ 型の値がサンプルできれば、数回のサンプルから $r$ が復元できます（分数 $\frac{k}{N} = \frac{s}{r}$ を約分する——第6章）。ポイントを2つ：
- オフセット不変性：どこから周期が始まっていても（$b$ が何でも）ピーク位置は同じ。これが第5・6章で「途中の測定結果がランダムでも困らない」効果を生みます。
- $r$ が $N$ を割り切らない場合はピークが完全な1点でなく近傍ににじみますが、最も近い整数への集中は保たれ、確率的に復元可能です（実験4で観察できます）。
4.3 回路 — $O(n^2)$ ゲートで組める
QFTの行列は $2^n \times 2^n$ の巨大なユニタリですが、$H$ と制御位相回転 $CR_k$（$R_k = \mathrm{diag}(1, e^{2\pi i/2^k})$）を $\frac{n(n+1)}{2}$ 個並べるだけで厳密に実装できます（＋最後にワイヤ順のSWAP）。$n = 2$ の例：
q0: ──[H]──●─────────╳──
│ │
q1: ───────[R₂]──[H]──╳── R₂ = diag(1, i) = S（制御付き）古典FFTが $O(N \log N) = O(2^n \cdot n)$ かかるところ、QFTは $O(n^2)$——指数的に少ないゲート数です。ステップ2問2-8の言葉で言えば「役に立つ巨大ユニタリのうち、多項式個の基本ゲートに分解できるもの」の代表例。導出の骨子は、QFTの出力が各量子ビットの積状態 $$\mathrm{QFT}|j\rangle = \bigotimes_{l} \frac{|0\rangle + e^{2\pi i\, j/2^l}|1\rangle}{\sqrt2}$$ に分解できる（積表現）ことにあります。興味があれば演習4-5で $n = 2$ を検算してください。
QFT自体は指数的に速い。しかし入力（信号データ）を振幅に載せる工程と、出力（スペクトル全体）を読み出す工程が含まれていません。$2^n$ 点の古典データを振幅にロードするには一般に $O(2^n)$ の手間がかかり、出力側も測定1回につき1サンプルしか得られない（振幅は読めない——ステップ1以来の鉄則）。QFTが本領を発揮するのは、入力が量子計算の内部で自然に生成され（第5・6章の周期状態）、出力もピーク位置1点だけ知れば良い場合に限られます。「サブルーチンが速い」と「アプリが速い」の峻別——ニュース読解の重要視点その2です。
演習4
$\mathrm{QFT}_4$ の行列を使って $\mathrm{QFT}_4|2\rangle$ を計算せよ（$|2\rangle$ は第3列…ではなく第2列。0始まりに注意）。結果の位相パターンを $e^{2\pi i \cdot 2k/4} = (-1)^k$ として確認せよ。
解答を見る
$\mathrm{QFT}_4|2\rangle = \frac12(|0\rangle - |1\rangle + |2\rangle - |3\rangle)$（第2列＝速度2の回転子は $1, -1, 1, -1$）。$j = 2$ は「$N = 4$ の中で最速の交番」であり、出力は符号が交互の一様重ね合わせ。入力の整数値 $j$ ＝出力の位相の回転速度という対応を、この小さな例で体に入れてください。
$N = 4$、周期 $r = 2$ の状態 $\frac{|0\rangle + |2\rangle}{\sqrt2}$ にQFTを掛けよ。ピークが $N/r = 2$ の倍数（$k = 0, 2$）に立つことを確認せよ。次にオフセット付き $\frac{|1\rangle + |3\rangle}{\sqrt2}$ でも計算し、ピーク位置が変わらないことを確かめよ。
解答を見る
線形性で列を足す：$\frac{1}{\sqrt2}\big(\mathrm{QFT}|0\rangle + \mathrm{QFT}|2\rangle\big) = \frac{1}{2\sqrt2}\big[(1{+}1)|0\rangle + (1{-}1)|1\rangle + (1{+}1)|2\rangle + (1{-}1)|3\rangle\big] = \frac{|0\rangle + |2\rangle}{\sqrt2}$。ピークは $k = 0, 2$ ✓（この状態はたまたまQFTの固有ベクトル）。オフセット版：$\frac{1}{2\sqrt2}\big[(1{+}1)|0\rangle + (i{-}i)|1\rangle + (-1{-}1)|2\rangle + (-i{+}i)|3\rangle\big] = \frac{|0\rangle - |2\rangle}{\sqrt2}$。$|2\rangle$ の符号（位相）は変わったが、測定確率は $k = 0, 2$ に各 $\frac12$ で同一。オフセットは位相にだけ現れる——事実ボックスの主張そのものです。
$N = 8$、$r = 4$、$b = 0$ の状態 $\frac{|0\rangle + |4\rangle}{\sqrt2}$ にQFTを掛け、測定確率分布を求めよ。ピークが $8/4 = 2$ の倍数（0, 2, 4, 6）に立つことを確認せよ。ヒント: $e^{2\pi i \cdot 4k/8} = (-1)^k$。
解答を見る
振幅：$c_k = \frac{1}{\sqrt{16}}(1 + (-1)^k)$。$k$ 偶数で $c_k = \frac{2}{4} = \frac12$、奇数で0。分布は $k = 0, 2, 4, 6$ に各 $\frac14$ ✓。$m = N/r = 2$ 本しか立っていない入力でも、干渉はきちんと「奇数 $k$ を全滅」させます。$r = 2$（$|0\rangle + |2\rangle + |4\rangle + |6\rangle$ を $\frac12$ 倍）なら $k = 0, 4$ に各 $\frac12$ になることも、同じ計算でぜひ確かめてください。
QFTがユニタリであることを、列の正規直交性（ステップ2第3章の判定法）で示せ。すなわち第 $j$ 列と第 $j'$ 列の内積が $\delta_{jj'}$ になることを、等比数列の和で確かめよ。
解答を見る
内積 $= \frac{1}{N}\sum_k e^{-2\pi i jk/N} e^{2\pi i j'k/N} = \frac{1}{N}\sum_k \omega^{(j'-j)k}$。$j = j'$ なら各項1で和は $N$、割って1。$j \ne j'$ なら公比 $\omega^{j'-j} \ne 1$ の等比数列で、和は $\frac{\omega^{(j'-j)N} - 1}{\omega^{j'-j} - 1} = 0$（分子は $e^{2\pi i (j'-j)} - 1 = 0$）。よって直交 ✓。第2章の消滅補題（$\pm1$ の総和が消える）の連続位相版です。量子アルゴリズムの計算は結局「等比数列の和が消えるか残るか」に帰着する——この感覚まで来れば、ステップ3の数学は卒業です。
4.3節の $n = 2$ QFT回路（$H$、制御$S$、$H$、SWAP）が $\mathrm{QFT}_4$ を実装していることを、入力 $|10\rangle$（$j = 2$）で検算せよ。問4-1の答え $\frac12(|0\rangle - |1\rangle + |2\rangle - |3\rangle)$ と一致するはず。ビット順（上位・下位）に注意。
解答を見る
$|q_0 q_1\rangle = |10\rangle$。$H$(q0)：$\frac{(|0\rangle - |1\rangle)|0\rangle}{\sqrt2}$。制御$S$（制御q1=0）：不発。$H$(q1)：$\frac{(|0\rangle - |1\rangle)(|0\rangle + |1\rangle)}{2} = \frac12(|00\rangle + |01\rangle - |10\rangle - |11\rangle)$。SWAPでビット順を入れ替え：$\frac12(|00\rangle + |10\rangle - |01\rangle - |11\rangle)$、整数で読むと $\frac12(|0\rangle - |1\rangle + |2\rangle - |3\rangle)$ ✓。ゲート3個＋SWAPで $4 \times 4$ ユニタリが正確に出る——積表現の威力です。
$n = 20$（$N \approx 10^6$）のQFTに必要なゲート数を見積もれ。古典FFTの演算数と比べよ。この比較だけを根拠に「量子コンピュータはFFTを使う全アプリケーション（音声処理、画像圧縮…）を指数加速する」と結論してよいか。「正直な評価」欄の2つの工程を踏まえて答えよ。
解答を見る
QFT: $\frac{n(n+1)}{2} = 210$ ゲート程度。古典FFT: $O(N \log n)$ ではなく $O(N \log N) \approx 10^6 \times 20 = 2 \times 10^7$ 演算。ゲート数では10万倍の差ですが、結論は否：(1) 音声データ $10^6$ 点を振幅にロードする汎用手段は $O(N)$ かかり、そこで利得が消える。(2) 出力スペクトル全体（$10^6$ 個の値）を知るには測定を $O(N)$ 回繰り返す必要があり、ここでも消える。QFTが勝てるのは「入力状態が量子回路の内部で $O(\mathrm{poly}(n))$ で作れて、出力もピーク位置だけで十分」という狭き門を通る問題だけ——それが周期発見（第5・6章）です。サブルーチンの速さをアプリの速さと混同しない。ニュースの「量子でAI/最適化が爆速」系の主張も、まずこのデータ入出力の壁を確認するのが定石です。