量子傅立葉變換

维基百科,自由的百科全书
跳转至: 导航搜索


量子傅立葉變換(quantum Fourier transform)是一種離散傅立葉變換,將原式分解成更為簡單的多個么正矩陣的積。利用這般的分解方式,離散傅立葉變換可以用作量子電路,其包含了多個哈達瑪閘受控移相閘

量子傅立葉變換在量子演算法中有多處應用,以其可提供相位估算步驟的理論基礎,在一些演算法中佔核心地位,例如用在做質因數分解的秀爾演算法(Shor's algorithm)、順序發現(order finding)演算法以及隱子群問題(hidden subgroup problem)。

細節[编辑]

l2(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\ranglel2(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)