量子傅立葉變換

量子傅立葉變換（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)

L
L
Category:量子演算法