# 5 The quantum Fourier transform and its applications
###### tags: `WS2020-IN2381-I2QC`

* 量子計算中，最有名的應用：**Shor's algorithm**
* 功能：n-bit 之整數分解 (factoring a n-bit integer)，或稱質因數分解 (破 RSA 用)。
* 時間複雜度：$O(n^2 \log n \log \log n)$
* 經典演算法：number field sieve
* 時間複雜度：$\exp(\Theta(n^{1/3} (\log n)^{2/3}))$
:::info
$O$：漸進上界，表示小於等於。
$\Theta$：漸進上界與下界，表示等於。
$\Omega$：漸進下界，表示大於等於。
:::

## 5.1 The quantum Fourier transform

### Discrete Fourier transform
* 定義：$F_N: \mathbb{C}^N \to \mathbb{C}^N$, $F_N(x) = y$
$$
y_k = \dfrac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j \mathrm{e}^{2 \pi i j k / N}
\ \ \ \ \ \ \ \ \ \
\forall\ k= 0, \cdots, N-1
$$
* 特性：
* $F_N$ 為 **unitary transformation**：對於所有 $x,x^{\prime} \in \mathbb{C}^{N}$，$\langle F_N(x^{\prime}) | F_N(x) \rangle = \langle x^{\prime} | x \rangle$ 成立。
* $F_N$ 為 $\mathbb{C}^{N \times N}$ 矩陣。

