量子計算新突破：密碼學迎來大考

你最近發送的電子郵件很可能是使用一種經典加密方法進行加密的，這種方法基于這樣一個想法：即使是最快的計算機也無法高效地將一個巨大的數字分解成因數。

然而，量子計算機則有潛力能夠快速破解傳統計算機可能永遠無法解決的復雜密碼系統。這可能會基于1994年由彼得·肖爾（現為美國麻省理工學院教授）提出的量子分解算法實現。

盡管過去30年來研究人員取得了巨大進展，但科學家們仍未建造出足夠強大的量子計算機來運行肖爾的算法。

一些研究人員正在努力建造更大的量子計算機，而另一些研究人員則嘗試改進肖爾的算法，使得它可以在較小的量子電路上運行。大約一年前，紐約大學計算機科學家奧德·雷格夫提出了一項重大理論改進。他的算法運行速度更快，但需要更多內存。

基于這些研究結果，麻省理工學院的研究人員提出了一種結合了奧德·雷格夫算法速度和肖爾算法內存效率的折中方法。這個新算法與奧德·雷格夫的算法一樣快，但需要更少的量子構件（稱為量子比特），并且對量子噪聲的容忍度更高，這可能使其在實際中更容易實現。

從長遠來看，這種新算法可能為開發能夠抵抗量子計算機破解能力的全新加密方法提供指導。 “如果大規模的量子計算機最終被建造出來，那么分解算法就失效了，我們必須找到其他的加密方法。但這真的會是個威脅嗎？ 我們能讓量子分解算法變得實用嗎？我們的研究可能讓我們離實用化更近了一步。”福特基金會工程學教授、計算機科學與人工智能實驗室（CSAIL）成員兼該論文的資深作者維諾德說。

該論文的主要作者是麻省理工學院電子工程與計算機科學系的研究生拉加萬。這項研究將在2024年國際密碼學會議上發表。

破解密碼學

為了通過互聯網安全地傳輸信息，電子郵件客戶端和消息應用等服務提供商通常依賴于一種名為RSA的加密方案。

然而，在1994年，肖爾在貝爾實驗室工作時提出了一個算法，證明量子計算機可以快速分解，從而打破RSA加密。

“ 那是一個轉折點。但在1994年， 沒人知道如何建造足夠大的量子計算機。而我們現在還遠遠沒有實現這一目標。有些人甚至懷疑它們是否真的會被建造出來。”維諾德說。

據估計， 一臺量子計算機大約需要2000萬個量子比特才能運行肖爾的算法。而目前，最大的量子計算機大約只有1100個量子比特。

量子計算機通過量子電路執行計算，就像經典計算機使用經典電路一樣。每個量子電路由一系列稱為量子門的操作組成，這些量子門利用量子比特（量子計算機最小的構件）進行計算。

但量子門會引入噪聲，因此減少量子門的數量可以提高機器的性能。研究人員一直在努力改進肖爾的算法，以便它可以在較小的電路上運行，使用更少的量子門。

這正是雷格夫在一年前提出的電路所做的。

“這是一個大新聞，因為這是自1994年肖爾提出的電路以來的首次真改進。”維諾德說。

肖爾提出的量子電路的大小與所分解數字的平方成正比。這意味著如果要分解一個2048位的整數，電路將需要數百萬個量子門。

雷格夫的電路需要顯著更少的量子門，但它需要更多的量子比特來提供足夠的內存，而這帶來了一個新的問題。

“從某種意義上說，有些類型的量子比特就像蘋果或橙子。如果你長時間保留它們，它們會衰減。你希望盡量減少需要保留的量子比特的數量。”

他在2023年8月的一個研討會上聽到了雷格夫的講座。在講座結束時，雷格夫提出了一個問題：有人能改進他的電路以減少所需的量子比特嗎？

量子乒乓

為了分解一個非常大的數字，量子電路需要多次運行，執行涉及計算冪次的操作，如2的100次方。

但是，計算如此大的冪次在量子計算機上成本高昂且難以執行，因為量子計算機只能執行可逆操作。而平方一個數字不是一個可逆操作，所以每次進行平方計算時，必須增加更多的量子內存來計算下一個平方。

麻省理工學院的研究人員找到了一種巧妙的方法，通過使用一系列斐波那契數進行冪次計算，這只需要簡單的乘法操作，而乘法是可逆的。他們的方法只需要兩個量子內存單元來計算任何冪次。

“這有點像乒乓球比賽，我們從一個數字開始，然后在兩個量子內存寄存器之間來回彈跳進行乘法運算。”維諾德補充道。

他們還解決了糾錯問題。肖爾和雷格夫提出的電路要求每個量子操作都必須是正確的，算法才能正常工作。但在真實機器上實現無誤的量子門是不可行的。

他們通過使用一種技術過濾掉錯誤的結果并僅處理正確的結果，克服了這個問題。

最終結果是一個顯著更節省內存的電路。此外，他們的糾錯技術使該算法更具實用性。

“作者解決了之前量子分解算法中的兩個最重要瓶頸。盡管仍然不夠實用，但他們的工作讓量子分解算法更接近現實。”雷格夫補充道。

未來，研究人員希望使他們的算法更加高效，并有朝一日在真實的量子電路上測試分解。 （綜合整理報道）（策劃/克珂）