量子計算，平行宇宙破解你的密碼！

本文出自《真實世界的脈絡：平行宇宙及其寓意（第2版）》，有刪改。

關注微信：DuoDaaMath每天獲得更多數學趣文

對於通用量子計算機的全部本領中包含的某些環境，用傳統的方法營造它們是難解的，這一事實說明一些純數學計算類也必定變得易解了。因為如伽利略所說，物理定律是用數學語言表達的，營造一個環境相當於計算一定的數學函數。的確，現在已經發現許多數學任務可以用量子計算高效地完成，而用所有已知的傳統方法都是難解的。最引人注目的一個就是對大的自然數進行因數分解。該方法稱為肖演算法，由貝爾實驗室的彼得·肖在1994年發現。

肖演算法極其簡單，對硬體的要求比通用量子計算機簡單得多。因此，很可能量子因數分解引擎製造成功會遠比量子計算技術全面可行化要早得多。這對於密碼學（關於通信安全和信息認證的科學）具有重大意義。現實中的通信網路可以是全球化的，具有龐大的、持續變化的用戶群，其通信模式不可預期。要求每一對用戶事先物理地交換機密的密鑰以備後來彼此通信而無需害怕竊聽者，這是不切實際的。公鑰密碼學是一種在收發雙方還沒有約定任何機密信息時發送機密信息的方法。已知的最安全的公鑰密碼手段依賴於大數分解問題的難解性。該方法稱為RSA密碼體制，以紀念羅納德·李維斯特、阿迪·沙米爾和倫納德·阿德爾曼，他們丁1978年首次提出這一方法。它依賴於一個數學過程，用一個大數（比如250位）作為密鑰給消息編碼。接收方可以隨意把該密鑰公開，因為任何用它編碼的消息只能在知道了那個數的因子以後才可以解碼。於是，我（原作者）可以選擇兩個125位的素數並使它們保密，但是把它們乘起來，讓250位的乘積公開。任何人可以用這個數作為密鑰給我發消息，但是只有我能夠讀消息，因為只有我知道秘密因子。

我講過，用傳統方法分解250位數是不實際的，但是運行肖演算法的量子因數分解引擎可以在僅僅幾千步算術運算內完成，這只需要幾分鐘。所以，任何能使用這種機器的人都能夠輕易地閱讀任何竊聽到的用RSA體制加密的消息。

密碼員選擇再大的數字作為密鑰也沒有用，因為肖演算法需要的資源只隨著待分解數字的長度緩慢地增長。在量子計算理論中，因數分解是非常易解的。有人認為，由於存在一定程度的脫散，可以分解的數字的長度會有一個實際的限制，但是還不知道在技術上可達到的脫散率有沒有下限。所以，我們只能認為未來的某一天，在現在還不能預測的某個時候，任何給定密鑰長度的RSA密碼體制都會變得不安全。在一定意義上，甚至現在也不安全了。因為任何人或任何組織現在可以記錄下用RSA加密的消息，一直等到他們購買了脫散率足夠低的量子因數分解引擎，就可以對消息解碼了。這種事情可能幾百年都不會發生，或者可能在僅僅幾十年甚至更短時間內就發生了，誰知道呢。但是對於原先RSA體制完美的安全性，現在只能指望這種事情在相當長時期內不會發生了。

當量子因數分解引擎分解250位數字的時候，相干宇宙的數目會達到10⁵⁰⁰量級，即10的500次方。這一令人驚愕的巨大數目是肖演算法把因數分解變得易解的原因。我講過，該演算法只需要幾千步算術運算，我當然指的是對答案有貢獻的每一個宇宙中有幾千步運算。所有計算是在不同的宇宙中並行完成的，並通過相干分享結果。

（圖片來自網路）