### Quantum Fourier transform
* 定義：
作用於一個 orthonormal basis $\begin{Bmatrix} | 0 \rangle, | 1 \rangle, \cdots, | N-1 \rangle\end{Bmatrix}$ 上的 QFT：
$$
| j \rangle
\mapsto
\dfrac{1}{\sqrt{N}} \sum_{k=0}^{N-1} \mathrm{e}^{2 \pi i j k / N} | k \rangle
$$
疊加態 (superposition) 的表示法：
$$
\sum_{j=0}^{N-1} x_j | j \rangle
\mapsto
\dfrac{1}{\sqrt{N}} \sum_{k=0}^{N-1} \sum_{j=0}^{N-1} \mathrm{e}^{2 \pi i j k / N} x_j | k \rangle =
\sum_{k=0}^{N-1} F_N(x)_k | k \rangle
$$
* 假設：
* $N$ 為 $2$ 的指數：$N = 2^n$，$n \in \mathbb{N}$。
* 如此 orthonormal basis 可寫作 $\begin{Bmatrix} | 0 \rangle, | 1 \rangle, \cdots, | 2^n-1 \rangle\end{Bmatrix}$，也就可表示成 **n-qubit quantum register**。
* 對於 $j \in \begin{Bmatrix} | 0 \rangle, | 1 \rangle, \cdots, | 2^n-1 \rangle\end{Bmatrix}$，$j=j_{n-1}j_{n-2}\cdots$。
* **n-qubit quantum register** 圖示：
* **公式 (QFT in product form)**：
$| j_{n-1} \cdots j_1 j_0 \rangle \mapsto \dfrac{1}{2^{n/2}} (|0\rangle + \mathrm{e}^{2 \pi i (0.j_0)}|1\rangle) (|0\rangle + \mathrm{e}^{2 \pi i (0.j_1 j_0)}|1\rangle) \otimes \cdots \otimes (|0\rangle + \mathrm{e}^{2 \pi i (0.j_{n-1} \cdots j_1 j_0)}|1\rangle)$
* 證明：
因為 $0.abcd \cdots = \dfrac{a}{2}+ \dfrac{b}{4} + \dfrac{c}{8} + \dfrac{d}{16} + \cdots$，
因此，
$$
\begin{eqnarray*}
| j \rangle \mapsto &&
\dfrac{1}{2^{n/2}} \sum_{k=0}^{N-1} \mathrm{e}^{2 \pi i j k / N} | k \rangle \\ = &&
\dfrac{1}{2^{n/2}} \sum_{k_{n-1}=0}^{1} \cdots \sum_{k_0=0}^{1} \mathrm{e}^{2 \pi i j (\sum_{l=1}^{n}k_{n-l}2^{-l})} | k_{n-1} \cdots k_1 k_0 \rangle \\ = &&
\dfrac{1}{2^{n/2}} \bigotimes_{l=1}^{n} \Bigg( \sum_{k_{n-l}=0} \mathrm{e}^{2 \pi i j k_{n-l} 2^{-l}} | k_{n-l} \rangle \Bigg) \\ = &&
\dfrac{1}{2^{n/2}} \bigotimes_{l=1}^{n} \Big( |0\rangle + \mathrm{e}^{2 \pi i j 2^{-l}}|1\rangle \Big) \\ = &&
\dfrac{1}{2^{n/2}} (|0\rangle + \mathrm{e}^{2 \pi i (0.j_0)}|1\rangle) \otimes (|0\rangle + \mathrm{e}^{2 \pi i (0.j_1 j_0)}|1\rangle) \otimes \cdots \otimes (|0\rangle + \mathrm{e}^{2 \pi i (0.j_{n-1} \cdots j_1 j_0)}|1\rangle)
\end{eqnarray*}
$$
:::info
因為 $q$ 為正整數，因此 $\mathrm{e}^{2 \pi i q} =1$，如此便可於最後一個等式將 $\mathrm{e}^{2 \pi i (ab.cd)}$ 約化為 $\mathrm{e}^{2 \pi i (0.cd)}$。
:::
* **構建 quantum circuit**：
* 矩陣表示法：$R_k := \begin{pmatrix} 1 & 0 \\ 0 & \mathrm{e}^{2 \pi i / 2^k} \end{pmatrix}$
* 圖示：
* 解說：
* 將第一個 qubit $j_{n-1}$ 進行 $\mathrm{Hadamard}\ \mathrm{gate}$ 運算：
首先我們知道 $H |x\rangle = \dfrac{1}{\sqrt{2}} (|0\rangle + (-1)^x |1\rangle)$，其中 $x \in \begin{Bmatrix} 0,1 \end{Bmatrix}$，
因為 $\mathrm{e}^{2 \pi i (0.0)_2} = 1$ 而 $\mathrm{e}^{2 \pi i (0.1)_2} = \mathrm{e}^{\pi i} = -1$，也就是說 $\mathrm{e}^{2 \pi i (0.x)_2} = (-1)^x$。
因此針對第一個 qubit 的運算可以這樣改寫：
$$
H |j_{n-1}\rangle = \dfrac{1}{\sqrt{2}} (|0\rangle + \mathrm{e}^{2 \pi i (0.j_{n-1})_2} |1\rangle)
$$
而整體 quantum register 的狀態則是：
$$
\dfrac{1}{\sqrt{2}} (|0\rangle + \mathrm{e}^{2 \pi i (0.j_{n-1})_2} |1\rangle) |j_{n-2} \cdots j_1 j_0 \rangle
$$
* 接下來進入 $\mathrm{controlled}\ R_2\ \mathrm{gate}$，只要 $|j_{n-2}\rangle = |1\rangle$ (control qubit)，那麼就會對 $\dfrac{1}{\sqrt{2}} (|0\rangle + \mathrm{e}^{2 \pi i (0.j_{n-1})_2} |1\rangle) |j_{n-2} \cdots j_1 j_0 \rangle$ 中第一個 qubit 的 $|1\rangle$ 乘以 $\mathrm{e}^{2 \pi i / 2^2} = \mathrm{e}^{2 \pi i (0.01)_2}$ (計算技巧同上一個步驟)：
$$
\dfrac{1}{\sqrt{2}} (|0\rangle + \mathrm{e}^{2 \pi i (0.j_{n-1}j_{n-2})_2} |1\rangle) |j_{n-2} \cdots j_1 j_0 \rangle
$$
* 第一個 qubit 經過了所有的 $\mathrm{controlled}\ R_k\ \mathrm{gates}$ 後：
$$
\dfrac{1}{\sqrt{2}} (|0\rangle + \mathrm{e}^{2 \pi i (0.j_{n-1} \cdots j_1 j_0)_2} |1\rangle) |j_{n-2} \cdots j_1 j_0 \rangle
$$
* 第二個 qubit 經過了 $\mathrm{Hadamard}\ \mathrm{gate}$ 運算後：
$$
\dfrac{1}{\sqrt{2}} (|0\rangle + \mathrm{e}^{2 \pi i (0.j_{n-1} \cdots j_1 j_0)_2} |1\rangle) \dfrac{1}{\sqrt{2}} (|0\rangle + \mathrm{e}^{2 \pi i (0.j_{n-2})_2} |1\rangle) |j_{n-3} \cdots j_1 j_0 \rangle
$$
* 以此類推，最後的輸出為：
$$
\dfrac{1}{2^{n/2}} (|0\rangle + \mathrm{e}^{2 \pi i (0.j_{n-1} \cdots j_1 j_0)_2}|1\rangle) (|0\rangle + \mathrm{e}^{2 \pi i (0.j_{n-2} \cdots j_1 j_0)_2}|1\rangle) \cdots (|0\rangle + \mathrm{e}^{2 \pi i (0.j_0)_2}|1\rangle)
$$
* 最後還要加上一個步驟：使用 $\mathrm{swap}\ \mathrm{gates}$ 翻轉 qubit 的順序。
$$
\dfrac{1}{2^{n/2}} (|0\rangle + \mathrm{e}^{2 \pi i (0.j_0)_2}|1\rangle) (|0\rangle + \mathrm{e}^{2 \pi i (0.j_0 j_1)_2}|1\rangle) \cdots (|0\rangle + \mathrm{e}^{2 \pi i (0.j_{n-2} \cdots j_1 j_0)_2}|1\rangle)
$$
:::info
從這邊也可推論出：
因為所有組成 QFT 的 quantum gates 都是 unitary，
因此 QFT 也一定是 unitary。
:::
* 計算 gates 的使用數量：
* 還有最後的 $\mathrm{swap}\ \mathrm{gates}$：$\dfrac{n}{2}$ ($n$ 為偶數) 或 $\dfrac{n-1}{2}$ ($n$ 為奇數)。
* 因此 QFT 需要 $O(n^2)$ 個 gates。
* 而 classical FFT 需要 $O(n 2^n)$ (exponential in n) 的運算複雜度。
* 但使用 QFT 有實際面的困難：無法直接測量輸出的振幅 (cannot measure output amplitudes directly)。

