量子傅里叶变换

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

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

细节

l²(Z/(N))是复数值函数于Z/N 的内积空间，伴有内积

$\langle \psi |\phi \rangle =\sum _{k\in \mathbb {Z} /(N)}{\overline {\psi (k)}}\phi (k)$

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

$\ell ^{2}(\mathbb {Z} /(N))\rightarrow \ell ^{2}(\mathbb {Z} /(N)).$

其叙述如下：

令$|0\rangle ,\ldots ,|N-1\rangle$是l²(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)