第7章 量子傅立葉轉換#

章前言#

古典傅立葉轉換把訊號從時間域搬到頻率域，是工程與科學的萬用工具。量子傅立葉轉換（Quantum Fourier Transform, QFT）把同樣的變換搬進量子世界，而且效率驚人：古典 FFT 需要 \(O(N \log N) = O(n 2^n)\) 次運算，QFT 電路只要 \(O(n^2)\) 個閘——這是指數級的加速。

但要注意：QFT 的輸入是量子態而非古典資料，輸出也是量子態，不能直接「讀出」所有頻譜值。QFT 真正的威力在於作為其他演算法的子程序：Shor 演算法的週期尋找（第 8 章）、相位估計（本章 7.3 節）、以及量子化學中的能量本徵值估計，全都建立在它之上。

7.1 節對照古典 DFT 與量子 QFT 的定義；7.2 節推導 QFT 的電路結構（Hadamard＋受控相位閘＋位元反轉）並實作模擬；7.3 節介紹週期偵測與相位估計——這兩者是通往 Shor 演算法的最後一塊拼圖。

學習目標

1. 寫出 QFT 的變換公式並與 DFT 對照。
2. 實作 \(O(n^2)\) 的 QFT 電路模擬。
3. 用 QFT 做相位估計，理解它如何反推出本徵值的相位。