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

（來源：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 接受了這個挑戰。