Shor算法

**秀爾演算法**（英語：Shor's algorithm）是一個於 1994 年發現的，以數學家彼得・秀爾命名，針對整數分解題目的的量子演算法（在量子計算機上面運作的演算法）。不正式地說，它解決的題目是：給定一個整數 $N$ ，找出它的質因數。在一個量子計算機上面，要分解整數 $N$ ，秀爾演算法的運作需要多項式時間（時間是 $\log N$ 的某個多項式這麼長， $\log N$ 在這裡的意義是輸入的檔案長度）。準確來說，該演算法花費 $O((\log N)^{3})$ 的時間，展示出質因數分解問題可以使用量子計算機以多項式時間解出，因此在複雜度類 BQP 裡面。這比傳統上已知的最快的因數分解演算法普通數域篩選法所花費的次指數時間 —— 大約 $O(e^{1.9(\log N)^{\frac {1}{3}}(\log \log N)^{\frac {2}{3}}})$ 還要快了一個指數。

秀爾演算法非常重要，它意味著：假如有可用的量子計算機，我們可以破解基於公開密鑰加密的演算法（比如 RSA 加密演算法）。RSA 演算法的基礎在於假設了我們不能有效率的分解一個已知的整數。就目前所知，這假設對傳統（即非量子）的電腦為真；沒有已知的傳統演算法可以在多項式時間內解決這個問題。但秀爾演算法展示了因數分解問題在量子計算機上可以很有效率的解決，所以一個足夠大的量子計算機可以破解 RSA。這對於建立量子計算機和研究新的量子計算機演算法是一個強大的動力。

2001 年，IBM 的一個小組展示了秀爾演算法的實例，使用 NMR 實驗的量子計算機及 7 個量子位元，將 15 分解成 3×5。不過，對於 IBM 的實驗是否是量子計算的真實展示，有一些疑慮出現，因為沒有發現纏結現象。IBM 的實驗之後，也有其他的團隊以光學量子位元實驗秀爾演算法，並強調可觀察到其纏結現象。

## 程式

試著解決的問題是：給定一個合成數 $N$ ，找到整數 $p$ 在 $1$ 和 $N$ 之間且不包含 $1$ 和 $N$ ，並且 $N$ 整除於 $p$ 。

秀爾演算法包含兩個部份：

1. 一個以傳統電腦運作的簡化演算法，將因數分解簡化成搜尋階問題。
2. 一個量子演算法，解決搜尋階問題。

### 傳統部份

1. 選擇任意數字 $a$ < $N$
2. 計算 gcd（ $a$ , $N$ ）。這裡可以使用輾轉相除法來計算。
3. 若 gcd ( $a$ , $N$ ) ≠ 1，則我們有了一個 $N$ 非平凡的因數，因此這部份結束了。
4. 否則，利用下面的週期尋找子程式（Period-finding subroutine，下面會列出）來找出下面這個函式的週期 $r$ ：

　
: $f(x)=a^{x}\ {\mbox{mod}}\ N$ ,

換句話說，找出 $a$ 在 $\mathbb {Z} _{N}$ 裡面的階 $r$ ，或者最小的正整數 $r$ 令 $f(x+r)=f(x)$ 。
5. 若 $r$ 是奇數，回到第一步。
6. 若 $a$ $r$ /2 ≡ -1 (mod $N$ ), 回到第一步。
7. gcd(a $r$ /2+1, $N$ ) 與 gcd (a $r$ /2-1, $N$ ) 至少有一個是 $N$ 非平凡的因數。分解完成。

### 量子部份：週期尋找子程式（Period-finding subroutine）

這個演算法使用的量子線路是為了在給定一個固定常數 $N$ 以及一個任意常數 $a$ 之下，找出 $f(x)=a^{x}\mod {N}$ 所設定的。給定 $N$ , 找出 $Q$ = 2 $q$ 且合乎 $N^{2}\leq Q<2N^{2}$ （這同時表示 $Q/r>N$ ）。輸入和輸出量子位元暫存器需要儲存從 0 到 $Q$ -1 所有值的疊加態，因此分別需要 $q$ 個量子位元。這裡使用看起來比所需的數量還要更多一倍的量子位元，保證了即使週期 $r$ 的大小逼近 $N$ /2，也至少有 $N$ 個不同的 $x$ 會產生相同的 $f(x)$ 。

程式如下：

1. 將暫存器初始化成

　
: $Q^{-1/2}\sum _{x=0}^{Q-1}\left|x\right\rangle \left|0\right\rangle $

 $x$ 從 0 到 $Q$ − 1。所以這一個初始態是 $Q$ 個狀態的疊加。
