和小白蔡一起入门量子计算–量子傅立叶变换（一）

哈喽大家好，我是量子小白蔡佳人。这个系列将分享我个人在入门量子计算时的理解和心得，我想用比较通俗易懂，轻松愉快的方式来讲述量子计算里的知识～因为在量子领域我也是小白一个，我也还在学习《量子计算》这门课程，希望能和大家一起学习交流，如果我的文章内容有误，请一定要帮我指出来，我也能发现自己在哪部分理解的不对，请与我联系我会改正滴！

本系列的内容将参考我正在上的课程UCI CS264 Quantum Computing，感谢我的老师Prof. Sandy Irani。此外，本篇文章还参考了André Chailloux的MPRI Quantum Computing Lecture 2；Umesh Vazirani的UCB CS294 Quantum Computing Lecture 7；张镇九和张昭理的量子信息讲座续讲第一讲，感谢以上老师们的材料。

经典的离散傅立叶变换

傅立叶变换(Fourier Transform)大家经常能在各个领域数学计算中能见到，包括信号处理、数据压缩等等。不过在量子计算里，为了方便，我们通常把傅立叶变换表示成一个\(N\times N\)的幺正矩阵(unitary matrix)，且矩阵的所有元素有相同的振幅(magnitude)。比如当 \(N=2\)时，即在二维空间里，傅立叶变换\({ F }_{ 2 }\)就变成了我们熟悉的阿达玛变换 \(H\)(Hadamard Transform):

\({ F }_{ 2 }=H=\frac { 1 }{ \sqrt { 2 } } \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\qquad \qquad\left( 1 \right) \)

所以对二维空间里的向量做傅立叶变换，就相当于对向量做阿达玛变换。

但是在三维空间（以及更高维度的空间）里，就不可能用实数来表示傅立叶变换了，因为我们不可能从\( { \{ +1,-1\} }^{ 3 } \)里找到三维空间的正交向量(orthogonal vectors)作为正交基。

而复数是个很神奇的东西，可以让我们定义任意的傅立叶变换\({ F }_{ 2 }\)。但是怎么用复数来表示矩阵元素呢？聪明的量子科学家们想到了欧拉公式：

\({ e }^{ \pi i }+1=0\quad \quad \Rightarrow \quad \quad { e }^{ \pi i }=-1 \qquad \qquad \left( 2 \right) \)

欧拉公式是个非常神奇的，在数学、量子力学等领域广泛运用的公式，它将数学里最重要的几个常数联系到了一起：两个超越数：自然对数的底e，圆周率π；两个单位：虚数单位i和自然数的单位1，以及数学里常见的0（引自欧拉公式——真正的宇宙第一公式）。

现在让我们来看看怎么用欧拉公式来表示矩阵元素的量。设相位(phase) 为

\(\omega ={ e }^{ \frac { 2\pi i }{ N } }=cos\left( \frac { \pi }{ 2 } \right) +i\cdot sin\left( \frac { \pi }{ 2 } \right) \qquad \qquad \left( 3 \right) \)

则在矩阵的j行k列的元素为\(\frac { 1 }{ \sqrt { N } } { \omega }^{ jk }\)，其中\(j\in \{ 0,…,N-1\} \) ，\(k\in \{ 0,…,N-1\} \) 。这样矩阵里的所有元素都可以用复数表示啦～

看到这里大家是不是还有点懵？那让我们来看一段直观的定义来理解怎么用复数表示\(N\)维的傅立叶变换：

要点1. 离散傅立叶变换

定义变换的输入向量为\(\left( { \alpha }_{ 0 },…,{ \alpha }_{ N-1 } \right) \)，该向量在\(N\)维空间中，\(\alpha\)是振幅(amplitude)；

输出向量\(\left( { \hat { \alpha } }_{ 0 },…,{ \hat { \alpha } }_{ N-1 } \right) \)为，该向量在\(N\)维空间中，

其中输出向量的第k个元素可表示为：

\({ \hat { \alpha } }_{ k }=\frac { 1 }{ \sqrt { N } } \sum _{ j=0 }^{ N-1 }{ { \omega }^{ jk }{ \alpha }_{ j } }\qquad \qquad \left( 4 \right) \)

所以维的离散傅立叶变换(Discrete Fourier Transform)\({ DFT }_{ N }\)的过程可以用以下矩阵的乘法表示：

