经典的傅立叶变换，无论对工程应用还是数据科学，都产生了深远。因此对于量子计算机来说，如何实施傅立叶变换也是很重要的事情1。 离散傅立叶变换，是将一组振幅 \(\{x_j\}\) ，通过如下的变换，转换成另一组共轭的振幅 \(\{\tilde{x}_k\}\) , \[ \tilde{x}_k = \frac{1}{\sqrt{N}}\sum_{j=1}^{N}e^{i\frac{2j\pi}{N}k}x_j \tag{1}\] 对于量子计算机而言，这些都是编码的概率幅，因此，我们只要对computational basis做傅立叶变换，例如： \[|\tilde{k}\rangle = \frac{1}{\sqrt{N}}\sum_{j=1}^{N}e^{i\frac{2\pi j}{N}k}|j\rangle \tag{2}\] 比较容易观察到，这组变换是unitary的。既然如此，我们就希望找到一种物理实现。 在谈具体实现之前，我们可以直觉上思考一些事情。1）对于一个n-qbit的量子计算机， $N=2^n ， j=j_{n-1}j_{n-2}j_0 $，后者我们用了二进制串。2）同时我们需要意识到，以 \(2\pi\) 为单位，每次转动的角度是 \(\frac{1}{2^n}\) ，对于所有的 \(j\) ，正好覆盖了所有\(n\)比特长度的小数， \(\sum_{k=0}^{n-1}j_k2^{k-n}\) ，如果我们读取了量子态的相位，那么可以很好的知道 \(k\) ，这为后面的很多算法做了奠基工作。 基于上面的我们可以给出Eq.(2)的等价描述， \[ |j_{n-1}j_{n-2}\cdots j_0\rangle \rightarrow \frac{1}{\sqrt{2^n}}\bigotimes_{l=0}^{n-1}(|0\rangle_l + e^{2\pi i 0.j_{n-l-1}\cdots j_0}|1\rangle_l)\] 从这个表达式，我们可以看出来，变换之后的态仍然是可分的，那么我们只需要关注如何把一个Qbit从 \(|j_{n-l-1}\rangle 变成 |0\rangle+e^{2\pi i 0.j_{n-l-1}\cdots j_0}|1\rangle\)。首先相位 \(e^{2\pi i 0.j_{n-l-1}}\) 通过一个Hadamard，直接可以得到。从第二位开始，相位的值依赖于其他的Qbit，因此需要借助控制门才能完成。例如我们需要把 \(|0\rangle \rightarrow \frac{|0\rangle + e^{2\pi i 0.0b}|1\rangle}{\sqrt{2}}\)（注意这边的小数仍然一个二进制串），那么我可以加一个基于b的值的控制门，来完成：如果 \(b=0\) ，不执行操作；如果 \(b=1\) ，执行一个门 \(\left(\begin{array}{cc}1 & 0 \\ 0 & e^{2\pi i 2^{-2}} \end{array}\right)\) . 因此对于 \(l\) 位的比特来说，我们也可以加基于所有他之后所有比特的控制门 \(\left(\begin{array}{cc} 1 & 0 \\ 0 & e^{2\pi i 2^{-d}} \end{array}\right)\)，这里的 \(d\) 代表距离 \(l\) 的位数。
复杂度： \(O(n^2)\) 我们需要做 \(\frac{n(n+1)}{2}\) 次门操作。 备注：概率幅并不如经典的振幅那样容易获得，因此直接应用QFT，不是那么容易，尽管我们展示了指数加速的能力。
Quantum Computation and Quantum Information, Michael A.Nielsen, Issac L. Chuang↩