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

(來源:MIT News)(來源:MIT News)

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

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

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

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

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

從長遠來看,這種新算法可能為開發能夠抵抗量子計算機破解能力的全新加密方法提供指導。

「如果大規模的量子計算機最終被建造出來,那麼分解算法就失效了,我們必須找到其他的加密方法。但這真的會是個威脅嗎?我們能讓量子分解算法變得實用嗎?我們的研究可能讓我們離實用化更近了一步,」福特基金會工程學教授、計算機科學與人工智能實驗室(CSAIL)成員兼該論文的資深作者 Vinod Vaikuntanathan 說。

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

破解密碼學

為了通過互聯網安全地傳輸信息,電子郵件客戶端和消息應用等服務提供商通常依賴於一種名為 RSA 的加密方案,該方案由麻省理工學院的 Ron Rivest、Adi Shamir 和 Leonard Adleman於上世紀 70 年代發明(因此得名「RSA」)。該系統基於這樣一個想法:分解一個 2048 位的整數(一個 617 位的數字)對於計算機來說在合理時間內太難完成。

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

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

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

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

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

這正是 Regev 在一年前提出的電路所做的。

「這是一個大新聞,因為這是自 1994 年肖爾提出的電路以來的首次真改進。」Vaikuntanathan 說。

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

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

「從某種意義上說,有些類型的量子比特就像蘋果或橙子。如果你長時間保留它們,它們會衰減。你希望儘量減少需要保留的量子比特的數量。」Vaikuntanathan 解釋說。

他在去年 8 月的一個研討會上聽到了 Regev 的講座。在講座結束時,Regev 提出了一個問題:有人能改進他的電路以減少所需的量子比特嗎?Vaikuntanathan 和 Ragavan 接受了這個挑戰。

量子乒乓

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

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

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

「這有點像乒乓球比賽,我們從一個數字開始,然後在兩個量子內存寄存器之間來回彈跳進行乘法運算。」Vaikuntanathan 補充道。

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

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

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

「作者解決了之前量子分解算法中的兩個最重要瓶頸。儘管仍然不夠實用,但他們的工作讓量子分解算法更接近現實。」Regev 補充道。

未來,研究人員希望使他們的算法更加高效,並有朝一日在真實的量子電路上測試分解。

「在這項工作之後,不可忽視的問題是:這是否真的讓我們更接近破解 RSA 加密?目前還不清楚;這些改進目前只有在整數遠大於 2048 位時才會顯現效果。我們能否推動這個算法,使其比肖爾的算法在分解 2048 位整數時更具可行性?」Ragavan 說。

這項研究得到了 Akamai 總統獎學金、美國國防高級研究計劃局、國家科學基金會、麻省理工學院-IBM 沃森人工智能實驗室、Thornton 家族教員研究創新獎學金以及西蒙斯研究員獎的資助。

原文鏈接:

https://news.mit.edu/2024/toward-code-breaking-quantum-computer-0823