### Inverse discrete Fourier transform

#### 簡單地回顧 Fourier transformation
* 定義：$F_N: \mathbb{C}^N \to \mathbb{C}^N$, $F_N(x) = y$
$$
y_k = \dfrac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j \mathrm{e}^{2 \pi i j k / N}
\ \ \ \ \ \ \ \ \ \
\forall\ k= 0, \cdots, N-1
$$
* 圖解 1：
向量 $x$ 為週期函數 (例如音訊) $f:[0,1] \to \mathbb{C}$ 的離散化。
* 圖解 2：
因為 $f$ 是週期函數，因此 Fourier analysis 可以將 $f$ 分解成許多不同頻率之振盪 (oscillations) 的總和。
* 圖解 2 可以寫成以下公式：
$\mathrm{e}^{-2 \pi i k t}$ 為一頻率為 $2 \pi k$ 的「oscillations」，$y_k$ 則是相對應的振幅 (amplitude)。
$$
f(t) = \sum_{k=-\infty}^{\infty} y_k \mathrm{e}^{-2 \pi i k t}
$$
但如果我們考慮「離散的」Discrete Fourier transform $F_N$，我們只要有限的「點」：$0, \frac{1}{N}, \cdots, \frac{N-1}{N}$ 便可以組合回原來的週期函數 $f$。

#### 進入正題：Inverse discrete Fourier transform
* 首先，**discrete Fourier transform** $F_N$ 是 **unitary transformation**，因此 $F_N^{-1} = F^{\dagger}$。
* 接下來我們可以想像所有的「**Fourier modes**」$(\frac{1}{\sqrt{N}} \mathrm{e}^{-2 \pi i j k / N})_{j=0,\cdots,N-1}$ 互為單位正交 (orthonormal)：
$$
\Bigg \langle
\begin{pmatrix}
\frac{1}{\sqrt{N}} \mathrm{e}^{-2 \pi i (0) \cdot k^{\prime} / N} \\
\frac{1}{\sqrt{N}} \mathrm{e}^{-2 \pi i (1) \cdot k^{\prime} / N} \\
\vdots \\
\frac{1}{\sqrt{N}} \mathrm{e}^{-2 \pi i (N-1) \cdot k^{\prime} / N}
\end{pmatrix}
\Bigg |
\begin{pmatrix}
\frac{1}{\sqrt{N}} \mathrm{e}^{-2 \pi i (0) \cdot k / N} \\
\frac{1}{\sqrt{N}} \mathrm{e}^{-2 \pi i (1) \cdot k / N} \\
\vdots \\
\frac{1}{\sqrt{N}} \mathrm{e}^{-2 \pi i (N-1) \cdot k / N}
\end{pmatrix}
\Bigg \rangle = \dfrac{1}{N} \sum_{j=0}^{N-1} \mathrm{e}^{2 \pi i (k^{\prime} - k) / N} =
\delta_{k,k^{\prime}}
$$
其中任意 $k, k^{\prime} \in \begin{Bmatrix} 0, \cdots, N-1 \end{Bmatrix}$。
* 因此，Inverse discrete Fourier transform 公式可以寫作如下：
$$
f(\frac{j}{N}) = x_j = \dfrac{1}{\sqrt{N}} \sum_{k=0}^{N-1} y_k \mathrm{e}^{-2 \pi i j k / N}
$$
而 $x$ 與 $y$ 之關係如下：
$$
x \mathrel{\mathop{\rightleftarrows}^{F_N}_{F_N^{-1}}} y
$$

