# 量子傅立葉轉換(下)
### QFT的二進位表示方式
$$\text{QFT}|{j}\rangle = \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{\frac{2\pi i jk}{2^n}} |{k}\rangle$$
>|j⟩為一量子態，n是電路中量子位元
>相對於QFT，IQFT可進行反向的操作
### 兩量子位元電路為例
在電路含有2個量子位元的情況下，以**數學式**表示為
$$\text{QFT}_2|{\psi}⟩=\frac{1}{2}\sum_{k=0}^{3}e^{\frac{2\pi i jk}{4}} |{k}⟩$$
**矩陣型態**則是
$$\text{QFT}_2|{\psi}⟩=\frac{1}{2}\left[
\begin{array}{cccc}
1 & 1 & 1 & 1 \\
1 & i & -1 & -i\\
1 & -1 & 1 & -1\\
1 & -i & -1 & i \\
\end{array}
\right]$$
### 不同數字在兩量子位元電路下的意義
首先先布置一個複數平面
現在我們可以將==數字看為逆時針繞園的速度==，舉例來說
- 若輸入0，也就是00，則從1開始每次行進2π*0/4：
順序為**1，1，1，1**，也就是矩陣的第一列
- 若輸入1，也就是01，則從1開始每次行進2π*1/4：
順序為**1，i，-1，-i**，也就是矩陣的第二列
- 若輸入2，也就是10，則從1開始每次行進2π*2/4：
順序為**1，-1，1，-1**，也就是矩陣的第三列
- 若輸入3，也就是11，則從1開始每次行進2π*3/4：
順序為**1，-i，-1，i**，也就是矩陣的第四列
==可以發現，不同數字每次旋轉都角度都取決於這個部分，而**k就正好代表了不同的數字**==
### 以布洛赫球表示三量子位元下的量子電路
**拿5來當作例子，轉換成二進位後也就是101**
在還未產生疊加態時，如果將三個位元分開表示，則第二顆球的狀態會向下指向|1⟩，其餘兩顆則向上指向|0⟩。
產生疊加態後，因同時處在|0⟩和|1⟩的疊加態，則會處於球體的中心水平面，並且如下呈現
箭頭所指的方位，就如同前一節所說
- 首先看到最左邊的Bloch Sphere，因為是第一個位元，因此只會處在|+⟩或|-⟩的狀態，而從|+⟩開始每次逆時針移動2π/2，最後抵達|-⟩
- 接著是中間的，第二個位元有2^2種狀態，因此每次逆時針移動2π/4，抵達|i⟩
- 最後是右邊的球，擁有2^3共8種狀態，每次逆時針移動2π/8，經過五次到達|-i⟩與|-⟩之間
**以數學式表達**
\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步驟後就得到了最後輸出的結果
