• 引言
• 离散傅立叶变换
• 快速傅立叶变换
• 量子傅立叶变换
• quantum circuit implementation
• 比较和讨论
• Reference

引言

本篇内容会研究离散傅立叶变换(DFT)的的经典形式和量子形式，以及对应的经典的复杂度为\(O(N\lg N)\)的快速傅立叶变换(FFT)算法，以及相应量子计算复杂度为\(O(\lg^2 N)\)的量子傅立叶变换(QFT)算法。通过这一过程的对比，也可以更好看清量子计算的实质和复杂度内涵的差异。

离散傅立叶变换

离散傅立叶变换自然是连续傅立叶变换的离散版本。和凝聚态物理打过交道的人，自然每天几十次的做这种活儿，把格点模型写到动量空间，以至于对离散傅立叶变换，都形成了如同九九乘法表一样熟悉的条件反射。书归正传，DFT 的定义为：

\[y_k = \frac{1}{\sqrt{N}}\sum_{n=0}^{N-1}x_n e^{-2\pi i k n/N}\]

也即给定N维向量\(x\)，我们通过该DFT变换可以同样的得出N个系数\(y_0,...y_{N-1}\)，用矩阵的语言重写以上DFT的定义即为：

\[\mathbf{y}=M\mathbf{x}, ~M_{kn}=\frac{1}{\sqrt{N}}e^{-2\pi i k n/N}\]

与之对应的我们也可以定义DFT的逆变换：

\[x_n = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} y_k e^{2\pi i k n/N}\]

也即：

\[\vec{x}=M^{\dagger}\vec{y}\]

验证两变换矩阵确实互逆 \(M^\dagger M=I\) 也很容易，只需始终牢记以下本文需反复使用的式子（可以由等比数列求和推导）：

\[\sum_{m=0}^{N-1}e^{2\pi im(a-b)/N}=N\delta_{ab}\]

不夸张的说，这个简单推导即可得出的纯数学关系式，可能是凝聚态和固体物理中出现最多的式子了。

额外的关于 DFT notation 的两个说明。第一，很多时候大家喜欢把DFT正向的系数记为1，而反向记为\(1/N\)。第二，有时候也有人令正向的指数上是正号，而逆变换的指数上是负号。这些标记本质上一样，但具体操作时可能要注意一下对应语境下的定义。

快速傅立叶变换

上文我们将 DFT 写成了矩阵形式，很容易看出给定 \(x\) 向量，DFT计算出 \(y\) 向量的复杂度是\(O(N^2)\)。我们将看到 FFT 算法可以将复杂度进一步降低。注意从现在开始，包括之后的量子部分，我们总是假定\(N=2^l\)，如果N不是2的幂次，可以先 padding 0 （严格来说，padding 0 再做 FFT 和原数据的 DFT 仅在连续极限是等价的，如果就是想严格按 DFT 定义计算的话，非2的幂次长度输入的处理，可以参考 [2]）。

FFT 的关键就是利用了 DFT 的周期性，也即 \(y_{k+N}=y_k\)，该周期性按照 DFT 的定义很容易证明。那么对于原 DFT 定义，我们可以将求和按奇数项和偶数项进行拆解，也即：

\[y_k= \sum_{m=0}^{N/2-1} x_{2m}e^{-2\pi i mk/(N/2)}＋e^{-2\pi i k/N}\sum_{m=0}^{N/2-1}x_{2m+1}e^{-2\pi i mk/(N/2)}\\\]

注意该式子的每一项对应的变为长度为\(N/2\)的向量的DFT，因此我们有 \(y_{k+N/2,1}=y_{k,1}\)，其中第二个下标可以为1，2，表示上边求和式的第一项或者第二项。由此，计算出所有 \(y_0,...y_{N-1}\) 总的乘法计算量从 \(N^2\) 降为了\(N^2/2\)。 我们可以将\(N/2\)维度的DFT按相同的方式继续递归分解下去，因此通过分治法，我们发现计算量变为了 \(T(N)=2T(N/2)+O(1)\)。根据递推公式的主方法，易知此时 DFT 的复杂度 \(O(N\lg N)\)。这就是 FFT 的原理，具体的递推实现和向量化实现，可以参考 [1]。当然还有其他很多不同的 DFT 加速的方案，这里不再介绍。

量子傅立叶变换

量子傅立叶变换其是就是经典的DFT，我们已经看到经典的DFT是一个矩阵，而量子力学中的算符在选定基之后也是一个矩阵。我们就称对应的量子算符是进行了量子傅立叶变换。考虑对应的基我们有：

\[Q_N\vert x\rangle =\frac{1}{\sqrt{N}}\sum_{y=0}^{N-1}e^{-2\pi i xy}\vert y\rangle\]

