量子傅里叶变换

量子傅里叶变换（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)