Shor 演算法
5.1 Shor演算法：古典密碼學的終結者？
1994年由Peter Shor提出的Shor演算法，是量子計算領域最具影響力的演算法，它宣告了量子電腦有能力破解當今互聯網安全的基石。
原理： Shor演算法的目標是高效地分解一個大整數 $N$。它巧妙地將這個純數學問題分為古典和量子兩個部分：
- 古典簡化： 首先，在古典電腦上，將「分解質因數」問題轉化為「求階」問題 [39, 40]。具體來說，隨機選取一個與 $N$ 互質的整數 $a$，然後去尋找 $a$ 模 $N$ 的階 $r$，即滿足 $a^r \equiv 1 \pmod{N}$ 的最小正整數。一旦找到一個偶數 $r$，且 $a^{r/2} \not\equiv -1 \pmod{N}$，那麼 $N$ 的一個因子就可以通過計算 $\text{gcd}(a^{r/2} \pm 1, N)$ 得到 [39, 41]。求階問題在古典上被認為是困難的。
- 量子求階： 這是演算法的核心，也是量子電腦發揮作用之處。求階問題等價於尋找函數 $f(x) = a^x \pmod{N}$ 的週期 $r$。這正是QPE演算法的用武之地 [40, 42]。通過構造一個酉算符 $U$ 使得 $U|y\rangle = |ay \pmod{N}\rangle$，其特徵值的相位與週期 $r$ 直接相關（形式為 $s/r$）[39]。利用QPE演算法估計出這個相位，再結合古典的連分數演算法，就能高效地從相位估計值中反推出週期 $r$ [39, 40]。
影響： Shor演算法能在多項式時間內解決大數分解和離散對數問題，而這兩個問題正是目前廣泛使用的公鑰密碼體系——如RSA和橢圓曲線密碼學（ECC）——的安全基礎 [1, 19, 40]。這意味著，一旦大規模的容錯量子電腦建成，現有的許多加密通信和數位簽名將變得不再安全。這一潛在威脅直接催生了「後量子密碼學」（Post-Quantum Cryptography, PQC）的興起，旨在開發能夠抵禦古典和量子電腦攻擊的新型古典加密演算法 [7, 15, 23]。
2.3 秀爾演算法 (Shor’s Algorithm)
秀爾演算法是彼得·秀爾於1994年提出的知名量子演算法，用於對大整數進行質因數分解:contentReference[oaicite:39]{index=39}。其意義在於，該問題對應的傳統最佳算法（比如數域篩選法）為次指數時間複雜度，而秀爾演算法能在多項式時間內完成，同時破解基於大數分解困難性的RSA等公鑰加密系統:contentReference[oaicite:40]{index=40}。秀爾演算法背後利用了量子計算對週期問題的擅長：給定欲分解的N，演算法隨機選取與N互質的數a，透過量子電路計算函數f(x)=a^x mod N的周期r，從而推導出N的非平凡因數。
秀爾演算法結合了經典與量子兩部分:contentReference[oaicite:41]{index=41}。經典部分負責一些預處理（如檢查是否為冪或偶數），而量子部分的核心是週期尋找子程序。在量子電路中，我們使用2n位元（n為N的位元長度）的量子暫存器，其中前n個qubit用於儲存指數x，後n個qubit用於儲存f(x)值。首先將前n個qubit置於|0…0⟩經Hadamard閘得到均勻疊加，後n個初始化為|1⟩（即f(0)）:contentReference[oaicite:42]{index=42}。接著構造電路實現函數f(x)的計算：對所有可能x同時計算a^x mod N並存入第二暫存器。這一步可視為執行一系列受控乘法模N的量子閘。完成後整個暫存器態為∑x|x⟩|a^x mod N⟩。
隨後，我們對第一暫存器（存放x的暫存器）執行QFT，以提取函數值中的周期信息:contentReference[oaicite:43]{index=43}。最後量測第一暫存器，得到的測量結果經過經典後處理（包括連分數分解等）即可計算出r的值。由r進一步計算出N的一個非平凡因數。如果結果不正確（比如r為奇數或得到平凡因數），則重新選取不同的a再執行一次。以足夠大的概率，秀爾演算法最終能產生正確的因數分解結果。
秀爾演算法的時間複雜度是多項式級別的。更準確地說，其主要量子步驟耗時約O((log N)2)，再考慮經典部分（模指數運算與連分數計算）的開銷，整體複雜度約為O((log N)3):contentReference[oaicite:44]{index=44}。這意味著，若N有上千比特長，量子計算可以在合理時間內完成質因數分解，而傳統計算需要極長時間:contentReference[oaicite:45]{index=45}。因此，一旦有足夠大的容錯量子電腦問世，當前廣泛使用的RSA公鑰加密體制將被攻破:contentReference[oaicite:46]{index=46}。秀爾演算法的提出極大地推動了量子計算的發展，因為它展示了量子電腦在實用問題上對經典電腦的指數級超越。
Shor 演算法與整數分解問題
Shor演算法是量子計算最具里程碑意義的演算法之一，由數學家彼得·Shor於1994年提出blog.csdn.net。它能在量子計算機上以多項式時間高效分解大整數，直接威脅傳統公鑰加密體制（如RSA）的安全性blog.csdn.net。整數分解問題在經典計算中被認為是超級多項式難度的（已知最佳演算法為次指數時間），而Shor演算法將其時間複雜度降低為多項式級別，這是量子計算對經典計算的指數級加速實例blog.csdn.net。Shor演算法針對的是：給定一個大整數 $N$，找出其非平凡因數（質因數）。其核心步驟包括兩部分： (1) 應用量子傅里葉變換（QFT）的量子相位估計程序來尋找一個與 $N$ 有關函數的週期，(2) 根據找到的週期推算出 $N$ 的因數blog.csdn.netblog.csdn.net。具體而言，Shor利用算數輔助函數 $f(a) = x^a \bmod N$（其中選取一隨機 $x < N$），該函數的周期 $r$ 與 $N$ 的因數有密切關聯：若 $r$ 為偶數且 $x^{r/2} \not\equiv -1 \pmod{N}$，則 $\gcd(x^{r/2}-1, N)$ 與 $\gcd(x^{r/2}+1, N)$ 即為 $N$ 的非平凡因數。Shor演算法利用量子並行性對 $f(a)$ 進行周期測量：它首先準備兩組量子暫存器，一組存放指數 $a$ 的疊加，另一組存放計算 $x^a \bmod N$ 的結果；然後對結果暫存器做量子傅里葉變換，經測量得到與周期 $r$ 有關的相位資訊，最後通過經典計算從相位推導出 $r$ 值blog.csdn.netblog.csdn.net。這一系列步驟的量子部分本質上實現了指數時間的平行計算（遍歷嘗試所有 $a$ 的次方），再透過傅里葉干涉濃縮出週期訊息。
Shor演算法在計算複雜度上具有革命性：它將 $N$ 位數的整數分解問題從經典的次指數（約 $\exp[(\log N)^{1/3}]$ 級別）降至 $O((\log N)^3)$ 級別edu.cn。對目前典型的RSA-2048（約617位十進制數），經典計算分解需要的時間可能超越宇宙年齡，而理論上Shor演算法在足夠大的量子計算機上幾分鐘至幾小時即可完成edu.cn。這種巨大的加速正是促使全球開始研究後量子密碼學的原因——Shor演算法證明一旦大規模可容錯量子計算機建成，當前廣泛使用的RSA和橢圓曲線密碼體制將不再安全blog.csdn.net。因此，Shor演算法不僅有學術價值，也對資訊安全構成現實挑戰。
實作進展：
Shor演算法要處理大數分解，需要相當數量的量子位元和可靠的量子邏輯閘。對一個 $n$ 位元的整數 $N$ 進行分解，大致需要 $2n$ 個量子比特（$n$ 個存指數，$n$ 個存函數值）以及數千至上百萬層量子閘操作（取決於分解數字的大小）。如此龐大的資源需求遠超當前NISQ裝置能力。截至目前，Shor演算法僅在非常小的整數上得到實驗驗證：早在2001年，IBM的NMR量子計算機成功將 $N=15$ 分解為3和5，首次展示了Shor演算法在硬體上的可行性edu.cn。之後的研究又陸續在光學量子系統、離子阱等平台上分解了 $N=21$、$N=35$ 等數字blog.creaders.net。例如，2012年美國UC Santa Barbara使用超導量子比特成功分解15，被視為「可進行因數分解的首個量子處理器」，發表於《Nature Physics》，標誌著Shor演算法硬體實現的一個里程碑edu.cn。不過，這些演示多半預先知道結果且使用了一些簡化技巧，仍屬於概念驗證範疇。例如分解21的實驗常預先假設部分已知因子來簡化電路。迄今Shor演算法在實驗中完全因數分解的最大數依然非常有限（有報導指僅21或稍大，且需要借助模擬輔助）crypto.stackexchange.com。要真正運行Shor算法來分解上千位數，需要擁有數百萬無糾錯錯誤的量子比特並執行長時間相幹演化，這在短期內無法達成。
當前瓶頸：
因此，Shor演算法的主要瓶頸在於量子硬體要求遠未達標。一方面需要足夠多的量子比特容納計算寄存器，且這些比特要維持高相干性以執行龐大的量子電路深度；另一方面，Shor演算法中的模數指數運算、量子傅里葉變換等都需要精確的兩比特閘操作，當前雜訊水準下累積的閘錯誤會完全破壞結果。另外，Shor演算法對錯誤糾正要求極高，只有引入量子錯誤更正碼，才能在數百萬層邏輯門操作下保持計算可靠。因此可以預見，在容錯量子計算實現之前，Shor演算法很難用於實際的大數分解。這也導致目前尚未出現「量子破解RSA」的事件。然而，理論上Shor算法的正確性和有效性已獲充分證明，一旦硬體成熟，其威力將即刻顯現。這給密碼學領域帶來強烈緊迫感：各國密碼專家正積極研發抗量子攻擊的新體制（如基於格問題、代數幾何碼等），以在未來量子計算機出現時保護資訊安全edu.cn。
現實意義與展望：
Shor演算法的提出從學術上證明了量子計算機在某些問題上能指數性超越經典計算機blog.csdn.net。它直接催生了「量子計算威脅下的密碼學」這一研究領域，也在一定程度上推動了政府和企業對量子計算研發的投入。儘管Shor算法暫未在大型整數上實現，但它的重要性在於提供了明確的應用目標和激勵：開發可以執行Shor算法的萬億級門操作量子計算機，相當於為量子工程設計指明了方向。未來，如果量子硬體發展到可運行Shor算法的規模，那也意味整個量子計算技術已極大成熟。在此同時，新一代後量子加密標準將取代現有RSA體系，確保數位通信在量子時代的安全。總結而言，Shor演算法象徵著量子計算對傳統計算挑戰的一大勝利，其實現僅是時間問題：伴隨技術進步，整數分解這一道「計算堡壘」最終將被量子計算攻克。
王培儒