其中的\(\vert x\rangle\)代表一组正交基，该 state 处在N维的 Hilbert 空间，其第 x 个分量为1，其他分量为0对应的态即为\(\vert x\rangle\)。容易看出在该组基下面，QFT算符的矩阵表示为 \(Q_{N y,x}=\frac{1}{\sqrt{N}}e^{-2\pi i xy}\)，这与经典的 DFT 变换矩阵一致。更进一步来看量子变换与经典变换的一致性的话，则将 \(Q_N\) 作用在不同 \(\vert x\rangle\) 的叠加态\(\sum_x\alpha_x\vert x\rangle\)上，该叠加态的N个分量对应的 amplitude \((\alpha_x)\) 相当于是之前 DFT 中的输入向量 \((x_n)\)。而对应的变换之后的状态 \(\sum_y \beta_y\vert y\rangle\) 的各分量 amplitude 相当于之前 DFT 中的输出向量 \((y_k)\)。至此，经典和量子的傅立叶变换的等价性就非常清楚了。

注意到此时为了保证变换矩阵的幺正性，前边的\(1/N\)系数不能随便分配，只能老老实实的正变换和逆变换一边一个\(1/\sqrt{N}\)。

quantum circuit implementation

现在我们来看，如何高效的实现一个 quantum circuit 来模拟 \(Q_N\)。由于我们考虑的 circuit 都是维度为2的线性空间的直积，令 \(N=2^n\)，对于\(2^n\)自由度的 \(\vert x\rangle\)，我们用\(n\)个自由度为2的 qubit 代替。这恰好对应 x 数值的一个二进制表达。例如 \(N=8, 6=1\times2^2+1\times2^1+0\times 2^0\)，即 \(\vert 6\rangle =\vert 1\rangle\vert 1\rangle\vert 0\rangle\)。 对于量子态 \(\vert y\rangle\)，我们也用同样的二进制表达的多个 qubit 来表示。

根据以上的表示，考虑以下推导 ：

\[\begin{align} Q_N\vert x\rangle& = \frac{1}{2^{n/2}}\sum_{y=0}^{2^n-1} e^{-2\pi i x y/2^n}\vert y\rangle\\ &= \frac{1}{2^n}\sum_{y\in \{0,1\}^n}e^{-2\pi i x\sum_{j=0}^{n-1}2^jy_j/2^n}\vert y_n-1\rangle\vert y_{n-2}\rangle...\vert y_0\rangle\\ & = \otimes_{j=1}^n(\frac{1}{\sqrt{2}}\sum_{y_{n-j}\in \{0,1\}}e^{-2\pi i x y_{n-j}/2^{j}}\vert y_{n-j}\rangle) \end{align}\]

考虑输出直积态的每项，\(x=2^{n-1}x_{n-1}+...2^0 x_0\)，那么 \(e^{-2\pi i x/2^j}=\Pi_{k=0}^{n-1}e^{-2\pi i x_k 2^{k-j}}\)。考虑到 \(x_k = 0,1\)，当\(k\geq j\)时，对应的连乘积中的项均为1，没有贡献。因此

\[Q_N\vert x\rangle =\otimes_{j=1}^n\frac{1}{\sqrt{2}} ( \vert 0\rangle +e^{-2\pi i \sum_{k=0}^{j-1} x_k/2^{j-k}}\vert1\rangle )\]

因此在 quantum circuit 中，我们从 \(\vert y_n\rangle\) 开始，逐个构造即可。这一过程需要用到两种矩阵，一个是 Hadamard gate \(H\)，另一个是改变子空间相位的矩阵 \(R_d\)。

\[H=\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1& -1\end{bmatrix}~~R_d=\begin{bmatrix}1&0\\0 &e^{\pi i/2^d}\end{bmatrix}\]

对于每条线路，我们首先对输入态 \(\vert x_i\rangle\) 应用 H，使得波函数具有 \(\frac{1}{\sqrt{2}}(\vert 0\rangle+e^{-2\pi i x_i/2}\vert 1\rangle)\)的形式。之后我们就在这一基础上，不断向上边应用对应的 \(R_1,R_2…\) 这些 R 矩阵分别以 \(x_{i-1},x_{i-2}…\) 等状态为 condition。综合起来我们用如下的量子线路用来实现 QFT。

虽然\(R_d\)不是 universal gate，但可以通过 universal gate 实现，这一实现需要的 gate 数目只和要求的近似精度 \(\delta\) 有关，而与 N 无关。那么整个量子线路的 gate 数目随着 n 的标度易得为 \(O(n+0+1+2+…n-1)=O(n^2)=O(\lg^2 N)\)。具体关于 QFT 的算法推导和其在周期寻找算法的应用，可以参考 [3]。