你可能感到奇怪，我們怎麼能說服我們在10⁵⁰⁰多個寧宙中的副本和我們一起開始干分解因數的工作呢？他們對自己的計算機沒有別的使用安排嗎？不，無需說服。初始時肖演算法僅僅在一組彼此相同的宇宙中操作，僅僅在分解因數引擎範圍內使它們分化。所以，在我們指定了待分解的數字、等待答案算出來的時候，在所有相干寧宙中是一樣的。毫無疑問，存在許多其他寧宙，其中的我們編製了不同的數字，或者根本沒有造出分解因數引擎，但是那些宇宙與我們的宇宙在太多的變數上不同，或更準確地說，在那些肖演算法程序沒有使它們以正確方式相互作用的變數上不同，所以不與我們的宇宙發生干涉。

從邏輯上講，複雜量子計算的可能性無助於解決不可回答的問題，但是它的確產生了心理影響。對於肖演算法，論述已經寫得很長。對那些仍然堅持單一宇宙世界觀的人，我提出這一挑戰：請解釋肖演算法的工作原理。我要求的不僅僅是預言它能夠有效工作，這不過是求解幾個沒有爭議的方程而已，我要求的是給出解釋。當肖演算法已經分解了一個數，使用的計算資源大約是可見存在的計算資源的10⁵⁰⁰倍的時候，這個數是在哪裡被分解出來的？在整個可見的宇宙中只有大約10⁸⁰個原子，與10⁵⁰⁰相比只是個零頭。所以，如果可見的宇宙是物理實在的全部，那麼物理實在所包含的資源將遠遠不足以分解這麼大一個數。那麼是誰分解了它？計算是如何以及在哪裡完成的？

我一直在討論的是量子計算機能夠比現有的機器更快地求解傳統類型的數學問題。但是存在另一類計算任務，傳統計算機根本不能完成它，而量子計算機則是有希望的。由於不可思議的巧合，首批發現的這類問題之一也與公鑰密碼學有關。這一次不是破譯現存的密碼體制，而是實現一個新的、絕對安全的量子密碼系統。1989年，在紐約約克鎮高地IBM研究所，在理論家查爾斯·班尼特的辦公室里，建成了第一台能夠運轉的量子計算機。這是一台專用量子計算機，由一對量子密碼設備組成，由班尼特和蒙特利爾大學的吉勒斯·布拉薩德設計。它是第一台曾經完成過圖靈機所不能完成的非平凡計算的機器。

在班尼特和布拉薩德的量子密碼系統中，消息被編碼在激光器發出的一個個光子的狀態中。雖然傳送一條消息需要許多光子（每比特一個光子，外加浪費在各種無效工作中的許多光子），但是可以用現有的技術造出這台機器，因為它一次只需在一個光子上執行量子計算。系統的安全性不是基於難解性（不論是傳統的還是量子的難解性），而是直接基於量子干涉的性質：正是這才使它具有傳統方法所不能獲得的絕對安全性。無論是哪種計算機，無論做多少計算，無論算幾百萬年還是幾萬億年，都無助於竊聽者偷聽到量子加密的消息，因為如果人們通過有干涉效應的媒介通信，那麼他們就能夠發覺竊聽者。根據經典物理，沒有辦法能夠防止已經接觸到通信媒介（如電話線）的竊聽者安裝被動偵聽裝置。但是，我解釋過，如果有人測量了一個量子系統，那麼他就改變了以後的干涉性質。通信協議就依靠這一效應。通信雙方有效地建立起反覆的干涉實驗，協調他們在公共信道上的行為。只有當干涉通過了檢查，證明沒有竊聽者，他們才繼續下一階段的協議，這時才用一些傳送的信息作為密鑰。在最壞情況下，堅持不懈的竊聽者可能會完全阻斷通信（當然，切斷電話線更容易達到目的）。但是對於閱讀消息來說，只有指定的接收方才能讀到，而且這是由物理定律保證的。

（圖片來自網路）

