從 Shor's 算法到邏輯比特：一條難以逾越的鴻溝
文｜徐令予
在近三十年的科技敘事中，量子計算的能力被賦予了某種“神話色彩”。其中流傳最廣的斷言莫過於：量子計算機一旦問世，現有的 RSA 等公鑰密碼體係將瞬間土崩瓦解。
這一判斷並非空穴來風。Shor's 算法在理論上確實表明，整數的質因數分解可以在量子計算框架下高效完成，嚴重威脅公鑰密碼 RSA 的安全。然而，從“理論上可行”到“現實中可為”，中間橫亙著一條極其深邃的鴻溝。
需要明確的是，本文的目的並非全盤否定量子計算。事實上，在模擬量子係統、尋找新型材料或優化特定算法等特殊領域，量子計算已經並正在展現其獨特的潛力。然而，一個耐人尋味的現實是：作為量子計算數十年來最引人注目的“賣點”以及爭取研發經費的最大旗幟——破解公鑰密碼——在實驗層麵卻幾乎交出了一張白卷。這種理論上的“降維打擊”與現實中的“寸步難行”之間形成的巨大反差，正是我們審視這一領域時最需要保持冷靜的地方。
本文試圖把這一問題拆解清楚。首先說明 RSA 的安全性究竟建立在什麽基礎之上；其次解釋Shor's 算法到底改變了什麽；然後回到實驗現實，看看三十年來量子計算在整數質因數分解上有何進展；最後將問題歸結到一個更根本的層麵：是否能夠構建有足夠數量的邏輯量子比特，去支撐真正可擴展的量子計算。
一、公鑰密碼 RSA 安全性的基礎
RSA 公鑰密碼的安全性，根植於一個極簡的數學事實：將兩個大素數相乘很容易，但要把它們的乘積重新分解開，卻極其困難。這種“正向容易、反向很難”的計算不對稱性是 RSA 算法的核心。
RSA 的基本思路其實並不複雜。先選兩個很大的素數 (p) 和 (q)，把它們相乘得到一個大整數(N=pq)。這個乘法很容易做，但反過來，如果隻把 (N) 交給別人，讓別人重新找出當初那兩個素數 (p) 和 (q)，事情就會變得極其困難。
在 RSA 中，公鑰裏最核心的參數之一，就是這個大整數 (N)。公鑰可以公開，任何人都能看到它；但私鑰的生成卻離不開 (p) 和 (q) 這兩個素數。也就是說，誰如果能把 (N) 分解開，誰就有可能進一步推出私鑰；誰分解不開，誰就隻能看到公鑰，卻推不出私鑰。
與此同時，RSA 的設計保證：用公鑰加密的信息，隻能由對應的私鑰才能解密。因此，隻要無法從公鑰推出私鑰，加密後的信息就無法被解讀，其安全性也就得到了保障。
因此，“質因數分解困難”並不隻是一個數學問題，它就是 RSA 密碼安全性的根基。
可以先看一個簡單的例子。如果 (N=21)，幾乎任何人都能一眼看出：
21 = 3 × 7 。也就是說，這樣的“公鑰”根本藏不住任何東西，因為它太容易被拆開了。
但 RSA 真正使用的並不是 21 這種小數，而是長達 1024 bit、2048 bit，甚至更長的大整數。隨著 (N) 的位數增加，把它分解成兩個素數的難度會上升得非常快。
到目前為止，人類公開完成的最大整數分解，大約是 829 bit 的 RSA-250。那已經需要國際團隊動用大量計算資源；如果把這些計算量折算成一台單個處理器來做，大約要連續運行幾千年[1]。更重要的是，這類計算並不能靠簡單地堆處理器來獲得理想的並行加速。
而這還不到 1024 bit，對於今天廣泛使用的 2048 bit，難度會再躍升好幾個數量級，這是一個在現實世界難以完成的計算任務。所以，RSA 這類公鑰密碼的安全性，本質上是一種基於計算複雜性的現實安全。
二、Shor's 算法到底改變了什麽
1995 年，Shor's 算法的提出，第一次從根本上動搖了 RSA 公鑰密碼安全的基礎。
它的意義，並不是“破解了 RSA”，而在於改變了人們對這個問題的認知：質因數分解之所以在現實中幾乎不可行，並不完全是問題本身的原因，而是與我們所使用的計算方式有關。隨著數字位數增大，質因數分解在經典計算機上計算量迅速增長而變得不可行；而在量子計算的框架下，它在原理上可以在多項式時間內完成。大致估算，原本需要數千年才能破解的 RSA 密碼，有可能在數天內被量子計算機破解。
從實現機製上看，Shor's 算法並不是直接去嚐試分解整數，而是把問題轉化為一個“尋找周期”的問題。一旦這個周期被找到，原來的分解問題就可以被還原出來。關鍵在於，這個周期隱藏在一個巨大的數值結構之中，在經典計算機上難以高效提取；而在量子計算中，可以利用疊加態同時處理大量可能性，並通過 Quantum Fourier Transform 將其中的周期結構迅速顯現出來。
需要強調的是，傅裏葉變換本身並不是量子獨有的，經典計算機同樣可以高效完成類似計算；真正的區別在於，量子計算能夠在疊加態中同時處理指數規模的數據，並在一次計算過程中提取其中的整體結構。這一點，是經典計算無法做到的。
換言之，Shor's 算法並不是找到了一種更高效的經典算法來破解 RSA，而是徹底改變了思路：如果換一種計算機器，原本“幾乎算不動”的問題，其計算難度可以發生本質改變。如果存在一台足夠強大的量子計算機，那麽 RSA 在原理上將不再安全。
但這個結論隱藏著一個極其關鍵、同時也最容易被忽略的前提：這台計算機必須是可以運行Shor's 算法的大規模、穩定、可擴展的量子計算係統。離開了這樣的前提，Shor's 算法就隻是一種優美的數學理論，它不會有任何實用價值。
因此，從 Shor's 算法提出後，構建相應的量子計算係統就成了破解 RSA 密碼的關鍵。
三、破解 RSA 的實驗結果令人十分失望
自1995年起，世界多國的大學和科研機構在量子計算機的研發中投入了大量的精力和時間，為了破解 RSA 可謂不惜一切代價。但是理想很豐滿，現實很骨感。
近三十年來，量子計算在“分解質因數”上始終無法突破 21=3*7 。相關論文和實驗報告中常被提到成功“分解 15”和“分解 21”，雖然這些結果顯得非常寒酸，但背後的真相更為不堪。因為這類實驗通常依賴針對特定數字的高度定製化電路、問題特殊化、編譯優化，離“輸入任意一個整數，通用地執行 Shor's 算法並得到質因子”還有本質距離。
破解 21都做不到，那麽破解 2048 位RSA 要分解一個多大的數字呢？看看下麵的圖片就能明白什麽叫異想天開了。
為什麽連破解 N = 21 都如此困難？直覺誤區是 21 隻有 5bit，應該很容易被破解。但實際難點在於：Shor's 算法需要實施可逆模運算、量子傅裏葉變換和一整套受控操作，所以必須有一組可以長期保持狀態、能夠反複操作的量子比特。
量子比特有點像經典計算機 CPU 中的寄存器，是所有運算繞不開的地方。沒有一組寄存器，再複雜的程序也無法運行；沒有一組穩定可靠的量子比特，Shor's 量子算法寸步難行。即使破解 N=21，理論上至少需要約 10–15 個穩定可靠的量子比特，但實際上能有個位數的穩定可靠量子比特都是難於上青天！
盡管媒體經常報道，“某某機構已經做出幾十個、上百個量子比特”，但它們都不是穩定可靠的量子比特，它們離運行 Shor's 算法的要求差之甚遠。破解 RSA 密碼困難重重，缺乏足夠數量合格的量子比特始終是問題的重中之重！
四、噪聲是邏輯量子比特的天敵
現實中的量子比特非常不穩定，它們會不斷受到環境幹擾，原有的量子狀態會迅速退相幹，因而就無法像經典寄存器那樣直接作為可靠的運算單元使用。為此，人們引入了 Quantum Error Correction 的概念：通過把大量物理量子比特組合在一起，構造出一個在計算過程中能夠維持其狀態的“有效比特”，這就是所謂的邏輯量子比特 （logical qubits）。
這正是量子誤差糾正的基本思想：用大量物理比特組織成一個邏輯比特，並在整個計算過程中持續進行糾錯操作，使這個邏輯比特在統計意義上保持穩定。
從理論上看，這條路是可行的。所謂的“閾值定理”表明，隻要單次操作的錯誤率低於某個閾值，就可以通過不斷增加冗餘，把邏輯錯誤率壓低到任意小，從而支持任意規模的計算。也正因為如此，很多人認為，量子計算的問題隻是工程問題，而不是原理問題。
但關鍵在於，這一結論依賴一組非常強的前提：噪聲必須近似局部、相互獨立，誤差率不能隨著係統規模擴大而顯著上升，糾錯過程本身也必須足夠可靠。這些條件在數學模型中成立，但在真實物理係統中，卻很難完全滿足。
實驗結果表明：一方麵，隨著糾錯規模的增加，確實可以在一定範圍內降低邏輯錯誤率，這說明糾錯機製本身是有效的；但另一方麵，一些更難處理的噪聲開始顯現出來，例如跨多個比特的相關錯誤、偶發但一次性影響大量比特的突發錯誤，以及測量與控製過程中引入的係統性誤差。
於是，一個根本性的矛盾浮現出來：為了得到更穩定的邏輯比特，必須引入更多的物理比特和更多的操作；但係統越複雜，新的噪聲來源也越多，糾錯本身就變得越來越困難。從這個角度看，邏輯量子比特之所以難以實現，並不僅僅是因為“技術還不夠成熟”，而是因為它陷進了需要不斷對抗變幻莫測的噪聲的困境之中。
結語
公鑰密碼 RSA 的安全基礎是大整數質因數分解。近三十年來，量子計算在分解質因數上始終無法突破 21=3*7 ，試圖破解2048位的RSA密碼根本無從談起。
量子計算破解 RSA 密碼，在數學上已然成真，在實驗中步履維艱，而在工程上則仍是空中樓閣。這場爭論的核心命題，早已超越了 Shor's 算法本身的有效性，而聚焦於一個更為本質的拷問：大規模容錯量子計算，究竟能否在真實物理世界中實現。
注釋
[1] 2020 年，國際團隊完成了 RSA-250（829 bit）的分解。公開資料通常將其總計算量表示為約 2700 CPU 核心年。正文中將其換算為“單個處理器運行幾千年”，隻是為了幫助讀者直觀理解規模。整數分解所用的數域篩法雖然可以有某種程度的並行計算，但並不能實現理想的線性加速，關鍵步驟還受到內存與通信開銷的限製，因此不可能做到“處理器多一萬倍，時間就縮短一萬倍”。
徐令予 作於美國南加州 （2024年 4月21日）
