7.1 古典 DFT 與量子 QFT#

概念說明#

古典離散傅立葉轉換（DFT）：對 \(N\) 維向量 \(x\) ，

矩陣形式 \(X = F x\) ，其中 \(F_{kj} = \omega^{jk}/\sqrt N\) （ \(\omega = e^{2\pi i/N}\) ）。直接計算 \(O(N^2)\) ；FFT 用對稱性降到 \(O(N\log N)\) 。

量子傅立葉轉換（QFT）：同一個么正矩陣 \(F\) 作用在量子態上：

其中 \(\tilde\alpha_k = \frac{1}{\sqrt N}\sum_j \alpha_j e^{2\pi i jk/N}\) 。

重要澄清——加速的真實面貌：

• QFT 電路只要 \(O(n^2)\) 個閘（ \(n = \log_2 N\) ），古典 FFT 是 \(O(2^n \cdot n)\) ——看似指數加速；
• 但 QFT 的輸入/輸出都是量子態：你無法把古典資料灌進去、也無法讀出整條頻譜。測量只給一個樣本；
• 因此 QFT 不是 DFT 的取代品，而是量子態上的變換，價值在於作為週期尋找、相位估計的子程序——把疊加態裡隱藏的週期結構轉換成可測量的尖峰。

一個有用的直覺：QFT 把「計算基底上的等間隔結構」變成「頻域的尖峰」。若態是 \(\frac{1}{\sqrt r}\sum_{j}|j_0 + jr\rangle\) （週期 \(r\) 的梳狀），QFT 後機率集中在 \(k \approx N/r\) 的倍數附近。

Python 範例#

import numpy as np

def qft_matrix(n):
    """n 位元 QFT 的 2^n x 2^n 矩陣"""
    N = 2**n
    j, k = np.meshgrid(np.arange(N), np.arange(N))
    return np.exp(2j*np.pi*j*k/N)/np.sqrt(N)

# 與 numpy 的 FFT 對照
n = 3
v = np.array([1, 2, 0, 0, 0, 1, 0, 0], dtype=complex)
F = qft_matrix(n)
print("QFT 矩陣法:", np.round(F @ v, 3))
print("numpy FFT :", np.round(np.fft.fft(v)/np.sqrt(len(v)), 3))

# 週期訊號的頻譜尖峰
N = 16; r = 4                       # 週期 4，N/r = 4
state = np.zeros(N, dtype=complex)
for j0 in range(0, N, r): state[j0] = 1
state /= np.linalg.norm(state)
spectrum = np.abs(F @ state)**2
print("週期 4 訊號的頻譜:", np.round(spectrum, 2))
# 集中在 k = 0, 4, 8, 12 —— 正是 N/r 的倍數

複雜度分析#

\(N=2^{30}\) 時 FFT 約 \(3\times10^{10}\) 次運算，QFT 電路約 900 個閘——但只在「資訊已在量子態裡、且只需要測量樣本」時有意義。

練習#

1. 手算 \(n=2\) 的 QFT 矩陣，並驗證 \(F^2|0\rangle = |0\rangle\) 、 \(F^2|1\rangle = |3\rangle\) （即 \(F^4=I\) ）。
2. （程式）對 \(N=32\) 、週期 \(r=8\) 的梳狀態做 QFT，列出機率前 4 大的頻率，驗證它們都是 \(N/r\) 的倍數。
3. （觀念）為什麼不能說「QFT 比 FFT 快指數倍，所以可以取代訊號處理」？什麼條件下 QFT 的優勢才會兌現？