簡介?
秀爾算法（Shor's Algorithm），以數學家彼得·秀爾命名，是一個在1994年發現的，針對整數分解這題目的的量子算法 (在量子計算機上面運作的算法 )。比較不正式的說，它解決題目如下：給定一個整數N，找出他的質因子。
在一個量子計算機上面，要分解整數N, 秀爾算法的運作需要多項式時間 (時間是log N的某個多項式這么長,log N在這裡的意義是輸入的檔案長度)。 更精確的說，這個算法花費O((log N))的時間，展示出質因子分解問題可以使用量子計算機以多項式時間解出，因此在複雜度類 BQP裡面。這比起傳統已知最快的因子分解算法, 普通數域篩選法, 其花費次指數時間 -- 大約O(e (log log N))，還要快了一個指數的差異。
秀爾算法非常重要，因為它代表使用量子計算機的話，我們可以用來破解已被廣泛使用的公開密鑰加密方法，也就是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 mod N。換句話說，找出a在裡面的目 r，或者最小的正整數r令 f(x + r) = f(x)。
5.若r是奇數，回到第一步。
6.若a^(r/2) ≡-1 (mod N), 回到第一步。
7. gcd(a^(r/2)? ± 1, N) 是N非平凡的一個因子。分解完成。
量子部份：周期尋找副函式(Period-finding subroutine)
這個算法使用的量子線路是為了在給定一個固定常數 N 以及一個任意常數 a之下，找出f(x) = a^x mod N所設定的。給定N, 找出Q = 2^q且合乎N^2≤Q≤2N^2??(這同時表示Q / r > N)。輸入和輸出量子位元暫存器需要儲存從0到Q-1所有值的疊加態，因此分別需要q個量子位元。這裡使用看起來比所需的數量還要更多一倍的量子位元，保證了即使周期r的大小逼近N/2，也至少有N個不同的x會產生相同的 f(x)。
算法如下：
1.將暫存器初始化成
x從0到Q - 1。所以這一個初始態是Q 個狀態的疊加。
2.建立量子函式版本的f(x) ，並且套用於上面的疊加態, 得到
這裡仍舊是Q個狀態的疊加。
3. 對輸入暫存器進行 量子傅立葉轉換。這個轉換（操作於二的冪次即Q = 2^q個疊加態上面）使用一個Qth 單位根 例如 ω = e^(2pi*i/Q)將任意給定態|x>的振幅平均分布在所有Q個態|y>上。另一個方法是對於每個不同的|x>：
由此得到最終狀態：
這是一個遠多過Q個狀態的疊加態，但是遠低過Q^2個。雖然在和中有Q^2項，但只要x0 和 x的值相同，態|y>f(x0)就可被提出來。令
ω = e^(2pi*i/Q)? 為 Qth 的一個單位根，
r 為 f 的周期，
x0為一個產生相同 f(x) 的 x 的集裡面的最小元素（我們已經有x0 < r），以及
b在0到[(Q-x0-1)/r]之間使得x0 + rb < Q。
那么ω^ry則是複平面的一個單位向量（ω是一個單位根，r 和 y 是整數），而?Q^(-1)|y>|f(x0)>在最終狀態下的係數則為?
這一求和的每一項代表一個獲得相同結果的不同路徑，而量子干涉發生。在單位向量ω^ryb幾乎與複平面指向同一方向（要求ω^ry指向正實數軸）時，干涉將是相長的。
4.進行測量。我們由輸入暫存器取得結果 y，由輸出暫存器取得f(x0)。而既然f 是周期，對某對y和 f(x0)進行測量的機率則由
給出。分析顯示這個機率越高，單位向量ω^ry就越接近正實數軸，或者yr/Q就越接近一個整數。除非r是2的乘方，否則它不會是Q的因子。
5.對y/Q進行連分數展開來計算其近似值，並生成滿足下列兩個條件的c/r′：
A: r′<N
B: |y/Q - c/r′| < 1/2Q
借著滿足這一些條件，r′ 有很高的機率會是我們要找的周期r 。
6. 檢查f(x) = f(x + r′) ，由此可得
?
如果成功了，我們就完成了。
7.否則，以接近y左右的數值作為r的候選，或者說多取幾個r′. 如果任何候選成功了，我們就完成了。
8.否則，回到第一步驟(也就是全部重新作一次)。?