事实上，更进一步的近似可以使得量子算法的复杂度降到 \(O(n\lg n)=O(\lg N\lg\lg N)\)。

比较和讨论

正如 Scott Aaronson 的博客 [4] 的 title page 所说，

If you take just one piece of information from this blog: Quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once.

事实上，量子计算机不是平行宇宙，也不是非确定图灵机，虽然量子计算的过程中信息是指数级的，但测量时我们将丢失大部分信息，因此量子计算机比经典计算机更快不是平庸的。正相反，甚至没有人证明在复杂度意义上，量子计算真的比经典计算更快。也就是说 \(P=BPP=BQP\) 是完全可能发生的。即使根据现在的证据，量子计算最多能解决一些处在 NPI 的问题（比如大数分解，但这一问题本身是否在 NPI 也存疑）。而且大家的共识是倾向于 \(BQP\subsetneq NP\)，因此即使造出了量子计算机，还是无助于根本上解决 NP 完全问题（当然总可以通过 Grover 算法对这类问题进行 quadratic 加速，但这对于指数屏障还是远远不够的）。说了这么多，就是想澄清，即使在理论上，现在的量子计算模型也没那么强。其在可计算性上和经典图灵机完全等价，在复杂度意义上，也比经典计算强不出太多。

因此在这样一种背景下，QFT 算法就显得很惊人。其将对应经典算法的复杂度 \(O(N\lg N)\) 直接降为了 \(O(\lg ^2N)\)，现在来看是从多项式级到对数级，但换个参照，明显就是从指数级到了多项式级，因此 QFT 是一个突破指数屏障的有效尝试。事实上，以 QFT 作为 subroutine 可以在 \(poly(\lg N)\) 的复杂度内，找到 N 个数据中存在的周期。而以周期寻找的算法作为 subroutine 就可以进行大数分解，也即 Shor’s algorithm。换句话说，归根结底，迄今为止最 nontrivial 的量子计算算法实现的指数屏障突破，其根源就来自于量子傅立叶变换相比经典对应的高效实现。

最后我们再来反思一下，当我们讨论量子算法的复杂度的时候，我们在讨论什么。首先，为什么经典算法按照量子算法同样的思路实现，不能达到 \(O(\lg^2N)\) 的复杂度？因为考虑一般的输入 \((x_n)\)，对应了 \(\sum_x\alpha_x\vert x\rangle\)，我们用经典的计算来模拟以上量子算法时，需要进行 \(O(N\lg^2N)\) 次操作，复杂度不比本来的 FFT 低。事实上，这一算法只有量子情形可行，原因就在于波的叠加。对于经典模拟，只能一个一个的计算，而真实的量子系统可以一次性的实现叠加波的正确的傅立叶变换。

另一个复杂度的反问就是，既然是按照数 gate 定义的量子复杂度。那我为什么不直接把 \(Q_N\) 整个矩阵看成一个整体 gate ，这样复杂度岂不只是 \(O(1)\)？这一问题的解答，在于量子复杂度的严格定义。[5] 中指出，刻画量子算法复杂度的不是简单的对应的 quantum circuit 中 gate 的数目，而是用来系统地生成不同 n 的对应 quantum circuit 的经典图灵机的复杂度。一般来说，按照安装 universal gate 的方法，经典算法的操作步数和最终 quantum circuit 的 gate 的数目在同一数量级。但如果把 \(Q_N\) 看成一个整体，由于需要通过经典图灵机依次生成该算符的各个矩阵元，从而来确定量子线路中该算符的“布线”，这一过程的算法复杂度不会小于 \(O(N^2)\)，这一复杂度远远高于了我们推导的量子算法。使用只作用在少数 qubit 上的 gate 来构造算法，其实质在于，对于给定的高自由度的大矩阵 \(Q_N\)，能不能找到一个总自由度大幅减少的矩阵分解方案。这一高效矩阵分解，对应的就是高效的量子算法，也正是线路上 gate 的摆放。

至于傅立叶变换成为了最显然的可能突破经典计算指数复杂度屏障的算法，从物理的角度看其实是非常自然的，毕竟量子力学超出经典物理的奥妙之处就在于波的叠加和干涉，而傅立叶变换无论怎么看都自然的居于这一奥妙的核心地位。于是就出现了这种神奇的境遇：一方面，傅立叶变换是描述波和波的干涉的核心数学工具；另一方面，基于波和波的干涉的计算模型也高效地实现了傅立叶变换。

Reference

1. 理解FFT算法
2. Non-power-of-2 FFT’s?
3. Advanced Quantum Information Theory
4. Scott’s blog
5. A. Yu. Kitaev, A. H. Shen, M. N. Vyalyi, Classical and Quantum Computation, American Mathematical Society.

EOF