量子傅里叶变换

量子傅里叶变换quantum Fourier transform)是一种离散傅里叶变换,将原式分解成更为简单的多个幺正矩阵的积。利用这般的分解方式,离散傅里叶变换可以用作量子电路,其包含了多个哈达玛闸受控移相闸

量子傅里叶变换在量子算法中有多处应用,以其可提供相位估算步骤的理论基础,在一些算法中占核心地位,例如用在做质因数分解的秀尔算法(Shor's algorithm)、顺序发现(order finding)算法以及隐子群问题(hidden subgroup problem)。

细节

l2(Z/(N))是复数函数Z/N内积空间,伴有内积

 

注意到离散傅里叶变换是个幺正映射

 

其叙述如下:

 l2(Z/(N))的一项正交归一基底(orthonormal basis)

参考文献

  • Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information (Cambridge, UK, 2000)
  • K. R. Parthasarathy, Lectures on Quantum Computation and Quantum Error Correcting Codes (Indian Statistical Institute, Delhi Center, June 2001)
  • John Preskill, Lecture Notes for Physics 229: Quantum Information and Computation (CIT, September 1998)