# 量子傅立葉轉換

## 傅立葉轉換(FT)是甚麼?
大致來說，任一個函數可以用數個週期函數(正弦波，餘弦波等)的線性組合來逼近。基於這個理念，傅立葉轉換可以**將一個看似毫無規律的波，轉換成它是由哪些週期函數組合而成**。
>[簡易理解傅立葉轉換](https://youtu.be/spUNpyF58BY?si=AqrYefY1PmMR-aWV)

而 FT 可運用於各種領域，以下是一些常見的操作
1. 音頻信號處理： 在音頻處理中，傅立葉變換用於分析音頻信號的頻譜，從而進行噪聲消除、音效增強等操作。
2. 圖像處理： 傅立葉變換可用於圖像的頻率分析，實現濾波、邊緣檢測等功能。
3. 振動分析： 在機械工程中，傅立葉變換用於分析機械振動的頻率成分，從而診斷設備故障。
4. 通信系統： 在通信領域，傅立葉變換用於調製和解調制信號，分析頻譜效率，設計濾波器等。
5. 量子物理： 傅立葉變換在量子力學中用於解決薛定諤方程，分析粒子的波函數等。


## 離散傅立葉變換(DFT)
### 概述
離散傅立葉變換（Discrete Fourier Transform,俗稱DFT）將離散信號從**時間域轉換至頻率域**，能夠將複雜的時域訊號分解成不同頻率的成分。這在分析信號的頻率特徵時非常有用。
### 性質和應用
- 週期性：DFT 的頻譜圖具有週期性。
- 頻率分辨率：DFT 的頻率分辨率為 T (時間週期)的倒數
- 應用：音訊分析、濾波器設計、壓縮和圖像處理等
### 推導
離散傅立葉變換 X[k] 的公式為：
$$
X[k] = \sum_{n=0}^{N-1} x[n] e^\frac{-i2\pi kn}{N} , \ \ k = 0,1,2,...,N-1
$$
其中 𝑋[𝑘]表示頻率索引為 k 的頻譜成分，
$$e^\frac{-i2\pi kn}{N}$$
是 DFT 的基函數。
### 基函數
DFT的基函數部分由歐拉公式展開得到
$$e^\frac{-i2\pi kn}{N} = (\frac{2\pi kn}{N}) - i \ sin(\frac{2\pi kn}{N})$$
引此可發現基函數是由兩個正弦波跟餘弦波組成
## 量子傅立葉轉換又是甚麼?
量子傅立葉轉換(quantum Fourier transform,俗稱QFT)，可大致將其視為量子狀態下的經典離散傅立葉變換（Discrete Fourier Transform,俗稱DFT），能快速找到資料週期，並且==隨著位元增加，運算速度以指數成長==。

## QFT的目標
大致來說 QFT 的目標是調整相位，使不同的量子態可以產生區別，這與經典傅立葉變換中的時域到頻域轉換相似，而實際的目標則有以下四點。
1. 估計相位：將疊加態轉換為相位表示，這在周期性問題中特別有用，例如：Shor’s 算法利用 QFT 來識別週期，進行因數分解。
2. 數據壓縮與疊加態轉換：QFT 可以壓縮計算基態中的所有可能態並轉換為傅立葉表示，從而提高處理疊加信息的效率。
3. 增強量子干涉與測量：QFT 強化量子干涉，幫助精確估計疊加態中的相位信息。

## QFT用武之地
- 上述所提及的**Shor's algorithm**：用於因數分解，QFT 幫助識別週期，進而進行質因數分解。
- **量子相位估計**(quantum Phase Estimation,俗稱QPE)：其目標是找出一個特徵向量∣ψ⟩所對應的特徵值中的相位部分，也就是與三軸的夾角𝜃。
- **密碼分析與破解**：QFT 被用於加速經典密碼學問題的解決，特別是在涉及模運算的問題中。

總而言之，QFT 的目標是將量子態轉換到傅立葉的頻域空間中，幫助**處理和估計疊加態中的相位信息**。
## QFT的概述
### 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位元電路為例
在電路含有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]$$

### 不同數字在2位元電路下的意義
首先先布置一個複數平面

現在我們可以將==數字看為逆時針繞園的速度==，舉例來說
- 若輸入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就正好代表了不同的數字**==

### 以布洛赫球表示3位元下的量子電路
**拿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^πi = -1

