量子フーリエ変換

QFT を「振幅への DFT」として捉える

量子フーリエ変換（QFT: Quantum Fourier Transform）は、Shor の素因数分解や量子位相推定（QPE）の心臓部にあたる変換です。名前が示すとおり離散フーリエ変換（DFT）の量子版ですが、決定的に違うのは作用する対象が古典的な数値列ではなく、重ね合わせ状態の「振幅」だという点です。ここでは定義・回路・位相推定での役割・古典FFTとの本質的な違いを、正確に順を追って解きます。

n 量子ビットの状態空間は N = 2^n 次元です。計算基底を |0>, |1>, ..., |N-1> と書くと、QFT は基底状態 |j> を次のように写す線形（ユニタリ）変換として定義されます。

QFT |j> = (1/√N) Σ_{k=0}^{N-1} exp(2πi · jk / N) |k>

一般の状態 Σ_j x_j |j> に適用すると、出力の各振幅 y_k は入力振幅 x_j の DFT になります。

Σ_j x_j |j>   ──QFT──►   Σ_k y_k |k>
y_k = (1/√N) Σ_j x_j · exp(2πi · jk / N)

つまり変換行列そのものは古典DFTの行列（成分 exp(2πi·jk/N)/√N）と同一です。違いは、この行列を N 個の実データに掛けるのではなく、N 次元の量子状態ベクトル（=振幅の集合）に一括で掛ける点にあります。DFT行列は各行・各列が正規直交なユニタリ行列なので、そのまま量子ゲート（可逆・ノルム保存）として実装できます。

積表現：回路が導かれる鍵

QFT を回路にできる理由は、指数の肩を2進数で展開するとテンソル積（各量子ビットごとの積）に分解できることにあります。入力 j を2進表記 j = j_1 j_2 ... j_n（j_1 が最上位ビット）とすると、QFT の出力は次の積の形に書けます。

QFT |j> = (1/√N) ⨂_{l=1}^{n} ( |0> + exp(2πi · 0.j_l j_{l+1} ... j_n) |1> )

ここで 0.j_l ... j_n は2進小数（例: 0.j_1 j_2 = j_1/2 + j_2/4）です。この式が示すのは、出力の第 l 量子ビットは、入力の下位ビット j_l 以降だけで決まる位相回転を受けた (|0>+e^{iθ}|1>)/√2 の形になるということ。各量子ビットが独立した積になるおかげで、量子ビットごとに順番に処理する回路として構成できます。

回路：アダマールと制御位相回転だけ

必要なゲートは2種類だけです。アダマールゲート H と、位相回転ゲート R_k です。

H = (1/√2) [ 1   1 ]        R_k = [ 1        0          ]
            [ 1  -1 ]              [ 0   exp(2πi/2^k)  ]

H は1量子ビットを |0> → (|0>+|1>)/√2 にする、いわば「1ビット版のフーリエ変換」です。積表現の各因子の骨格を作ります。R_k は |1> 成分にだけ位相 exp(2πi/2^k) を付ける回転で、これを制御ゲートとして使い、下位ビットの情報を上位ビットの位相へ書き込みます。手続きは次のとおりです。

for l = 1 .. n:
    量子ビット l に H を適用
    for m = l+1 .. n:
        量子ビット m を制御、量子ビット l を標的として C-R_{m-l+1} を適用
最後に SWAP でビット順序を反転（|j_1...j_n> ↔ |j_n...j_1>）

H の後に続く一連の制御 R_k が、0.j_l j_{l+1} ... j_n という2進小数位相を1ビットずつ積み上げます。積表現の各因子は「下位側のビットほど細かい位相（1/2^k）を寄与する」構造なので、制御位相回転の連鎖でちょうど再現できるのです。

ゲート数を数えると、量子ビット l に対して H が1個と制御回転が n - l 個、合計は n + (n-1) + ... + 1 = n(n+1)/2 個です。SWAP を加えても O(n^2)。n = log2(N) なので、状態次元 N に対しては O(log²N) という極めて浅い回路で済みます。

量子位相推定における役割

QFT の実用上の主役は、単独の変換としてよりも、その**逆変換 QFT†（逆QFT）**が量子位相推定（QPE）で果たす役割にあります。QPE は、ユニタリ U の固有状態 |u>（U|u> = e^{2πiφ}|u>）に対し、未知の位相 φ を推定する手続きです。流れはこうです。

1. n 量子ビットの制御レジスタを H で一様重ね合わせにする。
2. 制御 U^{2^0}, U^{2^1}, ..., U^{2^{n-1}} を順に適用する（位相キックバック）。すると制御レジスタは次の状態になる。

(1/√N) Σ_{k=0}^{N-1} exp(2πi · φ · k) |k>

3. この状態は、φ を位相に埋め込んだ「QFT の出力そのもの」の形をしています。だから逆QFT を掛けると、位相 φ に対応する計算基底 |φ·N> に集まり、測定すれば φ の2進近似が読み出せます。

QFT† [ (1/√N) Σ_k exp(2πi·φk)|k> ]  ≈  |round(φ · 2^n)>

古典FFTとの関係と本質的な違い

ここが最大の誤解ポイントです。QFT のゲート数 O(n^2) = O(log²N) は、古典 FFT の O(N log N) と比べて指数的に少ない——ならばデータのフーリエ変換を量子で爆速化できるのでは、と考えたくなります。しかしそれは成り立ちません。

理由は2つあります。第一に、入力の準備コストです。N 個の振幅 x_j を持つ量子状態を用意すること自体が、一般には指数的な手間を要します。任意のデータをそのまま量子状態に載せる万能な近道はありません。第二に、より本質的な出力の読み出し問題です。QFT を掛けても、変換後の N 個の振幅 y_k を直接は取り出せません。

したがって QFT は汎用の高速フーリエ変換の置き換えにはならない、というのが正確な理解です。QFT が量子優位をもたらすのは、Shor や QPE のように「フーリエ変換後の分布が特定の値（周期や位相）に鋭いピークを作り、その1点を測定するだけで答えが分かる」という構造を持つ問題に限られます。古典FFTが「全係数を得る道具」なら、QFTは「全係数への操作を安価に行い、目的の1点だけを測定で拾い上げる道具」だと捉えると、両者の住み分けが明確になります。

まとめ

量子フーリエ変換の要点は次の4つに集約できます。第一に、QFT は基底 |j> を (1/√N)Σ_k exp(2πi·jk/N)|k> へ写す、DFT行列と同一のユニタリ変換であり、作用するのは重ね合わせの振幅であること。第二に、指数を2進展開して得られる積表現により、アダマールと制御位相回転だけで O(n^2) ゲートの浅い回路に落とせること。第三に、その逆変換が量子位相推定の復調段を担い、Shor のアルゴリズムの土台になること。第四に、ゲート数は古典FFTより指数的に少ないが、入力生成と測定の制約ゆえに汎用FFTの代替にはならず、周期・位相抽出という特定構造でのみ真価を発揮すること。計算量の直感を固めたい場合は、プログラミング のアルゴリズム基礎も合わせて押さえておくと、O(n^2) と O(N log N) の差が指数と多項式の違いとして腑に落ちます。