## 5.2 Phase estimation
* 許多量子演算法 (**quantum algorithms**) 的輔助步驟 (**auxiliary step**)。
* 前置步驟 (setup)：
* 么正算子 (**unitary operator**) $U$、特徵向量 (**eigenvector**) $|u\rangle$、特徵值 (**eigenvalue**) $\mathrm{e}^{2\pi i \varphi}$，且不失一般性假設 $0 \le \varphi \le 1$ (without loss of generality)：
$$
U |u\rangle = \mathrm{e}^{2\pi i \varphi} |u\rangle
$$
* 目標：求 $\varphi$。
* 圖示：Schematic of overall algorithm

### First stage
* 假設有一 **oracle** (black box) 可以準備好 $|u\rangle$ (第 $2$ 個 quantum register)，並對所有 $j \in \mathbb{N}$ (第 $1$ 個 quantum register) 執行 $\mathrm{controlled}\ U^{2^{j}}\ \mathrm{operations}$。
$$
U^{2^{j}} |u]rangle = \underbrace{U \cdots U}_{2^{j} \ \mathrm{times}} |u\rangle = \mathrm{e}^{2\pi i 2^{j} \varphi} |u\rangle
$$
* 圖式：
* 講解：
* **第 $2$ 個 register** 永遠保持在 $|u\rangle$ 的 eigenstate。
* 將 $U$ 的運算以 **eigenvalue** 的形式施加到**第 $1$ 個 register** 上：
$$
\begin{eqnarray*}
|\chi_1\rangle = &&
\dfrac{1}{2^{t/2}}(|0\rangle + \mathrm{e}^{2\pi i 2^{t-1} \varphi} |1\rangle) \otimes \cdots \otimes
(|0\rangle + \mathrm{e}^{2\pi i 2^{1} \varphi} |1\rangle) \otimes
(|0\rangle + \mathrm{e}^{2\pi i 2^{0} \varphi} |1\rangle) \\ = &&
\dfrac{1}{2^{t/2}} \sum_{k=0}^{2^{t}-1} \mathrm{e}^{2\pi i \varphi k} |k\rangle
\end{eqnarray*}
$$

### Second stage
* 目標：對**第 $1$ 個 register** 做 **inverse Fourier transform**。
(例如：反轉正向傅立葉變換的電路，並 taking the adjoint of all gates)
* 講解：
* 回顧 QFT 公式：$| j \rangle \mapsto \dfrac{1}{\sqrt{N}} \sum_{k=0}^{N-1} \mathrm{e}^{2 \pi i j k / N} | k \rangle$，且 $N = 2^t$。
* 如果我們把上述 **First stage 結果**的 $\varphi$ 定義成 $\frac{j}{2^t}$ ($j \in \begin{Bmatrix} 0,1,\cdots,2^t-1 \end{Bmatrix}$)，那麼 $\varphi$ 就可以用 $t$ 個 bits 表示成 $0.\varphi_{t-1} \cdots \varphi_1 \varphi_0$。
* 再對此 $|\varphi_{t-1} \cdots \varphi_1 \varphi_0 \rangle$ 做 **inverse Fourier transform** 就可以求得 $\varphi$！
$$
\begin{eqnarray*}
|\chi_2\rangle := &&
F_{2^{t}}^{-1} |\chi_1\rangle =
\dfrac{1}{2^{t/2}} \sum_{k, l=0}^{2^{t-1}} \mathrm{e}^{-2\pi i k l/2^{t}} \mathrm{e}^{2\pi i \varphi k} |l\rangle \\ = &&
\sum_{l=0}^{2^{t-1}} \underbrace{\dfrac{1}{2^{t}} \sum_{k=0}^{2^{t-1}} \mathrm{e}^{2\pi i (\varphi - l/2^{t}) k} |l\rangle}_{=:a_l} \\ = &&
\sum_{l=0}^{2^{t-1}} a_l |l\rangle
\end{eqnarray*}
$$
* 範例：
* 上述公式可畫成下圖，我們可以看到其中 $l = 5$ 的時候機率最高，而鄰近的 $2^{t} \varphi$ 即是我們要求的結果：
* 令 $l = b$ 為機率最高的結果，而 $b \in \begin{Bmatrix} 0,1,\cdots, 2^t-1 \end{Bmatrix}$，因此：
$$
\dfrac{b}{2^t} = 0.b_{t-1}\cdots b_1b_0 \le \varphi
$$
假設 $t=3$ 而 $b=5$，則 $\dfrac{5}{2^3} =0.625 \le\varphi = 0.65$。