2. 建立量子函式版本的 $f$ ( $x$ )，並且應用於上面的疊加態，得到

　
: $Q^{-1/2}\sum _{x}\left|x\right\rangle \left|f(x)\right\rangle $ .

這裡仍舊是 $Q$ 個狀態的疊加。
3. 對輸入暫存器進行量子傅立葉變換。這個變換（操作於二的冪次 —— $Q=2^{q}$ 個疊加態上面）
使用一個 $Q$ 次單位根例如 $\omega =e^{2\pi i/Q}$ 將任意給定態 $\left|x\right\rangle $ 的振幅平均分佈在所有 $Q$ 個 $\left|y\right\rangle $ 態上。另一個方法是對於每個不同的 $x$ ：

　
: $U_{QFT}\left|x\right\rangle =Q^{-1/2}\sum _{y}\omega ^{xy}\left|y\right\rangle $ 。

由此得到最終狀態：

　
: $Q^{-1}\sum _{x}\sum _{y}\omega ^{xy}\left|y\right\rangle \left|f(x)\right\rangle $ .

這是一個遠多過 $Q$ 個狀態的疊加態，但是遠低過 $Q$ 2 個。雖然在和中有 $Q$ 2 項，但只要 $x_{0}$ 和 $x$ 的值相同，態 $\left|y\right\rangle \left|f(x_{0})\right\rangle $ 就可被提出來。令

　
: $\omega =e^{2\pi i/Q}$ 為 $Q^{th}$ 的一個單位根，

　
: $r$ 為 $f$ 的週期，

　
: $x$ 0 為一個產生相同 $f$ ( $x$ ) 的 $x$ 的集裡面的最小元素（我們已經有 $x$ 0 < $r$ ），以及

　
: _b_ 在 0 到 $\lfloor (Q-x_{0}-1)/r\rfloor $ 之間使得 $x_{0}+rb<Q$ 。那麼 $\omega ^{ry}$ 則是復平面的一個單位向量（ $\omega $ 是一個單位根， $r$ 和 _y_ 是整數），而 $Q^{-1}\left|y\right\rangle \left|f(x_{0})\right\rangle $ 在最終狀態下的係數則為

　
: $\sum _{x:\,f(x)=f(x_{0})}\omega ^{xy}=\sum _{b}\omega ^{(x_{0}+rb)y}=\omega ^{x_{0}y}\sum _{b}\omega ^{rby}$ 。這一求和的每一項代表一個獲得相同結果的不同路徑，而量子干涉發生。在單位向量 $\omega ^{ryb}$ 幾乎與復平面指向同一方向（要求 $\omega ^{ry}$ 指向正實數軸）時，干涉將是相長的。
4. 進行測量。我們由輸入暫存器取得結果 _y_，由輸出暫存器取得 $f(x_{0})$ 。而既然 $f$ 是週期，對某對 _y_ 和 $f(x_{0})$ 進行測量的機率則由

　
: $\left|Q^{-1}\sum _{x:\,f(x)=f(x_{0})}\omega ^{xy}\right|^{2}=Q^{-2}\left|\sum _{b}\omega ^{(x_{0}+rb)y}\right|^{2}$

