# Quantum Fourier Transform(QFT,量子傅立葉變換)
傅立葉變換是一種重要的數學運算，在各個領域中都有廣泛的應用。它允許我們在不同域之間轉換訊號，最常見的是在時域和頻域之間的轉換。傅立葉變換的本質是進行基礎轉換，使我們能夠分析訊號的頻率成分。

每個訊號都可以分解為特定頻率的複指數訊號的集合。我們的目標是找出每個頻率訊號的幅度，從而確定每個頻率對總訊號的貢獻程度。這可以通過傅立葉變換來實現，它將訊號從時間域表示轉換為頻率域表示，即將幅度與時間的關係轉換為振幅與頻率的關係。

傅立葉變換在訊號處理和圖像處理等方面有著重要的應用。例如，在訊號處理中，它被用來分析和處理各種波形，從而提取有用的信息；在圖像處理中，它可以用來進行圖像壓縮和特徵提取。因此，傅立葉變換是現代科學和工程中的一項關鍵技術，廣泛應用於通訊、音頻和視頻處理、醫學成像等諸多領域。

因此在我們開始介紹量子傅立葉變換QFT時，我們會從離散傅立葉變開始帶起，
## Discrete Fourier Transform (DFT,離散傅立葉變換)
離散傅立葉變換（DFT）是一種將離散時間信號轉換到頻域的數學運算。它的應用非常廣泛，包括信號處理、圖像處理、音頻分析等領域。DFT 將一組離散的複數數據點轉換成同樣數量的複數數據點，這些數據點表示原始信號的不同頻率成分。

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/HJILUicLR.png" alt="圖片內容" width="100%"/>
<br>
<p>訊號經DFT轉換後形式
<br>
</p>
</div>

## DFT 的數學表示

假設給定一個長度為 $N$ 的複數數列 $\{x_0, x_1, x_2, \ldots, x_{N-1}\}$，其離散傅立葉變換可以表示為：

\begin{split}
y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j e^{i \frac{2\pi}{N} jk} \quad \text{對於 } k = 0, 1, 2, \ldots, N-1
\end{split}

這裡：
- $x_j$ 是原始信號的第 $j$ 個樣本。
- $y_k$ 是傅立葉變換後的第 $k$ 個頻率分量。
- $N$ 是信號的樣本數。
- $e^{i \frac{2\pi}{N} jk}$ 是變換核，這裡的 $i$ 是虛數單位。

## 計算過程

從這個數學公式可以看到，DFT 是通過將每個樣本 $x_j$ 與一個複數指數函數相乘並累加得到的。這些複數指數函數對應於信號的不同頻率分量。每個 $y_k$ 表示信號中頻率 $\frac{k}{N}$ 的幅度和相位。

接下來公式詳細展示了計算前三個 $y_k$ 的過程：

### y~0~ 的計算

\begin{split}
y_0 = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j = \frac{1}{\sqrt{N}} (x_0 + x_1 + x_2 + \cdots + x_{N-1})
\end{split}

這意味著 $y_0$ 是所有樣本值的平均值。

### y~1~的計算

\begin{split}
y_1 = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j e^{i \frac{2\pi}{N} j} = \frac{1}{\sqrt{N}} (x_0 + e^{i \frac{2\pi}{N}} x_1 + e^{i \frac{2\pi}{N} \cdot 2} x_2 + \cdots + e^{i \frac{2\pi}{N} \cdot (N-1)} x_{N-1})
\end{split}

這意味著 ($y_1$) 是所有樣本值與一個複數旋轉因子相乘後的累加值，我們可以看到 $y_1$ 的 phase 相和 $y_0$ 的 phase 相，相差了1倍。

### y~2~ 的計算

\begin{split}
y_2 = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j e^{i \frac{2\pi}{N} \cdot 2j} = \frac{1}{\sqrt{N}} (x_0 + e^{i \frac{2\pi}{N} \cdot 2} x_1 + e^{i \frac{2\pi}{N} \cdot 4} x_2 + \cdots + e^{i \frac{2\pi}{N} \cdot 2(N-1)} x_{N-1})
\end{split}

這表示 $y_2$ 是所有樣本值與另一個複數旋轉因子相乘後的累加值，我們可以看到 $y_2$ 的 phase 相和 $y_0$ 的phase相相差了2倍。

所以$y_3$、$y_4$到$y_k$以此類推。

## Quantum Fourier Transform(QFT,量子傅立葉變換)
而QFT則是量子的DFT版本，QFT是一個重要的量子計算操作，主要用於量子算法如Shor's算法中。它是經典傅里葉變換在量子計算上的擴展，接下來我們將會介紹，十進位表示和二進位表示的QFT(量子傅立葉變換)數學推導，
### QFT十進位數學推導
首先是n個量子位元QFT(量子傅立葉變換)的十進位表示形式：
對於一個量子態 $|j\rangle$：

\begin{split}
[
|j\rangle \xrightarrow{F} \hat{F} \{|j\rangle\} := \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{2\pi i \frac{jk}{2^n}} |k\rangle
]
\end{split}

其中：
* $|j\rangle$：一個量子態，它可以被視為表示某種特定狀態的向量。
* $F$：量子傅里葉變換操作。
* $\hat{F}{|j\rangle}$：將量子態 $|j\rangle$ 變換成另一個態的表示。
* $n$：量子位的數量。
* $k$：變換後狀態的索引，從 0 到 $2^n-1$。
* $e^{2\pi i \frac{jk}{2^n}}$：複數指數函數，表示一個複數旋轉。

### 作用於量子態 $|\psi\rangle$ 上

初始量子態 $|\psi\rangle$ 表示為：

\begin{split}
[
|\psi\rangle = \sum_{j=0}^{2^n-1} x_j |j\rangle
]
\end{split}

將QFT $F$ 應用於 $|\psi\rangle$ 上：

\begin{split}
[
|\psi\rangle \xrightarrow{F} \sum_{j=0}^{2^n-1} x_j \hat{F} \{|j\rangle\} = \sum_{j=0}^{2^n-1} x_j \left( \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{2\pi i \frac{jk}{2^n}} |k\rangle \right)
\end{split}

將上式交換求和次序，得到：

\begin{split}
\sum_{k=0}^{2^n-1} \left( \sum_{j=0}^{2^n-1} x_j e^{2\pi i \frac{jk}{2^n}} \right) \frac{1}{\sqrt{2^n}} |k\rangle
\end{split}

我們定義 $y_k$ 為：

\begin{split}
y_k = \sum_{j=0}^{2^n-1} x_j e^{2\pi i \frac{jk}{2^n}}
\end{split}

因此，最終結果為：

\begin{split}
|\psi\rangle \xrightarrow{F} \sum_{k=0}^{2^n-1} y_k |k\rangle
\end{split}