### 誤差 (deviation) 的計算：
* 如果 $\delta := \varphi - \frac{b}{2^t}$ 且滿足 $0 \le \delta \le 2^{-t}$，則下述公式成立：
$$
\mathbb{P}(|m-b| > e_{\mathrm{tol}}) \le \dfrac{1}{2(e_{\mathrm{tol}}-1)}
$$
其中 $m$ 為最終量測的結果，$e_{\mathrm{tol}} \in \mathbb{N}$ 為誤差的容忍值 (deviation tolerance)。
白話的講：誤差 $|m-b|$ 愈高的情況愈不可能發生。
* 假設我們需要 $2^{-n}$ ($n$ 個 bits) 的精準度，那必須令 $e_{\mathrm{tol}} = 2^{t-n}-1$，其中 $t=n+p$ 為第 $1$ 個 register 的 qubit 數量：
$$
\mathbb{P}(|m-b| \le e_{\mathrm{tol}}) =
1 - \mathbb{P}(|m-b| > e_{\mathrm{tol}})
\ge
1 - \dfrac{1}{2(e_{\mathrm{tol}}-1)} =
1 - \dfrac{1}{\underbrace{2(2^p-2)}_{=:\epsilon}} =
1 - \epsilon
$$
* 解上述公式的 $p$：
$$
\begin{eqnarray*} 2\epsilon = \dfrac{1}{2^p-2}
\iff && 2^p = 2 + \dfrac{1}{2\epsilon} \\
\iff && p = \log_2 (2+\dfrac{1}{2\epsilon})
\end{eqnarray*}
$$
* 最後可以歸納，如欲在至少 $1-\epsilon$ 的機率下，求得精確度為 $n$ bits 的 $\varphi$，第 $1$ 個 register 的 bit 數量：
$$
t = n + \Bigg\lceil \log_2 \Bigg( 2 + \dfrac{1}{2\epsilon} \Bigg) \Bigg\rceil
$$

### 演算法總結：quantum phase estimation
* 輸入：
* **整數 $j$**，一黑盒子會對其做 $\mathrm{controlled}\ U^{2^{j}}\ \mathrm{operations}$。
* **eigenstate $|u\rangle$** ($U$ 的特徵向量，且特徵值為 $\mathrm{e}^{2\pi i \varphi}$)。
* **$t$ 個用來初始化的 qubits $|0\rangle$** ($t = n + \lceil \log_2 ( 2 + \frac{1}{2\epsilon} ) \rceil$)，如此保證 $2^{-n}$ 的精確度以及 $1 - \epsilon$ 的成功機率。
* 輸出：
* **n-bit 的 $\widetilde{\varphi}$** (近似於 $\varphi$)。
* 步驟：
1. initial state
$$
|0\rangle|u\rangle
$$
1. create superposition (Hadamard gates)
$$
\mapsto \dfrac{1}{\sqrt{2^t}} \sum_{j=0}^{2^t-1}|j\rangle|u\rangle
$$
1. apply black box
$$
\mapsto \dfrac{1}{\sqrt{2^t}} \sum_{j=0}^{2^t-1}|j\rangle (U^j|u\rangle) = \dfrac{1}{\sqrt{2^t}} \sum_{j=0}^{2^t-1} \mathrm{e}^{2\pi i j \varphi} |j\rangle |u\rangle
$$
1. inverse Fourier transform
$$
\mapsto \chi_2 |u\rangle
$$
1. measure first register
$$
\mapsto |\widetilde{\varphi}\rangle
$$