給出。分析顯示這個機率越高，單位向量 $\omega ^{ry}$ 就越接近正實數軸，或者 ${\frac {ry}{Q}}$ 越接近一個整數。除非 $r$ 是 2 的乘方，否則它不會是 $Q$ 的因子。
5. 對 ${\frac {y}{Q}}$ 進行連分數展開來計算其近似值，並生成滿足下列兩個條件的 ${\frac {c}{r'}}$ ：

　
: $A:r'<N$

　
: $B:|{\frac {y}{Q}}-{\frac {c}{r'}}|<{\frac {1}{2Q}}$

藉著滿足這一些條件， $r$ ′有很高的機率會是我們要找的週期 $r$ 。
6. 檢查 $f$ ( $x$ ) = $f$ ( $x$ + $r$ ′) $\Leftrightarrow $ $a^{r}\equiv 1{\pmod {N}}$ 。如果成功了，我們就完成了。
7. 否則，以接近 y 左右的數值作為 $r$ 的候選，或者說多取幾個 $r'$ . 如果任何候選成功了，我們就完成了。
8. 否則，回到第一步驟（也就是全部重新做一次）。

## 演算法的解釋

此演算法包含兩個部份。演算法的第一部份是將因數分解問題轉成尋找一個函式的週期，而且這部份可以用傳統方式實作。第二部份則是使用量子傅立葉變換來搜尋這個函式的週期，而且這一部份是量子加速這整個演算法的理由。

### I. 從週期得到因數

小於 _N_ 且互質於 _N_ 的整數組成一個有限大，且對乘法同餘 _N_ 的群。在步驟 3 之後，我們有一個屬於這個群的整數 _a_。既然這個群是有限的，_a_ 必有一個有限大的階 _r_, 也就是最小的正整數令

　
: $a^{r}\equiv 1\ {\mbox{mod}}\ N.\,$

因此可知，_N_ 是 _a_ r − 1 的因數。先假設我們有能力獲得 _r_，而且 _r_ 是偶數。則

　
: $a^{r}-1=(a^{r/2}-1)(a^{r/2}+1)\equiv 0\ {\mbox{mod}}\ N$

　
: $\Rightarrow N\ |(a^{r/2}-1)(a^{r/2}+1).\,$

_r_ 是令 _a_ r ≡ 1 _最小的_正整數，所以（_a_ r / 2 − 1）必定不能整除於 _N_。若（_a_ r / 2 + 1）也不整除於 _N_ 的話，則 _N_ 必定與（_a_ r / 2 − 1）或者（_a_ r / 2 + 1）有一個非顯然的公因數。

**證明：**為了簡化，我們分別用 _u_ 和 _v_ 表示（_a_ r / 2 − 1）和（_a_ r / 2 + 1）。_N_ | _uv_，故 _kN_ = _uv_（k 是某個整數）。假設 gcd (_v_, _N_) = 1：則必定存在某個整數 _m_ 和 _n_ 令 _mv_ + _nN_ = 1 (這是最大公因數的一個性質)。兩邊同乘以 _u_，我們得到 _mkN_ + _nuN_ = _u_, 所以 _N_ | _u_，從而產生矛盾（前文提到（_a_ r / 2 − 1）必定不能整除於 _N_）。故假設不成立，即 gcd (_v_, _N_) ≠ 1。用類似的方法，可以得知若（_a_ r / 2 + 1）不能整除於 _N_, gcd(_u_, _N_) ≠ 1。故得證 u 和 v 不同時與 _N_ 互質。

這給予我們一個 _N_ 的因數分解。若 _N_ 是兩個質數的乘積，則這是_唯一_可能的分解。

### II. 找尋週期

秀爾的週期尋找演算法非常倚賴量子計算機同時處於許多狀態的能力。物理學家稱呼這個特性為狀態的「疊加」。在計算函式 _f_ 的週期時，我們會同時估計這個函式的所有點。

不過，量子物理不允許我們直接取得這些資訊。測量會令觀測結果塌陷到其中一個可能的結果，並摧毀所有其他可能。如果不是因為不可複製原理，我們可以先測量 _f_(_x_) 而非測量 _x_，再製造幾個結果態的拷貝（將會是多個有著同樣的 _f_(_x_) 的態的疊加）。對這些態上的 _x_ 的測量將會給出能給出相同 _f_(_x_) 的不同的 _x_，由此推導出週期來。因為我們不能複製完全相同的量子狀態，這個方法行不通。因此在這裡我們需要小心的轉變疊加態，使其成為可以以高機率回傳正確答案的狀態。這可使用量子傅立葉變換來達成。

因此秀爾在這裡必須解決三個「實作」的問題，而且速度必須夠快，也就是可這些問題可以用量子閘個數為 $\log N$ 的多項式來實作。

1. 製造狀態的疊加。

這可以藉著對所有輸入的量子位元使用哈達瑪閘（Hadamard gate）來達成。另一個方法是使用量子傅立葉變換（如下述）。
2. 以量子變換實作函式 _f_。

要達成這件事情，秀爾使用了反覆平方以完成模的取冪變換。值得注意的是，這一個步驟比起量子傅立葉變換還難以實作，需要更多輔助的量子位元以及明顯更多的閘來完成。
3. 進行量子傅立葉變換。

利用受控旋轉閘（controlled rotation gate）和哈達瑪閘，秀爾設計了一個量子傅立葉變換的線路，只使用了 $q(q-1)/2=O((\log Q)^{2})$ 個閘（_Q_ = 2q）。

在這一些變換之後，測量會給出週期 _r_ 的近似值。為簡明起見，假設存在 _y_ 令 _yr/Q_ 是整數，則測量到 _y_ 的機率是 1（理論上）。要推導出這個，我們首先注意到對任何整數 _b_，

　
: $e^{-2\pi ibyr/Q}=1$ 。因此 _Q/r_ 的平方能告訴我們測量 _y_ 的機率，因為 _b_ 大致上取 _Q/r_ 個值，因此機率為 $1/r^{2}$ 。有 _r_ 個 _y_ 使得 _yr/Q_ 為整數， $f(x_{0})$ 也有 _r_ 種可能，所以機率總和為 1。

Note: 另一種解釋秀爾演算法的方式是將之視為是喬裝過後的量子相位估計演算法。

## 參見

* 包立矩陣
* 量子退火

## 參考資料

## 延伸閱讀