Last
First
個人首頁
帳號設定
登出
關於我們
最新消息
課程學習
興趣探索(測試版)
登入
立即開始
Last
First
個人首頁
帳號設定
登出
會員登入
歡迎進入量子學習的新紀元!
忘記密碼?
或
以 Google 帳號登入
Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
新用戶?
立即註冊
,開啟您的量子學習之旅。
量子計算入門(下):量子演算法
・第
7
課
量子傅立葉轉換(中)
作者:
施宇宸、林昱誠(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} 會發現接下來就在這三個數子中循環,我們將之對應到二維平面上就會長這樣,橫軸是實數,縱軸是虛數:
可以發現 $\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$ 度為單位做旋轉:
綜合以上,我們知道 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$,也就是矩陣的第四列
==可以發現,每次旋轉的角度取決於下圖紅框這部分,而 $k$ 就正好決定要轉多少==
## 以 Bloch sphere 表示 接著我們利用 [Bloch sphere](https://www.entangletech.tw/lesson/basic-algorithm-09) 來看怎麼做旋轉。以三個 qubits 的 QFT 為例,當初始態為 $5$,其二進位是 $101$。
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$:
初始態 Bloch sphere
三個 qubits 經過 H gate 操作後,不意外地你應該知道他們的 Bloch sphere 箭頭指向哪:
經過 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$ 軸的中間,如下圖所示
經過 QFT 轉換後,數字 5(101)轉換到疊加態的樣子
可以看到 QFT 是如何從原本人類看得懂的數字 $5$(二進位制 101)在 Bloch sphere 轉換到量子電腦看得懂在疊加態下 $5$ 的樣子。同理,今天量子電腦如果算出這樣的結果,經過 inverse QFT 之後就會變成我們人類看得懂的數字 $5$。
量子傅立葉轉換(下)
algorithm
8
量子傅立葉轉換(中)
algorithm
7
量子傅立葉轉換(上)
algorithm
6
以 Pennylane 做測量
pennylane
6
用 Pennylane 建立量子邏輯閘
pennylane
5
用 Pennylane 建立量子電路
pennylane
4
Colab 與 Jupyter 介面介紹
pennylane
3
安裝 Pennylane
pennylane
2
Deutsch-Jozsa 演算法(下)
algorithm
5
Deutsch-Jozsa 演算法(上)
algorithm
4
量子演算法總覽
algorithm
1
Deutsch 演算法(下)
algorithm
3
Deutsch 演算法(上)
algorithm
2
量子計算概覽:當電腦遇上量子世界
basic-algorithm
1
自學資源與路線:入門量子計算的第一步
basic-algorithm
2
量子電路:量子邏輯閘的實踐
basic-algorithm
17
測量:讀取計算結果
basic-algorithm
16
量子邏輯閘(下):量子邏輯閘的特性
basic-algorithm
15
量子邏輯閘(中):多個量子位元的操作
basic-algorithm
14
量子位元 (下):量子糾纏
basic-algorithm
13
量子位元(中):多個量子位元
basic-algorithm
12
布洛赫球面 (下):解讀量子邏輯閘的運作
basic-algorithm
11
布洛赫球面(上):量子位元可視化
basic-algorithm
10
量子邏輯閘(上):單一量子位元操作
basic-algorithm
9
量子位元(上):量子計算的基本單位
basic-algorithm
8
重視經典電腦:過渡到量子電腦
basic-algorithm
7
Pennylane 簡介
pennylane
1
演算法複雜度
basic-algorithm
6
經典邏輯閘(下):邏輯閘的特性
basic-algorithm
5
經典邏輯閘(上):電腦運算的基礎
basic-algorithm
4
電腦的世界只有 0 與 1:二進位表示法
basic-algorithm
3
量子硬體總覽
hardware-general
1
第三題:Many-Body Quantum Dynamics
ibm-2023-spring
3
第二題:Quantum Random Walks and Localization
ibm-2023-spring
2
第一題:Trotterization
ibm-2023-spring
1
如何綜合評估量子電腦的表現
hardware-general
10
Qubit 狀態的壽命(相干時間):T2
hardware-general
9
Qubit 狀態的壽命(相干時間):T1
hardware-general
8
保真度(Fidelity):衡量量子邏輯閘的指標
hardware-general
7
附錄 C:絕熱通道
hardware-general
13
如何操作 Qubit:絕熱通道(Adiabetic passage)
hardware-general
6
附錄 B:拉比震盪
hardware-general
12
如何操作 Qubit:拉比震盪(Rabi Oscillation)
hardware-general
5
附錄 A:雙態系統
hardware-general
11
Deutsch 演算法
basic-algorithm
18
雙態系統(Two Level System):Qubit 的基礎
hardware-general
4
DiVincenzo Criteria:量子電腦的五大標準
hardware-general
3
自學資源與路線:入門量子電腦硬體的第一步
hardware-general
2
課程撰寫中
s
1
特徵向量和特徵值(eigenvector and eigenvalue)
linear-algebra
9
量子計算中的特殊矩陣
linear-algebra
8
張量積(Tensor product)
linear-algebra
7
Orthonormal Bases
linear-algebra
6
正交(Orthogonality)
linear-algebra
5
基(Basis)
linear-algebra
4
數學基礎:量子計算的起點
linear-algebra
2
量子計算的數學之鑰:線性代數入門
linear-algebra
1
什麼是量子電腦?
quantum-computer-basics
1
量子電腦如何改變世界
quantum-computer-basics
2
如何實現量子電腦
quantum-computer-basics
7
電腦怎麼做計算
quantum-computer-basics
3
疊加態
quantum-computer-basics
5
量子糾纏
quantum-computer-basics
6
進入量子世界
quantum-computer-basics
4
自學資源與路線
quantum-computer-basics
8
狄拉克(Dirac)表示法
linear-algebra
3
量子電腦現況與未來
quantum-computer-basics
9
上ㄧ課
#上一課課程名稱
下ㄧ課
#下一課課程名稱
課程目錄