:::info
**Phase Estimation Algorithm 也可以使用於沒有 eigenstate $|u\rangle$ of $U$ 的狀態下：**

假設我們準備一 general state $|\psi\rangle$，
而 $|\psi\rangle$ 可以寫成 eigenstate $(|u_k\rangle)_k$ of $U$ 的線性組合：
$$
|\psi\rangle = \sum_k c_k |u_k\rangle
$$
令 $|u_k\rangle$ 的 eigenvalue 為 $\mathrm{e}^{2\pi i (\varphi_k)}$，則 Algorithm 最後的輸出結果為：
$$
\sum_k c_k |\chi_{2,k}\rangle |u_k\rangle
$$
其中近似結果 $\varphi_k$ 的 computational basis states $|u_k\rangle$ 上有著最大的權重 $|\chi_{2,k}\rangle$，
量測結果 $\widetilde{\varphi}_k$ 有著 $2^{-n}$ 的精確度以及 $|c_k|^2 (1 - \epsilon)$ 的成功機率逼近 $\varphi_k$。
:::

## 5.3 Applications: order-finding and factoring
* Order-finding problem 與 factoring problem 是等價的，因此能延伸 order-finding problem 的演算法以解出 factoring problem。

### 5.3.1 Order-finding (階數搜尋)
* 介紹：
* 正整數 $x<N$ 且 $x$ 與 $N$ 互質 ($\gcd(x,N)=1$)。
* **Order** of $x$ modulo $N$：必有最小的正整數 $r$ 滿足：
$$
x^r=1 \mod N
$$
* 此階數 (order) $r$ 為函數 $f:a\mapsto x^a$ 的週期 (period)：
$$
f(a+r) = f(a)
$$
* 前置作業：
* 正整數 $N$ 需要 $L$ 個 bit 來表示：
$$
L = \big\lceil\log_2(N)\big\rceil
$$
:::info
目前沒有任何已知的 order-finding 經典演算法 (classical algorithm) 可於 $L$ 的多項式時間內完成 (runtime polynomial in $L$)。
:::
* 么正算子 $U$ (對 L 個 qubits 進行運算)：
$$
U|y\rangle =
\begin{cases}
|x \cdot y\rangle, & 0 \le y < N \\
|y\rangle, & N \le y < 2^L\\
\end{cases}
$$
其中只有第一條 $0 \le y < N$ 條件下的計算會用到。
計算範例如下：($|5\rangle$ 可以表示成 $|0101_2\rangle\equiv |0\rangle|1\rangle|0\rangle|1\rangle$)
$$
U|5\rangle =
| 7 \cdot 5 \mod 12 \rangle =
| 35 \mod 12 \rangle =
| 11 \rangle
$$
:::info
$\mbox{controlled-}U^j\mbox{ operation}$ 可以藉由「**modular exponentiation**」實現，而這**需要 $O(L^3)$ 的 gates**。
:::
* $x$ 與 $N$ 必須互質，以保證 $x$ 必定有乘法反元素 $\widetilde{x}$：
$$
x \widetilde{x} = 1 \mod N
$$
* 原理：
* 首先，因為 $r$ 為 $x\mod N$ 的階數，因此我們可以定義 $|u_s\rangle$ 如下：
$$
\begin{align}
& |u_s\rangle = \dfrac{1}{\sqrt{r}} \sum_{k=0}^{r-1} \mathrm{e}^{-2 \pi i s k / r} \,|\, x^k \mod N \rangle \\
& \mbox{for }s = 0,1,\cdots,r-1
\end{align}
$$
我們可以看到，$r$ 在上述公式中扮演著「**週期 (period)**」的角色，$x^k$ 最多就到 $x^{r-1}$。
* 接下來，證明 $|u_s\rangle$ 為 $U$ 的 eigenstate，且有著 eigenvalue $\mathrm{e}^{-2 \pi i s / r}$：
$$
\begin{eqnarray*}
U|u_s\rangle = && \dfrac{1}{\sqrt{r}} \sum_{k=0}^{r-1} \mathrm{e}^{-2 \pi i s k / r} \,|\, x^{k+1} \mod N \rangle \\
= && \dfrac{1}{\sqrt{r}} \sum_{k=0}^{r-1} \mathrm{e}^{2 \pi i s / r} \mathrm{e}^{-2 \pi i s (k+1) / r} \,|\, x^{k+1} \mod N \rangle \\
= && \mathrm{e}^{2 \pi i s / r} \Bigg( \dfrac{1}{\sqrt{r}} \sum_{k=0}^{r-1} \mathrm{e}^{-2 \pi i s (k+1) / r} \,|\, x^{k+1} \mod N \rangle \Bigg) \\
= && \mathrm{e}^{2 \pi i s / r} |u_s\rangle
\end{eqnarray*}
$$
上述 $\Bigg( \dfrac{1}{\sqrt{r}} \sum_{k=0}^{r-1} \mathrm{e}^{-2 \pi i s (k+1) / r} \,|\, x^{k+1} \mod N \rangle \Bigg)$ 為週期函數，因此 $x$ 的指數變成 $k+1$ 並不會影響結果，仍為 $|u_s\rangle$。
* 最後，對 $\mathrm{e}^{2 \pi i s / r} |u_s\rangle$ 進行 **Phase Estimation**，便能獲得 $\frac{s}{r}$。
* 上述原理的**實作問題**：
:::danger
準備 $|u_s\rangle$ 居然需要先知道我們想要計算的 $r$！
:::
* 解決方案 (參考 Exercise 10.2(a))：
:::success
使用疊加態 (superposition) 作為 initial state $|u_s\rangle$：
$$
\dfrac{1}{\sqrt{r}} \sum_{s=0}^{r-1} |u_s\rangle = |1\rangle
$$
然後於 $|1\rangle$ 做 $U^j$ 運算 ($j$ 個 $U \mbox{ gates}$)：
$$
\begin{eqnarray*}
U^j |1\rangle
= && U^{j-1} \,|\,x \cdot 1 \mod N\rangle \\
= && U^{j-2} \,|\,x \cdot x \cdot 1 \mod N\rangle \\
= && \cdots \\
= && |\,x^j \mod N\rangle \\
\end{eqnarray*}
$$
:::
* 圖示：schematic overview
* **$t$ 個 qubits** 如同 phase estimaiton 章節所述：
$$
t = n + \Bigg\lceil \log_2 \Bigg( 2 + \dfrac{1}{2\epsilon} \Bigg) \Bigg\rceil
$$
* 輸出結果：$\widetilde{\varphi} = \frac{s}{r}$。
* 精確度：$n$ 個 qubits。
* 正確機率：$(1-\epsilon)/r$
* 會需要除以 $r$ 是因為 $|u_s\rangle$ 的 superposition 狀態：
$$
\dfrac{1}{\sqrt{r}} \sum_{s=0}^{r-1} |u_s\rangle = |1\rangle
$$
* 使用 $\mbox{continued fractions algorithm}$ 來計算 $s$ 與 $r$，這需要 $n=2L+1$ 的精確度。
* 關於「[連分數](https://zh.wikipedia.org/wiki/%E8%BF%9E%E5%88%86%E6%95%B0) ([Continued fraction](https://en.wikipedia.org/wiki/Continued_fraction))」。
* 如果 $s$ 與 $r$ 有公因數 (common factor)，那麼此 algorithm 會**輸出約分的結果** $\frac{s^{\prime}}{r^{\prime}}$。解決這個問題的辦法就是**重複運行此 algorithm**，那麼便會得到 $(s_1^{\prime}, r_1^{\prime})$ 與 $(s_2^{\prime}, r_2^{\prime})$，此時計算 $r_1^{\prime}$ 與 $r_2^{\prime}$ 的**最小公倍數 (least common multiple)** 即可獲得 $r$。

### 5.3.2 Factoring (Prime Factorization，質因數分解)

#### Prime factorization Definition
* 命題：given a composite integer $N$, what are the **prime numbers** which – when multiplied together – equal $N$?
* 目標：try to find a **non-trivial factor** of $N$.
* 策略：根據以下兩點觀察，可以將 **`factoring 問題`** reduce 成 **`order-finding 問題`**。
1. 找到一個 **non-trivial ($x \ne \pm 1 \mod N$) solution $x$** 滿足：
$x^2 =1 \mod N$，
那便能以此計算 **non-trivial factor of $N$**。
2. 一個隨機選擇，並且與 $N$ **互質**的 $y$ (意即 $\gcd(y,N)=1$)，「很有可能」：
* 擁有**偶數的階數 (order) $r$**。
* $y^{\frac{r}{2}} \ne \pm 1 \mod N$。
因此，令結果 $x=y^{\frac{r}{2}}$ 便可以輸出至第 1 個觀察以計算 factor。

#### Theorem 1.
* 假設：
* $N$ 是長度為 $L$ 個 bits 的合數 (composite number)。
* $x$ 為滿足 $x^2 =1 \mod N$ 的非凡解。
* 發現：
* $x=1 \mod N$ 或 $x=N-1=-1 \mod N$。
* 因此，至少 $\gcd(x-1,N)$ 與 $\gcd(x+1,N)$ 其中一個是 $N$ 的非凡因數解 (non-trivial factor)。
* 計算複雜度：$O(L^3)$
* 證明：
* 因為 $x^2=1 \mod N$，因此 $N$ 必須整除 $x^2-1$，也就是 $(x+1)(x-1)$。
* 由上可知，$N$ 一定至少與 $(x+1)$ 或 $(x-1)$ 有公因數。
* 根據假設，$x+1<N$，因此 $x-1<N$。也就是說，公因數不可能是 $N$ 本身。
* 最後使用 Euclid’s algorithm，可以藉由計算 $\gcd(x-1,N)$ 與 $\gcd(x+1,N)$ 來獲得 $N$ 的非凡因數解。

#### Theorem 2.
* 假設：
* $N = p_1^{\alpha_1} \cdots p_m^{\alpha_m}$ 為一個奇合數 (odd composite integer)的質因數分解 (prime factorization)。
* $x$ 為一個隨機挑選的整數，與 $N$ 互質且 $1 \le x \le N-1$。
* $r$ 為 $x$ modulo $N$ 的階數 (order)。
* 發現：
* $\mathbb{P}(\mbox{r is even and }x^{r/2} \ne -1 \mod N) \ge 1 - \dfrac{1}{2^m}$
* 假設 $m=2$，$r$ 為偶數的機率就是 $0.75$，如此便可以塞到 Theorem 1. 計算質因數分解。
* 證明：
* 從略。
* Nielsen and Chuang 2010, appendix A4.3.

#### Algorithm: reduction of factoring to order-finding
* 輸入：
* Composite integer $N$
* 輸出：
* Non-trivial factor of $N$
* 執行時間：
* $O(\log_2(N)^3)$ 個指令 (operations)
* 成功機率：
* $O(1)$ (失敗就再跑一次的意思)
* 步驟：
1. 當 $N$ 為偶數時，回傳**因數 $2$**。
2. 使用經典演算法 (classical algorithm) 檢查是否有整數 $a \ge 1$ 與 $b \ge 2$ 滿足 $N=a^b$，有的話回傳**因數 $a$**。
3. 隨機選擇整數 $x$ 滿足 $1 \le x \le N-1$，如果 $\gcd(x,N) > 1$，回傳**因數 $\gcd(x,N) > 1$**。
4. 使用 order-finding subroutine 找到 $x$ modulo $N$ 的階數 $r$。
5. 如果階數 $r$ 為「偶數」且「$x^{r/2} \ne -1 \mod N$」，便可以計算 $\gcd(x^{r/2}-1,N)$ 與 $\gcd(x^{r/2}+1,N)$，而其中之一必定是 non-trivial factor，驗證完成後回傳此**因數**。
如果 $r$ 不是「偶數」或「$x^{r/2} = -1 \mod N$」，則此步驟失敗，再從第 3 步驟重新開始。
:::info
* 第 2 步驟的檢查確保了第 5 步驟滿足 Theorem 2 的 $m \ge 2$。
* 第 3 步驟在 $\gcd(x,N) > 1$ 的條件下，直接迅速地回傳因數結果 (fast return)。這是為了確保第 4、5 步驟可計算滿足 Theorem 2 的「$x$ 互質於 $N$」。
* 只有第 4 步驟中的 order-finding subroutine 是「困難的」。
* 至目前為止還沒有 classical algorithm 可以以 $\log_2(N)$ 的多項式時間完成。
* 所以這邊必須使用量子運算的 order-finding！
:::

#### 參考資料
* [離散對數 - 維基百科，自由的百科全書](https://zh.wikipedia.org/wiki/%E7%A6%BB%E6%95%A3%E5%AF%B9%E6%95%B0)