因為量子密碼術依賴於操縱單個光子，所以它受到很大的局限。成功接收到的每一個光子負載1比特消息，必須設法完整地從發送方傳送到接收方。但是所有傳送方法都有損耗，如果損耗太大，消息就傳達不到接受方了。建立中繼站（在現有的通信系統中用來彌補損耗）會危及安全性，因為竊聽者可以監聽進入中繼站的信息而不會被發覺。現有的最好的量子密碼系統採用光纖，能傳達大約10千米的範圍。這足以給諸如城市的金融區這樣的地方提供絕對安全的內部通信網。市場化的系統可能為期不遠了，但是為了一般地解決公鑰密碼問題（如全球通信），還需要進一步發展量子密碼學。

量子計算領域的實驗和理論研究正在世界範圍內加速進行，甚至更有希望的實現量子計算機的新技術已經提出，具有超過傳統計算的各種優點的新型量子計算正在持續不斷地被發現、被分析。我感到所有這些發展都很振奮人心，我相信它們中的某些發展會產生技術碩果。但就本書而言，那些是枝節問題了。從基礎科學角度看，量子計算多麼有用無關緊要，我們的第一台通用量子計算機是下星期建成還是幾百年後建成，還是永遠也建不成，這都無關緊要。無論怎樣，對於那些尋求對真實世界的基本理解的人們來說，量子計算理論必定成為他們的世界觀的不可或缺的組成部分。通過量子計算機的理論研究，我們可以發現而且正在發現關於物理定律、通用性以及真實世界結構的幾個表面無關的解釋之間的內在聯繫。

術語

量子計算：需要量子力學過程，尤其是干涉效應的計算。換句話說，是通過平行宇宙間的協作來完成的計算。

指數計算：輸入每增加一位數字，所需資源（如時間）增加大約常數倍的計算。

易解/難解：（粗略但管用的規則）：如果完成計算需要的資源不隨著輸入數的位數指數地增加，那麼該計算任務被認為是易解的。

混沌：大多數經典系統運動的不穩定性。系統的兩個初始狀態的微小差異結果導致兩條運動軌跡的差異呈指數增長。但是真實世界遵循量子物理，而不是經典物理。混沌造成的不可預期性一般都被相同宇宙變為不同宇宙的過程中所造成的量子不確定性所淹沒。

通用量子計算機：能夠完成任何其他量子計算機所能完成的計算，營造任何有限的、物理上可能的虛擬現實環境的計算機。

量子密碼術：能夠被量子計算機執行，而不能被傳統計算機執行的任何形式的密碼術。

專用量子計算機：非通用的量子計算機，如量子密碼設備和量子因數分解引擎。

脫散：如果量子計算在不同宇宙中的不同分支對環境的影響不同，那麼干涉作用會被削弱，計算可能失敗。脫散是實際實現更強大量子計算機的主要障礙。

本文轉自公眾號中科院物理所(cas-iop)

請您繼續閱讀更多來自 哆嗒數學網 的精彩文章:

※平行宇宙會有相同的你 解密平行宇宙雙胞胎
※從量子糾纏到量子計算機，未來的某一時刻人類或許解開宇宙的起源
※平行宇宙真的存在嗎？如何進入平行宇宙？
※宇宙最讓人揪心未解之謎：平行宇宙蟲洞存在嗎？
※你能穿越平行宇宙嗎？
※平行宇宙一直存在，但想進平行宇宙太困難
※平行宇宙一直存在，但想進入平行宇宙太困難
※未解謎團！靈魂能夠穿越平行宇宙？
※引力波或是發現平行宇宙的關鍵，不過並不是你想的平行宇宙！
※霍金：掉入黑洞可能穿越到平行宇宙｜平行宇宙是啥？
※未解之謎：宇宙量子泡沫存在嗎？
※平行宇宙真的存在嗎？令人難以捉摸
※要理解宇宙，先理解計算機
※平行宇宙真的存嗎？10種證據證明平行宇宙可能真的存在！
※平行宇宙會是什麼樣子？
※平行宇宙能拯救我們嗎？
※宇宙是一個計算機程序嗎？可以把宇宙放到一塊硬碟上嗎？
※你知道平行宇宙嗎？
※如果宇宙不止一個，那平行宇宙是怎樣子的呢？