本系列的内容将参考我正在上的课程UCI CS264 Quantum Computing,感谢我的老师Prof. Sandy Irani。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\)维空间中 是振幅(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) \)的快速傅立叶变换吧~
本文为原创文章,版权归属作者和量子客所有,转载需要授权!
评论(5)
傅立叶~~~~么么哒
不错
第三个公式对吗?怎么来的呀?按照欧拉公式,不应该这样写吧?求指点~
小白求带!
我可以加下你qq学习吗