\(\frac { 1 }{ \sqrt { N } } \left[ \begin{matrix} 1 & 1 & 1 & 1 & … & 1 \\ 1 & { \omega }^{ 1 } & { \omega }^{ 1\cdot 2 } & { \omega }^{ 1\cdot 3 } & … & { \omega }^{ 1\cdot (N-1) } \\ 1 & { \omega }^{ 2\cdot 1 } & { \omega }^{ 2\cdot 2 } & { \omega }^{ 2\cdot 3 } & … & { \omega }^{ 2\cdot (N-1) } \\ 1 & { \omega }^{ 3\cdot 1 } & { \omega }^{ 3\cdot 2 } & { \omega }^{ 3\cdot 3 } & … & { \omega }^{ 3\cdot (N-1) } \\ & & & & & \\ … & … & … & … & { \omega }^{ jk } & … \\ & & & & & \\ 1 & { \omega }^{ (N-1)\cdot 1 } & { \omega }^{ (N-1)\cdot 2 } & { \omega }^{ (N-1)\cdot 3 } & … & { \omega }^{ (N-1)\cdot (N-1) } \end{matrix} \right] \cdot \begin{bmatrix} { \alpha }_{ 0 } \\ { \alpha }_{ 1 } \\ { \alpha }_{ 2 } \\ { \alpha }_{ 3 } \\ … \\ { \alpha }_{ k } \\ … \\ { \alpha }_{ N-1 } \end{bmatrix}=\begin{bmatrix} \hat { { \alpha }_{ 0 } } \\ \hat { { \alpha }_{ 1 } } \\ \hat { { \alpha }_{ 2 } } \\ \hat { { \alpha }_{ 3 } } \\ … \\ \hat { { \alpha }_{ k } } \\ … \\ \hat { { \alpha }_{ N-1 } } \end{bmatrix}\qquad \qquad \left( 5 \right) \)

其中矩阵就是\({ DFT }_{ N }\)，其中第j行第k列的元素为：

\(\left[ DFT \right] _{ jk }=\frac { 1 }{ \sqrt { N } } \omega ^{ jk }\qquad \qquad \left( 6 \right) \)

所以也\({ DFT }_{ N }\)可以表示成

\(DFT_{ N }=\frac { 1 }{ \sqrt { N } } \left( \begin{matrix} & … & \\ … & \omega ^{ jk } & … \\ & … & \end{matrix} \right) \qquad \qquad \left( 7 \right) \)

接下来我们来解释一下上面的知识点。

首先，通过公式(2)(3)我们可以得到

\({ \omega }^{ N }={ \left[ { e }^{ 2\pi i/N } \right] }^{ N }={ e }^{ 2\pi i }=cos\left( 2\pi \right) +i\cdot sin\left( 2\pi \right) =1 \qquad \qquad \left( 8 \right) \)

这个公式接下来将会大有用处哦～

此外，公式(5)中输出向量的第k个元素\(\hat { { \alpha }_{ k } } \)可以用公式(4)的展开式来表达：

\(\hat { { \alpha }_{ k } } =\frac { 1 }{ \sqrt { N } } \left( { \omega }^{ 0k }{ \alpha }_{ 0 }+{ \omega }^{ 1k }{ \alpha }_{ 1 }+…+{ \omega }^{ jk }{ \alpha }_{ j }+…+{ \omega }^{ (N-1)k }{ \alpha }_{ (N-1) } \right) \qquad \qquad \left( 9 \right) \)

这样展开了以后，大家是不是比较好理解了呢？

另外，傅立叶变换 \(mod N\)(Fourier Transform mod N)也是\({ DFT }_{ N }\)的另一种表示方法，其中\(mod N\)是取余。很多资料\({ DFT }_{ N }\)里也是简写成\({ FT }_{ N }\)。

如果你理解了以上部分，那咱们就可以来学习离散傅立叶变换的其中一个重要性质啦。因为有这个性质，离散傅立叶变换才能被运用在量子计算里。

要点2. 离散傅立叶变换是幺正的

是幺正的(unitary)，因为矩阵的每一列的范数(norm)都为1，所以任意两列都是正交的(orthogonal)。网上有很多\({FT }_{ N }\)的所有列两两正交的传统数学证明，这里就不展开讲啦，给个公式大家自己理解就好了，设\({FT }_{ N }\)的任意两列为第\(k\)列和第\({ k }\prime \)列，有以下过程能证明它们是相互正交的：

\(\sum _{ j=0 }^{ N-1 }{ \frac { 1 }{ \sqrt { N } } { \omega }^{ jk } } \cdot \frac { 1 }{ \sqrt { N } } { \omega }^{ jk\prime }=\frac { 1 }{ N } \sum _{ j=0 }^{ N-1 }{ { \omega }^{ j(k-k\prime ) } }=\begin{cases} 0\qquad if\quad k\neq k\prime \\ 1\qquad if\quad k=k\prime \end{cases} \qquad \qquad \left( 10 \right) \)

既然学量子计算，那我们就要用量子计算的方式来证明啦～

设\(|{ f }_{ k }\rangle \)为矩阵的第\(k\)列的向量，有：

