量子傅立葉轉換(中)

作者:
施宇宸、林昱誠(Yu-Cheng Lin)、徐育兆
閱讀時間:
10
分鐘
# 量子傅立葉轉換(中) 在這一節中,我們將從「旋轉」的角度來看 QFT 怎麼運作,也就是反覆出現的 $e^{i\frac{2\pi}{N}}$。首先我們先從 "*N*th-root"([方根](https://zh.wikipedia.org/zh-tw/%E6%96%B9%E6%A0%B9)) 問題開始。 ## 方根問題 我們現在要來解一道數學題,我們想找一個複數 $\omega$,讓 $\omega$ 的 $N$ 次方可以等於 1($N$ 是自然數),$\omega$ 會是什麼,即: \begin{split} \omega^N=1 \end{split} 當 $N=1$ 時,那 $\omega$ 只有一種可能,就是 $1$。當 $N=2$ 時, $\omega$ 可以是 $+1$ 或 $-1$。那當 $N=3$ 呢?要解這問題,我們就要從歐拉公式下手: \begin{split} e^{i\theta}=\cos{\theta}+i\sin{\theta} \end{split} 從上式我們知道 $\theta=2\pi$ 時,$e^{i\theta}=1$(可以自己驗證看看),要 $\omega^3=1$ 代表: \begin{split} \omega^3=1=\cos{2\pi}+i\sin{2\pi} \end{split} 由此我們得知,$\theta=\frac{2}{3}\pi$: \begin{split} \omega=e^{i\frac{2}{3}\pi} \end{split} 現在我們來做個計算: \begin{split} \omega^0&=e^{i0\times\frac{2}{3}\pi}=1\\ \omega^1&=e^{i1\times\frac{2}{3}\pi}=\cos{\frac{2}{3}\pi}+i\sin{\frac{2}{3}\pi}=-\frac{1}{2}+\frac{\sqrt 3}{2}i \\ \omega^2&=e^{i2\times\frac{2}{3}\pi}=-\frac{1}{2}-\frac{\sqrt 3}{2}i \\ \omega^3&=1 \\ \omega^4&=\frac{1}{2}+\frac{\sqrt 3}{2}i \\ \vdots \end{split} 會發現接下來就在這三個數子中循環,我們將之對應到二維平面上就會長這樣,橫軸是實數,縱軸是虛數:
i, omega^3=1

可以發現 $\omega$ 的作用就是在單位元上做旋轉,每次以 $\frac{2}{3}\pi$ 單位做旋轉,每三次旋轉就回到原本的位置,這時就我們會說 $\omega^1$ 與 $\omega^2$ 為 primitive(等於 1 的不能作為 primitive) 當 $N=4$ 時呢?要滿足 $\omega^4=1$,則 $\theta=\frac{2}{4}\pi$,那: \begin{split} \omega^0&= e^{i0\times \frac{2}{4}\pi}=1\\ \omega^1&= e^{i1\times \frac{2}{4}\pi}=i\\ \omega^2&= e^{i2\times \frac{2}{4}\pi}=-1\\ \omega^3&= e^{i3\times \frac{2}{4}\pi}=-i \end{split} 這個就相當於在單位元上每次以 $90$ 度為單位做旋轉:
i, omega^4=1

綜合以上,我們知道 primitive 的通式為: \begin{split} \omega=e^{i\frac{2\pi}{N}} \end{split} 熟悉的指數因子出現了。 ## QFT 現在我們回到 $n=2$ 的 QFT: \begin{align}\tag{1} QFT|j\rangle=\frac{1}{\sqrt 4}\sum_{k=0}^3 e^{i\frac{2\pi}{4}jk}|k\rangle \end{align} 其矩陣則為 \begin{split} \frac{1}{\sqrt 4} \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & \omega & \omega^2 &\omega^3\\ 1 & \omega^2 & \omega^4 &\omega^6\\ 1 & \omega^3 & \omega^6 &\omega^9 \\ \end{bmatrix}=\frac{1}{2} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i\\ 1 & -1 & 1 & -1\\ 1 & -i & -1 & i \\ \end{bmatrix} \end{split} 我們可以將(1)式中的 $e^{i\frac{2\pi}{4}jk}$看成在單位圓上==逆時針繞園的速度==(或是說以多少角度為單位做旋轉): - 當 $k$ 為 $0$,也就是$|00\rangle$,則從 $1$ 開始旋轉 $0\times\frac{2\pi}{4}$,那就是一直在原點沒有動: 順序為 $1,1,1,1$,就是矩陣的第一列 - 當 $k$ 為 $1$,也就是 $|01\rangle$,則從 $1$ 開始每次旋轉 $1\times\frac{2\pi}{4}$,就是每次旋轉 90 度: 順序為 $1,i,-1,-i$,也就是矩陣的第二列 - 當 $k$ 為 $2$,也就是 $|10\rangle$,則從 $1$ 開始每次行進$2\times\frac{2\pi}{4}$,就是每次旋轉 180 度: 順序為 $1,-1,1,-1$,也就是矩陣的第三列 - 當 $k$ 為 $3$,也就是 $|11\rangle$,則從 $1$ 開始每次行進$3\times\frac{2\pi}{4}$,就是每次旋轉 270 度: 順序為 $1,-i,-1,i$,也就是矩陣的第四列
i, omega^4=1

