这篇文章主要是为了实现量子傅里叶变换(Quantum Fourier Transform, QFT)的programming做准备，对QFT的算法以及它和在传统计算机上运行的FFT进行比较。

FFT-toc" style="margin-left:0px;">1 FFT

FFT-toc" style="margin-left:40px;">1.1 DFT与FFT

FFT%E5%8E%9F%E7%90%86-toc" style="margin-left:40px;">1.2 FFT原理

FFT%E7%AE%97%E6%B3%95%E5%AE%9E%E7%8E%B0-toc" style="margin-left:40px;">1.3 FFT算法实现

QFT-toc" style="margin-left:0px;">2 QFT

QFT%E5%8E%9F%E7%90%86-toc" style="margin-left:40px;">2.1 QFT原理

2.1.1 计算推倒

2.1.2 量子电路

QFT%E5%B9%BA%E6%AD%A3%E7%9F%A9%E9%98%B5%2F%E9%87%8F%E5%AD%90%E9%97%A8-toc" style="margin-left:80px;">2.1.3 QFT幺正矩阵/量子门

2.2 举例

QFT%E5%92%8CFFT%E5%AF%B9%E6%AF%94-toc" style="margin-left:40px;">2.3 QFT和FFT对比

3 代码部分

参考文献与推荐阅读

FFT">1 FFT

FFT快速傅里叶变换是一种快速计算离散傅里叶变换(DFT)以及其逆变换(IDFT)的方法。简单起见，这里我们只对其正变换进行讨论。

FFT">1.1 DFT与FFT

	DFT	FFT
定义式
时间复杂度

FFT%E5%8E%9F%E7%90%86">1.2 FFT原理

FFT能够大幅度对传统的DFT提速的原因在于，利用了傅里叶变换的对称性。

根据上面表格里的DFT定义式，用N+k代替k，我们不难得到:

这说明Xk是每N个loop后一重复的，即:

利用这种对称性，Cooley-turkey算法证明了，我们可以将DFT分为两部分，如下:

同理，上图中的拆分可以继续进行下去(代码体现为一个递归函数)，因此我们不难发现最终的算法复杂度降低为了。

FFT%E7%AE%97%E6%B3%95%E5%AE%9E%E7%8E%B0">1.3 FFT算法实现

QFT">2 QFT

QFT%E5%8E%9F%E7%90%86">2.1 QFT原理

Quantum Fourier transform是传统的离散傅里叶变换(DFT)的量子解决办法。

DFT的计算式为:

，其中x_0,...,x_{N-1}是一个由复数组成的向量。

量子计算做的就是首先计算量子态，然后再将它映射到去，其中yk就是DFT定义式的所求。

这样的映射也等同于:

2.1.1 计算推倒

（感谢sky-edge的更正，上图中的j_l j_{l+1}...j_m应该是0.j_l j_{l+1}...j_m。）

由此可以对之前的QFT映射做出以下变换:

其中推导过程中出现的表示的是n项相乘。而0.j1j2...jn的表示就是我们刚刚讨论的二进制:

2.1.2 量子电路

由这样的结果，我们可以将量子傅里叶变换表示为一个量子电路(Quantum Circuit):

其中H是Hadamard门，Rk表示的是幺正矩阵形式为的量子门。具体这些门的计算可以在参考文献3或4中详细阅读，最终得到的qubits state是，和2.1.1保持一致。

对于第一个qubit我们用了1个H门和n-1个Rk门(conditional rotations)，对于第二个qubit我们用了1个H门和n-2个Rk门(conditional rotations)...所以总共用的门的数量是n+(n-1)+(n-2)+...+1=n(n+1)/2个。上图中省略了一些SWAP运算(用来在计算后交换qubits的位置，应该第一行与最后一行交换，第二行与倒数第二行交换...全部换完后，和2.1.1中的最终算式的顺序保持一致)，最多有n/2个SWAP运算，每个SWAP可以用3个CNOT门实现。因此QFT所用的门的数量是O(n^2)。

对于FFT来说，门的数量是O(n·2^n)。