本系列的内容将参考我正在上的课程UCI CS264 Quantum Computing，感谢我的老师Prof. Sandy Irani。此外，本篇文章还参考了André Chailloux的MPRI Quantum Computing Lecture 2；Umesh Vazirani的UCB CS294 Quantum Computing Lecture 7；张镇九和张昭理的量子信息讲座续讲 第一讲，感谢以上老师们的材料。
本节我将会尝试用知识卡片+讲解的形式来写文章，和上一节和小白蔡一起入门量子计算–量子傅立叶变换（一） 的风格不太一样，大家更喜欢哪种形式呢？欢迎大家给我留言反馈，谢谢～
上一节我们学习了离散傅立叶变换\(DFT\)，并且根据\(DFT\)的矩阵和输入向量的相乘知道它需要\(N\times N\)次的乘法运算，所以复杂度为\(O\left( { N }^{ 2 } \right)\)。然而，还有一种更快的复杂度为\(O\left( { N }\log { N } \right)\)傅立叶变换，就是我们今天要学习的快速傅立叶变换\(FFT\) (Fast Fourier Transform)。
快速傅立叶变换
首先，在学习快速傅立叶变换之前，我们要先假设一个大前提：\(N={ 2 }^{ n },\quad n\in { Z }^{ + }\)，即N是2的n次方，且n为任意正整数。为什么要有这个限制呢？因为快速傅立叶变换算法本质上是一个递归算法，即从\({ FFT }_{ 1 }\)开始，\({ FFT }_{ 2 }\)就是在两个\({ FFT }_{ 1 }\)上做运算，\({ FFT }_{ 4 }\)就是在两个\({ FFT }_{ 2 }\)上做运算，以此类推，每次递归都调用前两个\(FFT\)。如果你还不是很明白，看一看本文后面的内容和例题或许能帮助你的理解。
接下来，让我们用矩阵的方式来理解第n-1次递归运算即\({ FFT }_{ N }\)是如何从\(FFT_{ N/2 }\)得到的。
用矩阵表示快速傅立叶变换\(FFT_{ N }\)
在步骤(1)中，我们重新组织了矩阵里的列，把所有偶数的列（即第0,2,4…N-2列）放在矩阵的左边，所有奇数的列（即第1,3,5…N-1列）放在矩阵的右边。同样的，我们重新组织了输入向量，可以在步骤(3)中看到，偶数位的\({ \alpha }_{ 0 },{ \alpha }_{ 2 },{ \alpha }_{ 4 },…,{ \alpha }_{ N-2 }\)放在输入向量的前半部分，奇数位的\({ \alpha }_{ 1 },{ \alpha }_{ 3 },{ \alpha }_{ 5 },…,{ \alpha }_{ N-1 }\)放在输入向量的后半部分。
在步骤(1)中，我们可以把矩阵分为4块，每小块都是\(\frac { N }{ 2 } \times \frac { N }{ 2 } \)的矩阵。设\(FFT_{ N }\)的相位为，所以左上矩阵第j行第k列元素为\({ \omega }^{ 2jk }\)，左下矩阵的第j行第k列元素为\({ \omega }^{ 2jk+Nk }\)，右上矩阵的第j行第k列元素为\({ \omega }^{ 2jk+j }\)，右下矩阵的第j行第k列元素为\({ \omega }^{ 2jk+Nk+j+N/2 }\)。
如步骤(2)所示，因为我们知道\(FFT_{ N/2 }\)的相位为\(\omega ’=\frac { 2\pi i }{ N/2 } ={ \omega }^{ 2 }\)，而四个小矩阵的所有元素都可以用来\(\omega ’\)表示，即四个小矩阵都可以用包含\(FFT_{ N/2 }\)的表达式来表示。看到这里大家可能会纳闷，\(\frac { 1 }{ \sqrt { 2 } } \)是哪来的呢？我这就来解释：用左上的小矩阵举个例子，左上矩阵可以用\(\omega ’\)表达为：
$$\frac { 1 }{ \sqrt { N } } \begin{bmatrix} { \omega \prime }^{ 0 } & … & \\ … & & … \\ & … & { \omega \prime }^{ (\frac { N }{ 2 } -1)(\frac { N }{ 2 } -1) } \end{bmatrix}$$
而我们看看\(FFT_{ N/2 }\)的矩阵是什么：
$$\frac { 1 }{ \sqrt { N/2 } } \begin{bmatrix} { \omega \prime }^{ 0 } & … & \\ … & & … \\ & … & { \omega \prime }^{ (\frac { N }{ 2 } -1)(\frac { N }{ 2 } -1) } \end{bmatrix}$$
所以左上矩阵等于\(\frac { { FFT }_{ N/2 } }{ \sqrt { 2 } } \)，其余三个小矩阵也是类似的，所以我们要在整个矩阵前加上系数\(\frac { 1 }{ \sqrt { 2 } } \)。
步骤(3)就是对输入向量做\({ FFT }_{ N }\)运算了，而\({ FFT }_{ N }\)又能通过\(FFT_{ N/2 }\)求得，\(FFT_{ N/2 }\)能通过\(FFT_{ N/4 }\)求得，以此类推进行不断的递归，最后完成运算。
接下来，运用步骤(3)的结论，我们来看看是如何基于\(FFT_{ N/2 }\)实现\(FFT_{ N }\)的电路。
用电路表示快速傅立叶变换\(FFT_{ N }\)
从这张图我们看出，在已有的两个电路\(FFT_{ N/2 }\)基础上只要再做\(N/2\)次乘法、\(N/2\)次加法和\(N/2\)次减法，即\(O(N)\)次的运算就能得到的电路。所以快速傅立叶变换的复杂度为：
$$T\left( N \right) =2T\left( N/2 \right) +O\left( N \right) =O\left( N\log { N } \right) $$
说到这里，大家可能对的电路还是没有很直观的认识，那我们就来用一个例题来了解电路是如何具体实现的吧～
快速傅立叶变换例题
- 画出\({ FFT }_{ 8 }\)的电路，并说明你将会以什么顺序输入初始值\({ \alpha }_{ 0 },…,{ \alpha }_{ 7 }\)。
大家可以先不要看我下面给出的答案，先自己画一画，再对一对答案，看看你对电路是否理解对了。
图中\({ \omega }_{ 1 }\)是\({ FFT }_{ 2 }\)的相位，\({ \omega }_{ 2 }\)是\({ FFT }_{ 4 }\)的相位，\({ \omega }_{ 3 }\)是\({ FFT }_{ 8 }\)的相位。大家可能会疑惑，为什么输入顺序要把\({ \alpha }_{ 2 }\)和\({ \alpha }_{ 4 }\)，\({ \alpha }_{ 3 }\)和\({ \alpha }_{ 5 }\)这两组对调呢？可以看看图中由粉色和黑色标注的二进制数字就知道啦。在\({ FFT }_{ 2 }\)电路里，\({ \alpha }_{ 0 }\)只取第一个qubit为0即偶数，如果输入向量的另一个元素\({ \alpha }_{ 2 }\)为只取第一个qubit为0还是偶数，而当\({ \alpha }_{ 2 }\)和\({ \alpha }_{ 4 }\)调换后，\({ \alpha }_{ 4 }\)只取第一个qubit为1是奇数，就能满足一半偶数一半奇数的要求；同样的，调换后的\({ FFT }_{ 4 }\)电路里，\({ \alpha }_{ 0 }\)只取前两个qubit为00即偶数，\({ \alpha }_{ 4 }\)只取前两个qubit为10即偶数，\({ \alpha }_{ 2 }\)为01即奇数，\({ \alpha }_{ 6 }\)为11即奇数，同样也满足了一半偶数一半奇数的要求。所以输入顺序的改变是为了满足每次递归时的输入的前半部分为偶数位元素，后半部分为奇数位元素。
讲到这里，大家应该对快速傅立叶变换有了一定的认识了吧？是的，前面讲的离散傅立叶变换和快速傅立叶变换都是为了下一节的量子傅立叶变换做铺垫的！并且，惊人的是量子傅立叶变换的复杂度只有\(O\left( \log ^{ 2 }{ N } \right) \)！那我们下一节来看看这神奇的量子傅立叶变换是怎么做到这么低的复杂度～
评论(1)
好