｜量客江湖系列01｜破RSA大盜——Peter Shor
20世紀80年代，物理學家們首次提出量子計算機的構思時，聽起來十分樂觀，但只能通過文字的方式來呈現。
後來在1995年，也就是25年前的上個月，應用數學家Peter Shor發表了一篇論文，改變了當時的一切。
圖1｜Peter Shor（來源：TQD）
Peter Shor的論文
Shor的論文展示了量子計算機是如何克服一個關鍵問題的。這些機器將以量子比特的形式處理信息，量子比特是普通比特的量子版本，可以同時處理0和1。
但衆所周知，量子態易受到噪音的影響，從而導致信息丟失。他的糾錯技術（用於檢測噪聲引起的錯誤）展示瞭如何使量子信息更加可靠。
圖2｜Peter Shor在1995年發表的論文（來源：美國物理學會）
Shor目前在劍橋的麻省理工學院工作，同時，他也是一位出版過詩集的詩人。
早在1994年，他就發現瞭如何使用量子計算機的模型進行計算，這讓物理學界和計算機科學界感到震驚。
他提出了一個算法——質因數分解算法，可以讓量子計算機以閃電般的速度將整數分解成質因數。今天的大多數互聯網流量是基於大質數的加密技術保護的。**這些代碼十分困難，因爲經典計算機在分解大型整數時很慢。
圖3｜Peter Shor在1994年發表的論文（來源：電氣電子工程師學會）
量子計算機現在已經成爲現實，儘管它們還不足以計算兩位數以上的數字。但量子計算機威脅互聯網加密只是時間問題。
訪談內容
《自然》雜誌採訪了Shor，詢問了關於他的工作所帶來的影響——以及互聯網安全的發展趨勢。
- 在你的質因數分解算法出現之前，量子計算機純粹就是爲了滿足理論層面的好奇心嗎？
我的論文的確使人們明白，這些機器可以做一些有用的事情。
計算機科學家Daniel Simon，在我得出我的結論之前，他就解決了一個他提出的問題，該問題表明量子計算機（比普通計算機）快得多。
但是即使採用Simon的算法，也無法得知這些機器是否可以發揮它們的用處。
- 在宣佈了你的質因數分解算法後，人們的反應如何？
起初，我只得到了一個不完整的結果。後來，在1994年4月，我在貝爾實驗室做了一個關於這個選題的報告。
消息傳得非常快，那個週末，計算機科學家Umesh Vazirani就給我打了電話說，「我聽說你可以在量子計算機上進行質因數分解，告訴我你是怎麼做到的。」
圖4｜Umesh Vazirani（來源：伯克利工程學院）
那時，我其實還沒有真正解決質因數分解的問題。但很神奇的是，報告結束的五天內，我的結果在人們的奔走相告中，變成了質因數分解成功。而在這五天裏，我也確實解決了分解的問題，於是我就可以告訴Umesh我是怎麼做到的了。
當時人們都在向我索要我還未完成的論文，所以我只能把粗稿拿給他們看了。
- 但是仍有許多專家認爲，量子計算機會在完成計算之前就丟失信息是嗎？
其中一個反對意見是，在量子力學中，如果你測量一個系統，你會不可避免地干擾到它。
我演示瞭如何在不測量計算的情況下測量誤差——然後你就可以修正誤差，而不破壞計算。
在我1995年發表了關於糾錯的論文之後，一些懷疑論者也確信量子計算是可行的。
- 糾錯依賴於「物理」和「邏輯」量子比特，這兩者間的區別是？
當你寫下一個量子計算機的算法時，你會假設量子比特是無噪聲的。這些無噪聲的量子比特就是邏輯量子比特，而我們的量子計算機中不存在沒有噪聲的量子比特。
事實上，如果我們試圖在沒有噪聲干預的環境下，運行我們的算法。那錯誤的發生，是不可避免的。
物理量子比特是量子計算機中的含噪聲的量子比特之一。爲了在運行我們的算法時，不出現任何錯誤，我們需要使用物理量子比特對邏輯量子比特進行編碼，這其中會用到量子糾錯代碼。
圖5｜量子比特（來源：medium）
而我們所知道的最好的方法，是有相當大的開銷的，此方法爲每個邏輯量子比特都提供了諸多物理量子比特。
要計算出這項技術還需要多少量子比特是相當複雜的。如果你想用表面碼（目前最佳選項）來建造一臺量子計算機，那麼每一個邏輯量子比特，大約需要100個物理量子比特來支持，甚至更多。
- 在2019年，谷歌展示了其「量子優勢」——即54個量子比特的量子計算機，它可以解決一個在經典計算機上耗時冗長的問題，你的反應是什麼？
這絕對是一個里程碑。它表明，量子計算機可以比經典計算機做得更好——至少在以人爲主導因素的問題上。
即便谷歌做了一些宣傳活動，但毋庸置疑的是，這臺量子計算機的確讓人印象深刻。
在它能創造出奇蹟之前，還需要一些完善工作。另外，初創公司IonQ製造的量子計算機，在某種程度上可能比谷歌和IBM的都要好。
- 當量子計算機可以分解大質數時，它們就可以**無處不在的互聯網加密系統「 RSA」，這點你如何看待？
是的，但是第一個**RSA的人，要麼是NSA（美國國家安全局），要麼是一些其他大型機構。
一開始，這些計算機運行會非常緩慢。如果你有一臺每小時只能**一個RSA**的計算機，那你肯定將其用於**國家級別安全風險的信息。
比起用量子計算機閱讀普通大衆的電子郵件，美國國家安全局有更重要的事情可以做——他們將閱讀中國大使的電子郵件，哈哈。
- 有沒有一種加密系統可以取代RSA，而且在量子計算機時代也是安全的——即「後量子加密」？
我認爲我們會有可以代替RSA的後量子密碼系統。
但RSA不是當下最重要的問題，當務之急是，還有其他方法可以破壞互聯網的安全，比如編程不良的軟件、病毒，會將信息發送給一些惡意玩家。
我認爲用安全的後量子密碼體制，來取代RSA的最大障礙，是我們的不懈努力及編程時間。我認爲這是我們知道如何去做的事情，只是我們是否能及時做到還是未知數。
圖6｜RSA算法（來源：Exabeam）
- 會不會出現讓我們措手不及的風險呢？
會的。爲了修復2000年出現的錯誤（千年蟲），人們付出了巨大的努力。
而人們需要付出更大的努力，才能切換到後量子時代。但如果我們等得太久，那就太遲了。
參考鏈接：
[1]https://www.nature.com/articles/d41586-020-03068-9
[2]https://journals.aps.org/pra/abstract/10.1103/PhysRevA.52.R2493
[3]https://ieeexplore.ieee.org/document/365700
[4]https://link.springer.com/article/10.1007/s00283-020-10022-0
[5]https://www.nature.com/articles/d41586-019-02936-3
[6]https://www.nature.com/articles/d41586-019-03213-z
聲明：此文出於傳遞高質量信息之目的，若來源標註錯誤或侵權，請作者持權屬證明與我們聯繫，我們將及時更正、刪除，所有圖片的版權歸屬所引用組織機構，此處僅引用，原創文章轉載需授權。