>這裡的小數點是二進位的小數點：若j=0則帶入的0.0即為10進位的0，而j=1得出的0.1是為10進位的1/2。
**以結果論來說，其實就是把 j 放在二進位的小數點後的第一位**0
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步驟後就得到了最後輸出的結果
:::spoiler **二進位說明**
二進位制的小數點後面的部分。類似於十進位制的小數點後面代表分數（如10^-1, 10^-2），二進位制的小數點後面也是依照2的負次方來進行表示。具體來說：
- 小數點後的第一位：代表2^-1（1/2）
- 小數點後的第二位：代表2^-2（1/4）
- 小數點後的第三位：代表2^-3（1/8）
例如，二進位數字 `0.101` 可表示為：
- \( 1 * 2^{-1} + 0 * 2^{-2} + 1 * 2^{-3} \)
- \( = 1/2 + 0/4 + 1/8 \)
- \( = 0.5 + 0 + 0.125 \)
- \( = 0.625 \) （十進位制）
換句話說，二進位制的小數點後面的部分，就是通過將各位的數值乘以相應的2的負次方來表示的。
:::
---
# 量子相位估計

**量子相位估計**（**Quantum Phase Estimation, QPE**）是一種量子算法，這個算法結合了 **量子傅立葉變換和疊加原理** ，用來估算特定量子態的==相位==。對量子經過一系列的操作後，以QPE解得相位θ，在複雜應用中以高精度獲得相位訊息。

## 量子相位估計的發展史
- 1994年： 彼得·秀爾（Peter Shor）提出了著名的Shor算法，為QPE的發展奠定了基礎。
- 1995年： 基塔耶夫（Alexei Kitaev）等人提出了量子相位估計（QPE）算法，成為許多量子算法的核心組成部分，特別是在求解特徵值問題中發揮了重要作用。
- 2009年： Harrow、Hassidim和Lloyd提出了HHL算法，該算法將QPE應用於線性系統的求解。
- 2020年： 中國科學技術大學的研究團隊利用多光子量子糾纏，首次實現了分布式量子相位估計的實驗驗證。

## 量子相位估計的作用

因其準確性，QPE常作為各種牽涉量子領域的實作基礎，如

1. Shor algorithm：先前曾提及的Shor演算法正是採用了QPE，找到了同餘的週期
2. 量子模擬：用於模擬分子和材料的量子行為，幫助研究化學反應、材料設計等，特別是計算哈密頓算子的特徵能級
3. 機器學習：在量子機器學習中，QPE可以用來分析量子系統的特徵，進行數據降維、聚類等操作
4. 特徵值問題：可用於估算哈密頓量的特徵值，從而在量子物理和化學中計算系統的性質。

> 哈密頓量（Hamiltonian），主要用來描述一個物理系統的能量和動力學行為，在量子力學中表示為==系統的總能==，是為**粒子運動的能量**及**粒子間相互作用或外部場的能量**的相加

## QPE的數學原理
先介紹特徵值和特徵向量，在物理學、機器學習、量子計算中，這兩者常用來描述矩陣的性質。
### 特爭值與特徵向量（eigenvalue and eigenvector）
#### 定義
假設有一個 n × n 的矩陣 A 及一個非零向量 v 及純量(無方向性) 𝜆 ，且
$$ Av=λv $$
則對於 A 來說， **v 為其特徵向量（eigenvector），而 𝜆 為對應的特徵值（eigenvalue）** 。
#### 意義
這個公式表示，當我們對矩陣A 應用一個向量
v 時，結果 **向量不會改變方向（只有縮放），而縮放的比例就是這個向量的特徵值 𝜆** 。

在幾何學中，==特徵值為實數的情況下，畫一條通過原點的特徵向量，則在這個直線上的任何向量被 A 作用後，所得到的結果仍然會在這條直線上==。

#### 特徵方程
$$
\begin{aligned}
&Av=λv \\
\Rightarrow &Av−λv=0 \\
\Rightarrow &（A−λI）v=0
\end{aligned}
$$
>而其中的 I 是單位矩陣，能將 λ 轉為矩陣形式，才能與 A 進行計算

接著為使方程式成立，必須使
$$det（A−λI）=0$$
此行列式等式即為 **特徵方程**，解這個方程可以得到特徵值 𝜆。

### QPE的特徵值
回到QPE的部分，假設有一個矩陣 U 並乘上特徵相量 v ，特徵值中的 θ 則是我們要求的
$$ U |v\rangle = e^{iθ} |v\rangle$$

## QPE電路
在QPE電路中，出現的有兩個部分的寄存器
- 除最後一排以外：用於儲存欲估計的相位
- 最後一排：此寄存器表Ｕ的特徵向量，用於應用並計算出所求的角度

### 步驟
1. H-gate：對所有第一寄存器的qbit加上Hadamard gate，使產生疊加態以對後續相位測量做準備
2. 受控閘：
3. IQFT：對第一寄存器全體一起進行**逆量子傅立葉轉換**，目的是將各量子態轉換回基態，如此才能對其進行測量以得到結果