量子フーリエ変換(QFT)をQiskitでゼロからつくる｜位相に情報を書き込む

ショアのアルゴリズムや量子位相推定の心臓部が 量子フーリエ変換（QFT） です。古典FFTが O(n·2ⁿ) なのに対し、QFTは O(n²) のゲート数で済みます。この記事ではQiskitで、アダマールと制御位相ゲートからQFTを手で組み立てます。ライブラリに頼らず作ると、何をしているかが腹落ちします。

QFTがやること

QFTは、量子ビットの「基底の状態」を「位相の回転」に変換します。各ビットに異なる周波数の位相を書き込むイメージ。この位相の情報を後段のアルゴリズムが読み取ります。

準備

pip install qiskit qiskit-aer

① QFTを手で組む

各ビットにアダマール → 下位ビットからの制御位相回転 → 最後にビット順を反転（スワップ）します。

from qiskit import QuantumCircuit
from math import pi

def qft(n):
    qc = QuantumCircuit(n, name="QFT")
    for j in range(n):
        qc.h(j)
        for k in range(j + 1, n):
            qc.cp(pi / 2 ** (k - j), k, j)   # 制御位相回転
    # ビット順を反転
    for i in range(n // 2):
        qc.swap(i, n - 1 - i)
    return qc

print(qft(3).draw(output="text"))

cp(角度, 制御, 標的) が制御位相ゲート。ビットが離れるほど回転角を半分ずつ小さくするのがポイントです。

② 動作を確かめる

状態ベクトルシミュレータでQFTの効果を見ます。|000⟩ にQFTをかけると、全基底が均等な重ね合わせになります。

from qiskit_aer import AerSimulator
from qiskit import transpile

qc = QuantumCircuit(3)
qc.compose(qft(3), inplace=True)
qc.save_statevector()

sv = AerSimulator(method="statevector").run(transpile(qc, AerSimulator())).result().get_statevector()
import numpy as np
print(np.round(np.abs(sv.data), 3))   # すべて 0.354 ≈ 1/√8

すべての振幅が 1/√8 ≈ 0.354。|000⟩ が全基底へ均等に広がりました。QFTが「基底→位相」の変換をしている証拠です。

まとめ

• QFTは「基底の状態」を「位相の回転」に変換する。ゲート数はO(n²)
• アダマール＋制御位相回転（cp）＋スワップで手作りできる
• 実アルゴリズムでは逆QFTで位相の情報を読み出す
• ショアや位相推定の心臓部

もう少し詳しく（背景と理論）

量子フーリエ変換（QFT）は離散フーリエ変換の量子版で、n 量子ビットに対し O(n²) 個の基本ゲートで実装できます¹。古典の高速フーリエ変換（FFT）が O(N log N)＝O(2ⁿ·n) であるのに対し、QFTは指数的に少ないゲート数で「振幅の上」にフーリエ変換をかけます。ただし結果は測定でしか読めず、全係数を取り出せるわけではない点に注意が要ります²。実務では、位相に埋め込んだ情報を読み出す逆QFTとして使われ、量子位相推定やショアの周期発見の心臓部になります³。制御位相回転は微小角になるほどノイズに弱く、近似QFT（小さい回転を省く）で深さを削るのが実機での定石です⁴。

次の一歩 🌸

QFTを使う代表例は量子位相推定、アルゴリズム全体像は量子アルゴリズム入門、ゲートの基礎は量子ゲート入門へどうぞ。

Footnotes

1. n 量子ビットのQFTはアダマール n 個と制御位相回転 n(n−1)/2 個、スワップ n/2 個で構成され、ゲート数は O(n²)。 ↩

2. QFTはユニタリ変換であり、出力の全2ⁿ係数を直接読み出すことはできない。干渉によって「欲しい情報が測定確率に現れる」よう設計するのがアルゴリズム側の役割。 ↩

3. Shor のアルゴリズムでは、剰余べき乗のユニタリの固有位相を逆QFTで読み、連分数展開で周期を得る。QFTはショアの本質的な部品。 ↩

4. Coppersmith, D. (1994/2002). "An approximate Fourier transform useful in quantum factoring." 一定閾値以下の微小回転を省く近似QFTで、精度をほぼ保ちつつゲート数を O(n log n) に削減できる。 ↩