1. 在线看片av免费观看
  2. 量子計算

和小白蔡一起入门量子計算–量子傅立葉變換(二)

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

本系列的內容將參考我正在上的課程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) \)?!那我們下一節來看看這神奇的量子傅立葉變換是怎麽做到這麽低的複雜度~

本文爲原創文章,版權歸屬作者和量子客所有,轉載需要授權!

本文由量客特約作者撰写,转载需授权,欢迎至信: Support@qtumist.com ,转载请注明出处:/post/6160

發表評論

登錄後才能評論