數(shù)學家Peter Shor：量子計算機威脅到網(wǎng)絡(luò)加密，只是時間問題
撰文 | Davide Castelvecchi
● ● ●
上世紀80年代，當物理學家首次提出量子計算機的想法時，它們聽起來就像是理論上很精彩、但可能注定只能停留在論文里的概念。到了1995年，也就是25年前的10月，數(shù)學家 Peter Shor 發(fā)表的一篇論文 [1] 改變了人們的看法。
Shor在論文中證明了如何克服量子計算機的一個關(guān)鍵問題。量子計算機以量子比特為單位處理信息——量子比特對應(yīng)經(jīng)典比特，但能同時表示0和1。已知量子態(tài)對噪聲非常敏感，這會造成信息丟失。Shor提出的誤差修正技術(shù)能檢測到噪聲導致的錯誤，帶來了一種讓量子信息更抗噪的方法。
Shor目前就職于麻省理工學院，同時也是一位出版過作品的詩人。1994年，他第一次發(fā)現(xiàn)了 [2] 使用理論量子計算機的方法，震驚了物理學界和計算機科學界——這種方法可能有用但也令人擔憂。他寫了一種算法，可以讓量子計算機以閃電般的速度將整數(shù)分解質(zhì)因數(shù)。今天的大部分網(wǎng)絡(luò)流量的安全性都是由基于大質(zhì)數(shù)的加密技術(shù)來保證的。破解這些密碼很難，因為經(jīng)典計算機分解大整數(shù)質(zhì)因數(shù)的速度很慢。
如今，量子計算機已經(jīng)成為現(xiàn)實，但它們分解超過兩位數(shù)數(shù)字的能力依然處于初級水平。但是，量子計算機威脅到網(wǎng)絡(luò)加密只是一個時間問題。
最近，Shor在接受《自然》雜志采訪時，就如何看待自己研究的影響力，網(wǎng)絡(luò)安全的未來將走向何方等分享了自己的看法。
在你的分解質(zhì)因數(shù)算法出現(xiàn)前，量子計算機是否只停留在理論層面？
我的論文確實給了大家一種印象，就是這些計算機能做些有用的事。計算機科學家 Daniel Simon 在我的結(jié)果出來前，解決了他遇到的一個問題，證明了量子計算機（比普通計算機）快了好幾個指數(shù)級。但即使有了 Simon 的算法，人們依然不清楚量子計算機能有什么用。
你公布這個分解質(zhì)因數(shù)算法時，人們有何反應(yīng)？
剛開始，我只得到了中間結(jié)果。1994年4月，我在[當時我就職的新澤西州]貝爾實驗室（Bell Labs）做了一次關(guān)于它的演講。消息傳得很快，那個周末，計算機科學家 Umesh Vazirani 給我打了個電話。他說：“我聽說你能用量子計算機分解質(zhì)因數(shù)，請告訴我是如何做到的?！?那時候，我其實還沒有解決分解質(zhì)因數(shù)的問題。我不知道你聽說過兒童游戲 “打電話” 沒有，但不知怎的，五天時間里，我的研究結(jié)果就變成了分解質(zhì)因數(shù)，因為人們都在這樣傳。在那五天里，我正好也解決了那個問題，所以我能告訴Umesh如何做。
我的論文還沒寫完的時候，就有各種各樣的人來問我要論文，所以我只能把還不完整的草稿先寄給他們。
但是許多專家還是認為量子計算機會在完成計算前丟失信息？
有一個反對意見是說在量子力學中，如果你測量一個系統(tǒng)，你就會不可避免地干擾它。我證明了如何在測量錯誤的同時不測量計算，這樣你就能糾正錯誤，而不會破壞整個計算。
在我那篇1995的糾錯論文發(fā)表后，一些懷疑人士也開始相信量子計算或許是可行的。
糾錯依賴 “物理” 和 “邏輯” 量子比特。這兩者有什么差別？
為量子計算機寫算法時，假設(shè)的是量子比特是無噪的，算法中描述的這些無噪量子比特就是邏輯量子比特。實際上量子計算機中沒有無噪量子比特，事實是，如果我們在不進行任何降噪的情況下運行算法，幾乎必定會出現(xiàn)錯誤。
物理量子比特是量子計算機的其中一種噪聲量子比特。如果要在不出錯的情況下運行算法，我們就要利用物理量子比特編碼邏輯量子比特，使用一種量子糾錯碼。據(jù)我們所知，實現(xiàn)這一步的最好做法要求相當高—— 每個邏輯量子比特都需要許多物理量子比特。
要計算出這項技術(shù)需要多少量子比特是一項非常復(fù)雜的工作。如果你想用表面碼（目前最好的候選對象）構(gòu)建一個量子計算機，每個邏輯量子比特大約需要100個物理量子比特或更多。
2019年，谷歌用54量子比特的量子計算機解決了一個經(jīng)典計算機幾乎不可能完成的任務(wù)，這也是對 “量子優(yōu)越性” 的首次演示。您對此有何評價？
它肯定是一個里程碑。它表明了量子計算機可以比經(jīng)典計算機做得更好—— 至少是在一些人為設(shè)計的問題上。谷歌確實進行了一些宣傳。但他們也有一臺非常值得稱道的量子計算機。但這個計算機依然需要改進，才能做出有意思的事來。還有初創(chuàng)公司IonQ，他們看起來好像能構(gòu)建一個在某種程度上超過谷歌或IBM的量子計算機。
如果量子計算機能做大數(shù)質(zhì)因數(shù)分解，它們就能破解 “RSA” ——無處不在的網(wǎng)絡(luò)加密系統(tǒng)。
是的，但是最先破解RSA的人不是來自NSA（美國國家安全局），就是來自其他大型機構(gòu)。這些計算機一開始會很慢。比如，如果你有一臺只能一小時破解一個RSA密鑰的計算機，那么任何不屬于優(yōu)先事項或國家安全風險的東西都不會被破解。相比看你的郵件，NSA的量子計算機有更重要的事情要做。
有沒有能取代RSA的密碼系統(tǒng)，即使在量子計算機時代（“后量子密碼”）也是安全的？
我認為已經(jīng)有能取代RSA的后量子密碼系統(tǒng)了。RSA不是現(xiàn)在的大問題，現(xiàn)在的大問題是還有其他方法可以破壞網(wǎng)絡(luò)安全，比如惡意編程的軟件、病毒、向并非絕對誠實的一方發(fā)送信息等。我認為用安全的后量子密碼系統(tǒng)取代RSA的唯一阻礙是意志和編程時間。我認為我們已經(jīng)知道要如何做到這一點，只是不清楚是否能及時做到。
我們是否有被突然襲擊的風險？
是的，人們已經(jīng)為解決千年蟲問題（Year 2000）投入了大量精力。你需要付出大量努力才能過渡到后量子時代。如果我們等得太久，就太遲了。
制版編輯 | 盧卡斯
