# 量子傅立葉轉換(中)

在這一節中，我們將從「旋轉」的角度來看 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}

會發現接下來就在這三個數子中循環，我們將之對應到二維平面上就會長這樣，橫軸是實數，縱軸是虛數：

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/B1_bBlPtye.svg"
alt="i, omega^3=1" width="90%"/>
<br>
<p>
</p>
</div>

可以發現 $\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$ 度為單位做旋轉：

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/rkkHSgvFkx.svg"
alt="i, omega^4=1" width="90%"/>
<br>
<p>
</p>
</div>

綜合以上，我們知道 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$，也就是矩陣的第四列

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/HksvHevtke.svg"
alt="i, omega^4=1" width="80%"/>
<br>
<p>
</p>
</div>

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

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/HkSI4DhiR.png"
alt="i, omega^4=1" width="90%"/>
<br>
<p>
</p>
</div>

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

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/SkoiGkIY1x.svg"
alt="n=2 QFT" width="90%"/>
<br>
<p>n=3 的 QFT 電路圖
</p>
</div>

在此之前，我們先依照[前一篇文章附錄部分](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$：

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/BkiN7UUtyg.png"
alt="n=3 Bloch" width="90%"/>
<br>
<p>初始態 Bloch sphere
</p>
</div>

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

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/Sk9BJevKJe.png"
alt="n=3 Bloch" width="90%"/>
<br>
<p>經過 H gate 操作後各 qubits 的 Bloch sphere
</p>
</div>

先來看（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$ 軸的中間，如下圖所示

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/HJTBHI8tye.png"
alt="n=3 Bloch" width="90%"/>
<br>
<p> 經過 QFT 轉換後，數字 5（101）轉換到疊加態的樣子
</p>
</div>

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

<!--
**以數學式表達**
\begin{aligned}
QFT|x\rangle &= \frac{1}{\sqrt{2^n}} \sum_{y=0}^{2^n - 1} \exp\left(i 2 \pi x y / 2^n \right) |y\rangle \\
&= \frac{1}{\sqrt{2^n}} \left( |0\rangle + e^{i \frac{2 \pi}{2} x} |1\rangle \right)
\otimes \left( |0\rangle + e^{i \frac{2 \pi}{2^2} x} |1\rangle \right)
\otimes \cdots \\
&\otimes \left( |0\rangle + e^{i \frac{2 \pi}{2^{n-1}} x} |1\rangle \right)
\otimes \left( |0\rangle + e^{i \frac{2 \pi}{2^n} x} |1\rangle \right)
\end{aligned}

若以上方3位元下的5為例，則
$$\text{QFT}\ket{101} = \frac{1}{\sqrt{2}} \left( \ket{0} + e^{i\pi}\ket{1} \right) \frac{1}{\sqrt{2}} \left( \ket{0} + e^{i \frac{\pi}{2}}\ket{1} \right) \frac{1}{\sqrt{2}} \left( \ket{0} + e^{i \frac{5\pi}{4}}\ket{1} \right)$$

## QFT電路表示

### QFT電路會使用到的gate
1. Hadamard 閘 (H-gate)：
- 對每個量子位進行初步的變換，使得其進入均勻的疊加態。
- 數學形式為：
$$H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$$
- 效果：
$$ \begin{split}\begin{multline*} H\ket{0} \Rightarrow\frac{1}{\sqrt{2}} \left( \ket{0} + \ket{1} \right)
\\ H\ket{1} \Rightarrow\frac{1}{\sqrt{2}} \left( \ket{0} - \ket{1} \right) \end{multline*}\end{split}$$

2. 控制旋轉閘 (Controlled Phase Rotation Gate,R_k)：
- 這是 QFT 中的核心操作，控制的旋轉角度取決參數k，即旋轉2π/2^k
- 數學形式為：
$$R_k = \begin{pmatrix} 1 & 0 \\ 0 & e^{2 \pi i/2^k} \end{pmatrix}$$
- 效果：
$$ \begin{split}\begin{multline*} R_k \ket{0} \Rightarrow\ket{0}
\\ R_k\ket{1} \Rightarrow e^{\frac{2\pi i}{2^k}}\ket{1}\end{multline*}\end{split}$$

3. 交換閘 (Swap Gate)：
- 最後一步會用到交換閘來反轉量子位的順序。這是因為 QFT 的輸出通常 會顛倒排列。
$$Swap = \begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0\\0 & 1 & 0 & 0 \\0 & 0 & 0 & 1 \end{pmatrix}$$

### QFT電路架設
**在量子電路中，QFT電路是由一系列的 H-gate 和旋轉閘組成。**
#### 概述
QFT電路首先對每一個量子位施加 H-gate 來產生疊加態，然後透過旋轉閘進行相位操作。最終，QFT 的電路會進行量子位交換來修正排列順序，從而得到正確的傅立葉變換結果。
#### 步驟

1. 對第一位元施加H-gate產生疊加態
2. 如圖，施加多個**控制旋轉閘**，而分別由第二至第n的位元操控控制
3. 對第二位元施加H-gate產生疊加態
4. 施加多個**控制旋轉閘**，而分別由第三至第n的位元操控控制
5. 重複上述直到第n個位元施加H-gate(無須控制旋轉閘)
6. 在第1及n位元放上交換閘，第二及第n-1，以此類推(此步驟不一定需要做)

### 電路推導

#### 二進位制小數點
在下文表示量子態中會用到二進位制，因此這邊以一個簡陋的轉換公式帶過
$$ \begin{aligned}
0.x_1x_2x_3… &= \frac{x_1}{2} + \frac{x_2}{4} + \frac{x_3}{8}+…\\二進位制 &\Rightarrow 分數
\end{aligned}$$

#### 這邊以進行最多次旋轉的第1個位元為例
1. 首先經過H-gate後，狀態變成
$$\left\{
\begin{array}{ll}
\frac{1}{\sqrt{2}} (|0\rangle + |1\rangle) & (j_{1} = 0) \\
\frac{1}{\sqrt{2}} (|0\rangle - |1\rangle) & (j_{1} = 1)
\end{array}
\right.$$
而這種不確定的量子態也可以這樣表達
$$ \frac{1}{\sqrt{2}} (|0\rangle + e^{2 \pi i 0.j_1}|1\rangle)$$

>歐拉恆等式：e^{\pi i} = -1(可參考數學系列文章)

>這裡的小數點是二進位的小數點：若j=0則帶入的0.0即為10進位的0，而j=1得出的0.1是為10進位的1/2。
**以結果論來說，其實就是把 j 放在二進位的小數點後的第一位**

2. 接著經過第一個旋轉受控閘(以第二位元控制)
如果第二位元為0，旋轉控制閘就不會作用於第一位元；但當第二位原為1，第一位元的量子態就會旋轉2π/2^k度，而第二位元的k就等於2，因此是2π/4度。
若是把量子態以二進位表達則如下：
$$ \frac{1}{\sqrt{2}} (|0\rangle + e^{2 \pi i 0.j_1 j_2}|1\rangle)$$

3. 接下來所有的受控選轉閘如上處理之後會變成
$$ \frac{1}{\sqrt{2}} (|0\rangle + e^{2 \pi i 0.j_1 j_2 j _3…j_n}|1\rangle)$$

4. 接下來所有位元都重複上述1~3步驟後就得到了最後輸出的結果
-->