（來源：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
