量子傅里叶变换（QFT）

你可以把量子傅里叶变换看作在问一个问题：'这个模式里藏着哪些节奏？'经典傅里叶变换接收一个信号，告诉你它由哪些频率构成。QFT 做的是同样的事，只不过它作用在描述量子态的振幅上，而不是作用在内存里的一串数字上。如果一个量子态里藏着某种重复结构，比如一个每隔 r 步就重复一次的周期，QFT 会重新排布这些振幅，让周期信息汇聚到测量更有可能揭示它的地方。

下面是诚实且重要的部分。QFT 的'快'是在一个特定且狭窄的意义上：它所需的量子门数量，远少于经典快速傅里叶变换（FFT）所需的算术运算次数——大致是量子比特数的平方，相比之下经典 FFT 对一串 2^n 个数字要做约 n 乘以 log n 次运算。但这并不意味着你能把整个变换读出来。测量这个态仍然只会给你一个结果，并且这个结果是按照玻恩定则从变换后的振幅中抽取出来的。QFT 之所以强大，唯一的原因是：在合适的算法内部，它让振幅彼此干涉，从而使有用的结构（比如一个隐藏的周期）成为你最可能看到的结果。如果它孤立存在、外面没有巧妙的算法包裹，它并不会给你一张更快算出来的频率清单。

这正是为什么 QFT 的意义主要在于作为一个子程序，而不是一个独立工具。它是量子相位估计内部的引擎，也是 Shor 算法中提取周期的那一步——而这个周期正是用来分解大整数的关键，也正是 Shor 算法对 RSA 和 ECC 构成威胁的原因。一旦离开了这类带有隐藏周期结构或代数结构的问题，QFT 相比经典计算并不会带来任何普遍的加速。