上上篇 “Quantum Fourier Transform” 介紹了 DFT 與 QFT 之間的關係，並用一些小規模的範例讓讀者可以方便驗證該理論。接下來我們要往更一般化的形式以完善 QFT 的介紹。

有錯再麻煩指正，感謝。

符號

• $i = \sqrt{-1}$
• $N = 2^n, n = \log N$
• 為了避免搞混，這裡使用 $a, b$ 表示 n-bit 量子位元，原本的 $x, y$ 表示 N 個古典機率分佈。可以想作二進位編碼，例如，$a_0, …, a_{n-1}$ 皆為 $0$ 的 $\lvert 00…0\rangle$，表示 N 種情況中 $x_0$ 機率為 $1$ 其餘 $x_1, …, x_{N-1}$ 為 $0$ 的 $\begin{pmatrix}1&0&0&…&0\end{pmatrix}^T$。同理，$(b_0, …, b_{n-1})$ 可表示 $(y_0, …, y_{N-1})$。其實它們是在描述同一件事: $\lvert x\rangle = \begin{pmatrix}x_0 & x_1 & … & x_{N-1}\end{pmatrix}^T = \lvert a\rangle = \lvert a_0 a_1…a_{n-1}\rangle$
• $[0.a_0a_1…a_{n-1}]$ 的用法是二進位的分數表示，例如 $0.1$ 表示 $\frac{1}{2}$，用於方便表示連續 $\frac{1}{2^n}$。較嚴謹的定義為: $[0.a_0a_1…a_{n-1}] = \sum_{k = 0}^{n-1}a_k2^{-(k+1)}$。

Recall

QFT:

$$
\begin{equation*}
\begin{split}
y_k =& \frac{1}{\sqrt{N}}\sum^{N-1}_{n = 0}{x_n{\omega_N}^{kn}}, k = 0, 1, 2, …, N-1
\newline
\newline
\omega_N =& e^{\frac{2 \pi i}{N}}
\newline
{\omega_N}^k =& e^{{\frac{2 \pi i}{N}}k}, \text{Root of unity}
\end{split}
\end{equation*}
$$

Generalized QFT Matrix

矩陣形式

$\omega = e^{\frac{2\pi i}{N}}$, $\omega_N$ 的下標 $N$ 省略

$$
M_{QFT} = {\frac{1}{\sqrt{N}}
\small\begin{pmatrix}
\omega^{0\times 0} & \omega^{0\times 1} & \omega^{0\times 2} & \ldots & \omega^{0\times (N-1)}\\
\omega^{1\times 0} & \omega^{1\times 1} & \omega^{1\times 2}& \ldots & \omega^{1\times (N-1)}\\
\omega^{2\times 0} & \omega^{2\times 1} & \omega^{2\times 2}& \ldots & \omega^{2\times (N-1)}\\
\vdots & \vdots & \vdots & \ddots & \vdots \\
\omega^{(N-1)\times 0} & \omega^{(N-1)\times 1} & \omega^{(N-1)\times 2}& \ldots & \omega^{(N-1)\times (N-1)}\end{pmatrix}_{N\times N}}
$$

運算過程

$$
\begin{equation*}
\begin{split}
\lvert a \rangle&\xrightarrow{QFT}\lvert b\rangle
\end{split}
\end{equation*}
$$

其中依照情境 (因為 QFT 前後也可以有其他量子邏輯閘) 作古典跟量子之間的轉換:

$$
\begin{equation*}
\begin{split}
\begin{pmatrix}x_0 & x_1 & … & x_{N-1}\end{pmatrix}^T&\xrightarrow{encoding}\lvert a \rangle
\newline
\newline
\lvert b\rangle&\xrightarrow{decoding}\begin{pmatrix}y_0 & y_1 & … & y_{N-1}\end{pmatrix}^T
\end{split}
\end{equation*}
$$

Encoding 又可稱作 Quantum Embedding¹ 用於將古典資料轉成量子狀態，可細分為 Basis Embedding、Amplitude Embedding 兩種。這裡用的比較偏向後者: $\lvert x\rangle = \sum^{N-1}_{k = 0}x_k\lvert k\rangle$。

Decoding 可視為用觀測 (measurement) 去統計各狀態出現機率。

QFT Implemented by Quantum gates

為了一致性，這邊的電路或許跟其他地方的上下顛倒，不過這只是位元組順序 (Endianness²)不同，這邊採用 IBM 使用的 little endian，也就是 q[0] 為 LSB (圖中靠上位置)，q[n] 為 MSB (圖中靠下位置)。

$R_k = CU1(\lambda) = {\small\begin{pmatrix}1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & e^{i\lambda}\end{pmatrix}}, \lambda = \frac{2\pi}{2^k}$

拓展到 n-bit 的電路如下圖，其支援 $2^n = N$ 種情況當作輸入:

Derivation

由上圖可以看出 $a_0$ 被 $a_0, …, a_{n-1}$ 控制，其中 $H$ 就是巧妙地用來代表控制自己的旋轉。若簡化到只有 $a_0$ (1-bit QFT) 可以看成輸出為 $\frac{1}{\sqrt{2}}(\lvert 0\rangle + e^{2\pi i[0.a_0]}\lvert 1\rangle)$ 當 $a_0 = 0$ ($e^{2\pi i[0.a_0]} = 1$) 輸出不旋轉 Z 軸為 $\frac{1}{\sqrt{2}}(\lvert 0\rangle+\lvert 1\rangle)$；反之 ($e^{2\pi i[0.a_0]} = -1$) 旋轉變成 $\frac{1}{\sqrt{2}}(\lvert 0\rangle-\lvert 1\rangle)$。

$$
\begin{equation*}
\begin{split}
QFT(\lvert a\rangle) &= \lvert b_0\rangle \otimes\lvert b_1\rangle\otimes …\otimes\lvert b_{n-1}\rangle
\newline
&=
\frac{1}{\sqrt{2}}(\lvert 0\rangle + e^{2\pi i[0.a_0…a_{n-1}]}\lvert 1\rangle) \otimes…\otimes
\frac{1}{\sqrt{2}}(\lvert 0\rangle + e^{2\pi i[0.a_{n-1}]}\lvert 1\rangle)
\newline
&=
\frac{1}{\sqrt{2^n}}\big(\otimes^{n-1}_{k=0}(\lvert 0\rangle+e^{2\pi i[0.a_k…]}\lvert 1 \rangle)\big)
\end{split}
\end{equation*}
$$