\(|{ f }_{ k }\rangle =\frac { 1 }{ \sqrt { N } } \begin{bmatrix} { \omega }^{ 0 } \\ { \omega }^{ 1\cdot k } \\ { \omega }^{ 2\cdot k } \\ … \\ { \omega }^{ (N-1)\cdot k } \end{bmatrix}=\frac { 1 }{ \sqrt { N } } \sum _{ a=0 }^{ N-1 }{ { \omega }^{ ak } } \qquad \qquad \left( 11 \right) \)

因为该向量为正交向量(orthogonal vector)，且范数为1，我们可以认为\(|{ f }_{ k }\rangle \)是组成\(N\)维空间的标准正交基(orthonormal basis)的一个向量，所有向量组成一个标准正交基。所以证明矩阵的所有列相互正交的问题就变成了证明在维空间里的基\(\left\{ |{ f }_{ 0 }\rangle ,..,|{ f }_{ k }\rangle ,…,|{ f }_{ N-1 }\rangle \right\} \)是标准正交的。让我们回忆一下证明基是标准正交的条件：

当\(k=j\)时，\(\langle { f }_{ k }|{ f }_{ j }\rangle =\langle { f }_{ k }|{ f }_{ k }\rangle= 1\)；

当\(k\neq j\)时，\(\langle { f }_{ k }|{ f }_{ j }\rangle =0\).

接下来我们就来证明这两个条件成立：

因为从公式(3)我们可以推得\({ \omega }^{ k }\)的共轭(conjugate)，共轭就是对虚部即含\(i\)的部分取负：

\({ \left( { \omega }^{ k } \right) }^{ \ast }={ \left( { e }^{ 2\pi i\cdot k/N } \right) }^{ \ast }={ e }^{ -\frac { 2\pi i\cdot k }{ N } }={ \omega }^{ -k }\qquad \qquad \left( 12 \right) \)

所以\(|{ f }_{ k }\rangle \)的对偶为：

\(\langle { f }_{ k }|=\frac { 1 }{ \sqrt { N } } \sum _{ a=0 }^{ N-1 }{ { \omega }^{ -ak } } \qquad \qquad \left( 13 \right) \)

所以可得任意两向量的内积(Inner Product)为：

\(\langle { f }_{ k }|{ f }_{ j }\rangle =\frac { 1 }{ N } \sum _{ a=0 }^{ N-1 }{ { \omega }^{ -ak } } \cdot { \omega }^{ aj } =\frac { 1 }{ N } \sum _{ a=0 }^{ N-1 }{ { \omega }^{ a(j-k) } } \qquad \qquad \left( 14 \right) \)

由此公式很容易得到当\(k=j\)时，内积\(\langle { f }_{ k }|{ f }_{ j }\rangle \)为1。

我们来看看当\(k\neq j\)这个情况，我们设\({ \omega }^{ (j-k) }=A\)，通过等比数列的求和公式我们可得知 \(\sum _{ a=0 }^{ N-1 }{ { A }^{ a } } =\frac { { A }^{ N }-1 }{ A-1 } \)，而运用公式(8)我们可得到\({ \omega }^{ (j-k)\cdot N }-1={ e }^{ (i\cdot \frac { 2\pi }{ N } \cdot N)\cdot (j-k) }-1={ e }^{ (i\cdot 2\pi )\cdot (j-k) }-1=1^{ (j-k) }-1=0\)，所以此时内积为0：

\(\frac { 1 }{ N } \sum _{ a=0 }^{ N-1 }{ \left[ { \omega }^{ (j-k) } \right] ^{ a } } =\frac { 1 }{ N } \cdot \frac { { \omega }^{ (j-k)\cdot N }-1 }{ { \omega }^{ (j-k) }-1 } =\frac { 1 }{ N } \cdot \frac { 0 }{ { \omega }^{ (j-k) }-1 } =0\qquad \qquad \left( 15 \right) \)

至此我们集齐了证明标准正交基的两个条件，所以也就证明了\({FT }_{ N }\)的所有向量都相互正交。

呼～我们终于证明完啦，到这里离散傅立叶变换的内容就结束了吗？不，趁着我们的证明思路还在脑海里，我来简单提一下它的另一个性质：对称性。\({FT }_{ N }\)是对称的(symmetric)，从公式(12)我们可以推得\({FT }_{ N }\)的逆变换(inverse transform)为\({ { FT }_{ N } }^{ -1 }={ \left( { { FT }_{ N } } \right) }^{ \ast }\)。

好了，这一小节的最后，我们来看一看\({DFT }_{ N }\)的复杂度，因为它是个\(N\times N\)的矩阵，所以乘法上的复杂度为\(O\left( { N }^{ 2 } \right) \)。这个复杂度还是有一点高了的，那有没有复杂度更低的傅立叶变换呢？有的！让我们进入下一节来看看复杂度为\(O\left( { N }\log { N } \right) \)的快速傅立叶变换吧～