量子傅立葉轉換（QFT）

你可以把量子傅立葉轉換看作在問一個問題：'這個模式裡藏著哪些節奏？'經典傅立葉轉換接收一個訊號，告訴你它由哪些頻率構成。QFT 做的是同樣的事，只不過它作用在描述量子態的振幅上，而不是作用在記憶體裡的一串數字上。如果一個量子態裡藏著某種重複結構，比如一個每隔 r 步就重複一次的週期，QFT 會重新排布這些振幅，讓週期資訊匯聚到測量更有可能揭示它的地方。

下面是誠實且重要的部分。QFT 的'快'是在一個特定且狹窄的意義上：它所需的量子閘數量，遠少於經典快速傅立葉轉換（FFT）所需的算術運算次數——大致是量子位元數的平方，相比之下經典 FFT 對一串 2^n 個數字要做約 n 乘以 log n 次運算。但這並不意味著你能把整個轉換讀出來。測量這個態仍然只會給你一個結果，而且這個結果是依照玻恩定則從轉換後的振幅中抽取出來的。QFT 之所以強大，唯一的原因是：在合適的演算法內部，它讓振幅彼此干涉，從而使有用的結構（比如一個隱藏的週期）成為你最可能看到的結果。如果它孤立存在、外面沒有巧妙的演算法包裹，它並不會給你一張更快算出來的頻率清單。

這正是為什麼 QFT 的意義主要在於作為一個子程式，而不是一個獨立工具。它是量子相位估計內部的引擎，也是 Shor 演算法中提取週期的那一步——而這個週期正是用來分解大整數的關鍵，也正是 Shor 演算法對 RSA 與 ECC 構成威脅的原因。一旦離開了這類帶有隱藏週期結構或代數結構的問題，QFT 相比經典計算並不會帶來任何普遍的加速。