出处已验证第 3 级
量子傅里叶变换
量子傅里叶变换（QFT）是离散傅里叶变换的量子类似物，用O(n²)个门将计算基态变换为相位编码的频率态。
这是什么意思
QFT将计算基态映射为编码频率分量相位的叠加。比经典FFT的O(n·2^n)只需O(n²)个门。是Shor算法和量子相位估计的关键子程序。生活类比
像将和弦转换为单独音符。
像棱镜将白光分成彩虹。
常见误解
- QFT加速不直接转化为信号处理加速。
- QFT电路与经典FFT不同。
要点总结
- O(n²)个门转换。
- 比经典FFT指数级少。
- Shor和相位估计的关键子程序。
检验你的理解
n量子比特QFT需要多少门？
- A.O(n)
- B.O(n²)
- C.O(2^n)
- D.O(n·2^n)
查看答案
答案: B. O(n²)
原因: O(n²)个门。
先修概念
一次文献: Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26, 1484 (1997), doi:10.1137/S0097539795293172
Circuit form per Coppersmith (1994), arXiv:quant-ph/0201067.