量子計算機威脅到網路加密只是一個時間問題｜對話應用數學家Peter Shor

25年前，Peter Shor證明了如何讓量子計算變得可行，同時也表明了量子計算會如何威脅到數據；以下是《自然》對他的採訪。

原文作者：Davide Castelvecchi

上世紀 80 年代，當物理學家首次提出量子計算機的想法時，它們聽起來就像是理論上很精彩、但可能註定只能停留在論文里的概念。到了 1995 年，也就是 25 年前的 10 月，數學家Peter Shor 發表的一篇論文[1]改變了人們的看法。

應用數學家 Peter Shor 解決了量子計算領域的一個重要問題。來源：BBVA FOUNDATION。

Shor 在論文中證明了如何克服量子計算機的一個關鍵問題。量子計算機以量子比特為單位處理信息——量子比特對應經典比特，但能同時表示 0 和 1。已知量子態對雜訊非常敏感，這會造成信息丟失。Shor 提出的誤差修正技術能檢測到雜訊導致的錯誤，帶來了一種讓量子信息更抗噪的方法。

Shor 目前就職於麻省理工學院，同時也是一位出版過作品的詩人。1994 年，他第一次發現了[2]使用理論量子計算機的方法，震驚了物理學界和計算機科學界——這種方法可能有用但也令人擔憂。他寫了一種演算法，可以讓量子計算機以閃電般的速度將整數分解質因數。今天的大部分網路流量的安全性都是由基於大質數的加密技術來保證的。破解這些密碼很難，因為經典計算機分解大整數質因數的速度很慢。

如今，量子計算機已經成為現實，但它們分解超過兩位數數字的能力依然處於初級水平。但是，量子計算機威脅到網路加密只是一個時間問題。

《自然》採訪了 Shor，詢問他如何看待自己研究的影響力，以及網路安全的未來將走向何方。

Q：在你的分解質因數演算法出現前，量子計算機是否只停留在理論層面？

A：我的論文確實給了大家一種印象，就是這些計算機能做些有用的事。計算機科學家Daniel Simon在我的結果出來前，解決了他遇到的一個問題，證明了量子計算機[比普通計算機]快了好幾個指數級。但即使有了Simon的演算法，人們依然不清楚量子計算機能有什麼用。

Q：你公布這個分解質因數演算法時，人們有何反應？

剛開始，我只得到了中間結果。1994 年 4 月，我在[當時我就職的新澤西州]貝爾實驗室（Bell Labs）做了一次關於它的演講。消息傳得很快，那個周末，計算機科學家 Umesh Vazirani 給我打了個電話。他說：「我聽說你能用量子計算機分解質因數，請告訴我是如何做到的。」那時候，我其實還沒有解決分解質因數的問題。我不知道你聽說過兒童遊戲「打電話」沒有，但不知怎的，五天時間裡，我的研究結果就變成了分解質因數，因為人們都在這樣傳。在那五天里，我正好也解決了那個問題，所以我能告訴 Umesh 如何做。

我的論文還沒寫完的時候，就有各種各樣的人來問我要論文，所以我只能把還不完整的草稿先寄給他們。

Q：但是許多專家還是認為量子計算機會在完成計算前丟失信息？

有一個反對意見是說在量子力學中，如果你測量一個系統，你就會不可避免地干擾它。我證明了如5何在測量錯誤的同時不測量計算，這樣你就能糾正錯誤，而不會破壞整個計算。

在我那篇 1995 的糾錯論文發表後，一些懷疑人士也開始相信量子計算或許是可行的。

Q：糾錯依賴「物理」和「邏輯」量子比特。這兩者有什麼差別？

為量子計算機寫演算法時，假設的是量子比特是無噪的，演算法中描述的這些無噪量子比特就是邏輯量子比特。實際上量子計算機中沒有無噪量子比特，事實是，如果我們在不進行任何降噪的情況下運行演算法，幾乎必定會出現錯誤。

物理量子比特是量子計算機的其中一種雜訊量子比特。如果要在不出錯的情況下運行演算法，我們就要利用物理量子比特編碼邏輯量子比特，使用一種量子糾錯碼。據我們所知，實現這一步的最好做法要求相當高——每個邏輯量子比特都需要許多物理量子比特。

要計算出這項技術需要多少量子比特是一項非常複雜的工作。如果你想用表面碼（目前最好的候選對象）構建一個量子計算機，每個邏輯量子比特大約需要 100 個物理量子比特或更多。

Q：2019 年，谷歌用 54 量子比特的量子計算機解決了一個經典計算機幾乎不可能完成的任務，這也是對「量子優越性」的首次演示。您對此有何評價？

它肯定是一個里程碑。它表明了量子計算機可以比經典計算機做得更好——至少是在一些人為設計的問題上。谷歌確實進行了一些宣傳。但他們也有一台非常值得稱道的量子計算機。但這個計算機依然需要改進，才能做出有意思的事來。還有初創公司 IonQ，他們看起來好像能構建一個在某種程度上超過谷歌或IBM的量子計算機。

Q：如果量子計算機能做大數質因數分解，它們就能破解「RSA」——無處不在的網路加密系統。

是的，但是最先破解 RSA 的人不是來自 NSA（美國國家安全局），就是來自其他大型機構。這些計算機一開始會很慢。比如，如果你有一台只能一小時破解一個 RSA 密鑰的計算機，那麼任何不屬於優先事項或國家安全風險的東西都不會被破解。相比看你的郵件，NSA的量子計算機有更重要的事情要做。

Q：有沒有能取代 RSA 的密碼系統，即使在量子計算機時代（「後量子密碼」）也是安全的？

我認為已經有能取代 RSA 的後量子密碼系統了。RSA 不是現在的大問題，現在的大問題是還有其他方法可以破壞網路安全，比如惡意編程的軟體、病毒、向並非絕對誠實的一方發送信息等。我認為用安全的後量子密碼系統取代 RSA 的唯一阻礙是意志和編程時間。我認為我們已經知道要如何做到這一點，只是不清楚是否能及時做到。

Q：我們是否有被突然襲擊的風險？

是的，人們已經為解決千年蟲問題（Year 2000）投入了大量精力。你需要付出大量努力才能過渡到後量子時代。如果我們等得太久，就太遲了。

參考文獻：

1. Shor, P. W.?Phys. Rev. A?52, R2493(R) (1995).

2. Shor, P. W.?Proc. 35th Annual Symp. Found. Comp. Sci.?124–134 (1994).

版權聲明：

2020?Springer Nature Limited.?All Rights Reserved

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！