量子傅立葉變換 (QFT)
3. 量子傅立葉轉換 (QFT): 量子加速的核心
3.1 數學定義與古典關聯
量子傅立葉轉換（Quantum Fourier Transform, QFT）是古典離散傅立葉轉換（Discrete Fourier Transform, DFT）在量子計算中的直接對應 [25, 26, 27]。古典DFT將一個 $N$ 維的複數向量 $\{x_0, x_1, \dots, x_{N-1}\}$ 轉換為另一個 $N$ 維向量 $\{y_0, y_1, \dots, y_{N-1}\}$，其定義為：
$$y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j e^{2\pi i jk/N}$$
QFT則是在量子態上執行同樣的變換。它將一個表示為計算基態疊加的量子態 $|\psi\rangle = \sum_{j=0}^{N-1} x_j |j\rangle$ 轉換為另一個量子態 $|\tilde{\psi}\rangle = \sum_{k=0}^{N-1} y_k |k\rangle$。因此，QFT對任意計算基態 $|j\rangle$ 的作用可以寫為：
$$QFT|j\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i jk/N} |k\rangle$$
其中 $N = 2^n$， $n$ 是系統的量子位元數。QFT的真正威力在於其高效的實現方式。古典上最快的傅立葉轉換演算法（FFT）需要 $O(N \log N)$ 的計算時間，而QFT在量子電腦上僅需 $O(n^2)$，即 $O((\log N)^2)$ 的時間，實現了指數級的加速 [26, 28]。
理解QFT電路實現的關鍵在於其產品表示法。QFT作用在一個 $n$-qubit計算基態 $|j\rangle = |j_1 j_2 \dots j_n\rangle$ 上的結果，可以被優雅地分解為 $n$ 個單獨量子位元的張量積形式 [26, 27]：
$$QFT|j_1 j_2 \dots j_n\rangle = \frac{1}{\sqrt{2^n}} \left(|0\rangle + e^{2\pi i [0.j_n]}|1\rangle\right) \otimes \left(|0\rangle + e^{2\pi i [0.j_{n-1}j_n]}|1\rangle\right) \otimes \dots \otimes \left(|0\rangle + e^{2\pi i [0.j_1j_2\dots j_n]}|1\rangle\right)$$
這裡，$[0.j_l \dots j_n]$ 代表二進制小數，例如 $[0.j_1j_2] = j_1/2 + j_2/4$。這個表達式揭示了輸出態的第 $k$ 個量子位元的相位，是如何依賴於輸入態的第 $k$ 到第 $n$ 個位元的。
3.2 電路實現
基於上述的產品表示法，QFT可以通過一個僅由Hadamard閘和受控相位旋轉閘構成的量子電路來高效實現 [26, 27, 29]。一個 $n$-qubit QFT電路的構建步驟如下：
- 對第一個量子位元（$q_1$，對應 $|j_1\rangle$）施加一個Hadamard閘。
- 接著，由第二個量子位元（$q_2$）控制，對 $q_1$ 施加一個相位旋轉 $R_2$ 閘（旋轉角度為 $\pi/2$）。然後由第三個量子位元（$q_3$）控制，對 $q_1$ 施加一個 $R_3$ 閘（旋轉角度為 $\pi/4$），以此類推，直到由第 $n$ 個量子位元控制施加 $R_n$ 閘。
- 對第二個量子位元（$q_2$）施加一個Hadamard閘，然後依次由 $q_3, q_4, \dots, q_n$ 控制，對其施加 $R_2, R_3, \dots, R_{n-1}$ 閘。
- 重複此過程，直到對最後一個量子位元（$q_n$）施加Hadamard閘。
- 由於上述過程產生的量子位元順序是顛倒的，最後通常需要一系列的SWAP閘來將量子位元的順序反轉（$q_1 \leftrightarrow q_n$, $q_2 \leftrightarrow q_{n-1}$, etc.）[26, 29]。
整個電路總共需要 $n$ 個Hadamard閘和 $n(n-1)/2$ 個受控相位旋轉閘，因此總的閘數目是 $O(n^2)$ [26, 30]。這種高效的可實現性，使得QFT成為眾多關鍵量子演算法中不可或缺的核心子程序 [25, 31, 32]。
值得注意的是，QFT的指數級加速並非沒有代價。與古典FFT能讓我們讀出所有傅立葉係數不同，對QFT的輸出態進行測量，只會讓我們以一定的機率得到其中一個頻率分量。QFT的真正威力體現在它作為一個中間步驟，能夠將週期性等資訊高效地編碼到量子態的相位中，再通過後續的量子操作（如干涉）或測量，以高機率提取出我們感興趣的特定資訊。這揭示了量子演算法設計的一個核心理念：計算過程是為了巧妙地操控機率振幅，使得最終測量時，答案能以極高的機率「現身」。
2.1 量子傅立葉變換 (Quantum Fourier Transform, QFT)
量子傅立葉變換是離散傅立葉變換在量子計算上的類比，它將傳統演算法中的傅立葉變換通過量子電路實現:contentReference[oaicite:26]{index=26}。QFT作用在量子位元的振幅上，可以將量子態從計算基底轉換到傅立葉基底，是許多複雜量子演算法的核心步驟:contentReference[oaicite:27]{index=27}。例如，Shor演算法中的周期發現、量子相位估計演算法中的相位讀取，都仰賴於QFT高效地提取振幅中的週期性資訊:contentReference[oaicite:28]{index=28}。QFT電路通常由一系列Hadamard閘和受控旋轉閘組成，其電路深度隨著輸入位元數n呈O(n2)增長:contentReference[oaicite:29]{index=29}。相比之下，傳統快速傅立葉變換(FFT)對應於O(N log N)的複雜度（N=2^n為資料長度），因此QFT在指數級壓縮了轉換所需步驟:contentReference[oaicite:30]{index=30}。然而，QFT的結果以量子態疊加方式存儲，需經由測量取得，這意味著除非在更大的演算法結構中使用，單獨的QFT無法直接讀出完整的變換結果。
儘管如此，QFT的出現使多項突破性量子演算法成為可能。它的電路設計包含許多相位旋轉門，能夠在量子態中同時對所有基向量附加不同相位。這種全局且平行的相位操作在古典計算中難以有效模擬。QFT的應用場景除了因數分解與相位估計，還包括隱秩序尋找、隱子群問題以及解線性方程的HHL演算法等。在這些應用中，QFT扮演將問題轉換到頻域或對偶域來簡化處理的角色，是量子計算相對於經典計算實現指數級加速的關鍵環節之一。
王培儒