==可以發現,每次旋轉的角度取決於下圖紅框這部分,而 $k$ 就正好決定要轉多少==
i, omega^4=1

## 以 Bloch sphere 表示 接著我們利用 [Bloch sphere](https://www.entangletech.tw/lesson/basic-algorithm-09) 來看怎麼做旋轉。以三個 qubits 的 QFT 為例,當初始態為 $5$,其二進位是 $101$。
n=2 QFT

n=3 的 QFT 電路圖

在此之前,我們先依照[前一篇文章附錄部分](https://www.entangletech.tw/lesson/algorithm-05)的數學推理來看他產生的效果是什麼 \begin{align} QFT|101\rangle&= \frac{1}{\sqrt 8}[|0\rangle+(-1)^{j_0}|1\rangle]\otimes S^{j_0}[|0\rangle+(-1)^{j_1}|1\rangle] \otimes T^{j_0}S^{j_1}[|0\rangle+(-1)^{j_2}|1\rangle] \\ &=\frac{1}{\sqrt 8}[|0\rangle+(-1)^{1}|1\rangle]\otimes S^{1}[|0\rangle+(-1)^{0}|1\rangle] \otimes T^{1}S^{0}[|0\rangle+(-1)^{1}|1\rangle] \\ &=\frac{1}{\sqrt 8}(|0\rangle-|1\rangle)\otimes e^{i\frac{1}{2}\pi}(|0\rangle+|1\rangle)\otimes e^{i\frac{1}{4}\pi}(|0\rangle+|1\rangle) \\ \end{align} 回到 Bloch sphere,在還沒經過 QFT 處理前,初始三個 qubits 的 Bloch sphere 如下圖。第二個 Bloch sphere 的箭頭指向南方 $|1\rangle$,其餘兩顆則向上指向 $|0\rangle$:
n=3 Bloch

初始態 Bloch sphere

三個 qubits 經過 H gate 操作後,不意外地你應該知道他們的 Bloch sphere 箭頭指向哪:
n=3 Bloch

經過 H gate 操作後各 qubits 的 Bloch sphere

先來看(2)式中的第一項,對應電路圖就是最後一個 qubit(不過經過 SWAP gate 後,最後一個 qubit 的狀態跑到第一個 qubit),不做旋轉(或是說 $0\times\frac{2\pi}{8}$),所以最後 Bloch sphere 箭頭仍然指向 $-X$ 軸。 第二個 qubit 對應(2)式中第二項,旋轉 $2\times\frac{2\pi}{8}$ ,也就是 90 度,所以從 $+X$ 軸逆時針轉到 $+Y$ 軸。 (2)式中的第三項,對應電路圖中第一個 qubit(一樣經過 SWAP 後資訊跑到第三個 qubit),旋轉 $1\times\frac{2\pi}{8}$,所以箭頭從 $-X$ 軸跑到 $-X$ 與 $-Y$ 軸的中間,如下圖所示
n=3 Bloch

經過 QFT 轉換後,數字 5(101)轉換到疊加態的樣子

可以看到 QFT 是如何從原本人類看得懂的數字 $5$(二進位制 101)在 Bloch sphere 轉換到量子電腦看得懂在疊加態下 $5$ 的樣子。同理,今天量子電腦如果算出這樣的結果,經過 inverse QFT 之後就會變成我們人類看得懂的數字 $5$。
課程目錄