量子傅立葉轉換（上） | EntangleTech 量子教育平台

# Quantum Fourier Transform(QFT,量子傅立葉變換)(上) ## 傅立葉轉換是甚麼？大致來說，任一個函數可以用數個週期函數(正弦波，餘弦波等)的線性組合來組合。基於這個理念，傅立葉轉換（Fourier transform）可以**將一個看似毫無規律的波，轉換成它是由哪些週期函數組合而成**。可以看這段[影片](https://youtu.be/spUNpyF58BY?si=AqrYefY1PmMR-aWV)，透過圖示化的方式理解傅立葉轉換。

## 離散傅立葉變換離散傅立葉變換（Discrete Fourier Transform, 簡稱 DFT）是一種重要的數學運算，它能將離散的時間訊號轉換到可以提取特徵的頻域，廣泛應用於信號處理、音頻分析、圖像壓縮等領域。傅立葉變換的核心是將訊號分解為不同頻率的成分，從而分析每個頻率對訊號的貢獻。這使我們能夠從時間域轉換到頻率域，進行訊號的頻率分析。DFT 是現代科學與工程中的關鍵技術，應用於通訊、音視頻處理和醫學成像等方面，也是我們後面推導量子傅立葉變換（QFT）的重要基礎。

訊號經DFT轉換後形式

## 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），可大致將其視為量子狀態下的經典 DFT，QFT 是一個重要的量子計算操作，主要用於量子算法如 Shor 演算法中。它是經典傅里葉變換在量子計算上的擴展，能快速找到資料週期，並且==隨著位元增加，運算速度以指數成長==，後面我們將會介紹，十進位表示和二進位表示的 QFT數學推導。 ## QFT的目標大致來說 QFT 的目標是調整相位，使不同的量子態可以產生區別，這與經典傅立葉變換中的時域到頻域轉換相似，而實際的目標則有以下四點。 1. 估計相位：將疊加態轉換為相位表示，這在周期性問題中特別有用，例如：Shor’s 算法利用 QFT 來識別週期，進行因數分解。 2. 數據壓縮與疊加態轉換：QFT 可以壓縮計算基態中的所有可能態並轉換為傅立葉表示，從而提高處理疊加信息的效率。 3. 增強量子干涉與測量：QFT 強化量子干涉，幫助精確估計疊加態中的相位信息。 ## 為什麼需要QFT？ - 上述所提及的**Shor's algorithm**：用於因數分解，QFT 幫助識別週期，進而進行質因數分解。 - **量子相位估計**(quantum Phase Estimation,俗稱QPE)：其目標是找出一個特徵向量∣ψ⟩所對應的特徵值中的相位部分，也就是與三軸的夾角𝜃。 - **密碼分析與破解**：QFT 被用於加速經典密碼學問題的解決，特別是在涉及模運算的問題中。總而言之，QFT 的目標是將量子態轉換到傅立葉的頻域空間中，幫助**處理和估計疊加態中的相位信息**。 ![截圖 2024-10-27 晚上8.28.11](https://hackmd.io/_uploads/Sk31f2je1g.png) ### QFT十進位表示首先是 $n$ 個量子位元 QFT 的十進位表示形式：對於一個量子態 $|j\rangle$： \begin{align} [ |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{align} 其中： * $|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{align} [ |\psi\rangle = \sum_{j=0}^{2^n-1} x_j |j\rangle ] \end{align} 將QFT 經過 $F$ 操作應用於 $|\psi\rangle$ 上： \begin{align} [ |\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{align} 將上式交換求和次序，得到： \begin{align} \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{align} 我們定義 $y_k$ 為： \begin{align} y_k = \sum_{j=0}^{2^n-1} x_j e^{2\pi i \frac{jk}{2^n}} \end{align} 因此，最終結果為： \begin{align} |\psi\rangle \xrightarrow{F} \sum_{k=0}^{2^n-1} y_k |k\rangle \end{align} 此結果為 QFT 的十進位表示，而我們要讓其可以在量子電路上做操作，我們要將其推導成二進位表示。