以下為原文翻譯：
您最近發送的電子郵件可能使用經過驗證的方法進行了加密，該方法依賴於這樣一個想法：即使是最快的計算機也無法有效地將大量數字分解為因子。
另一方面，量子計算機有望快速破解經典計算機可能永遠無法破解的複雜加密系統。這一承諾基於Peter Shor（現任麻省理工學院教授）1994年提出的量子因子分解算法。
儘管研究人員在過去30年裡取得了巨大進展，但科學家尚未建造出一台強大到足以運行肖爾算法的量子計算機。
雖然一些研究人員正在致力於建造更大的量子計算機，但其他人一直在試圖改進肖爾的算法，以便它可以在更小的量子電路上運行。大約一年前，紐約大學計算機科學家Oded Regev提出了一項重大理論改進。他的算法可以運行得更快，但電路需要更多內存。
基於這些結果，麻省理工學院的研究人員提出了兩全其美的方法，將雷格夫算法的速度與肖爾算法的內存效率相結合。這種新算法與雷格夫的算法一樣快，需要更少的量子構建塊（稱為量子位），並且對量子噪音的容忍度更高，這可能使其在實踐中更可行。
從長遠來看，這種新算法可以為能夠抵禦量子計算機密碼破解能力的新加密方法的開發提供信息。
「如果建造大規模量子計算機，就會完成因式分解，我們必須找到其他東西來用於密碼學。「但這種威脅有多真實？我們能讓量子因式分解變得可行嗎？
「我們的工作可能會讓我們更接近實際實現，」福特基金會工程學教授、計算機科學與人工智慧實驗室（CSAIL）成員、描述該算法的論文的高級作者Vinod Vaikuntanathan說。
該論文的主要作者是麻省理工學院電氣工程和計算機科學系的研究生Seyoon Ragavan。該研究發表在2024年國際密碼學會議（Crypto 2024）上。
密碼分析
為了通過網絡安全地傳輸消息，電子郵件客戶端和消息應用程式等服務提供商通常依賴RSA，這是麻省理工學院研究人員Ron Rivest、Adi Shamir和Leonard Adleman於20世紀70年代發明的加密方案（因此得名「RSA」）。該系統基於這樣一個想法：對2，048位的積分（具有617位的數字）進行因式分解對於計算機來說太難在合理的時間內完成。
1994年，當時在貝爾實驗室工作的肖爾居間了一種算法，證明量子計算機可以足夠快地分解RSA密碼，這個想法被徹底推翻了。
「那是一個轉折點。但在1994年，沒有人知道如何建造足夠大的量子計算機。而我們離那裡還很遠。有些人想知道它們是否會被建造，」Vaikuntanathan說。
據估計，量子計算機需要大約2000萬個量子位來運行Shor的算法。目前，最大的量子計算機約有1，100個量子位。
量子計算機使用量子電路來執行計算，就像經典計算機使用經典電路一樣。每個量子電路都由一系列稱為量子門的操作組成。這些量子門使用量子位（量子計算機的最小構建塊）來執行計算。
但量子門會引入噪音，因此減少量子門會提高機器性能。研究人員一直在努力增強Shor的算法，使其可以在量子門更少的更小的電路上運行。
這正是雷格夫在一年前提出的賽道上所做的。
Vaikuntanathan說：「這是一個大新聞，因為這是自1994年以來肖爾賽道的首次真正改進。」
肖爾提出的量子電路的大小與被分解的數字的平方成正比。這意味著，如果你想分解一個2，048位的積分，該電路將需要數百萬個門。
雷格夫的電路需要的量子門少得多，但需要更多的量子位來提供足夠的存儲器。這提出了一個新問題。
「從某種意義上說，某些類型的量子位就像蘋果或橙子一樣。如果你保留它們，它們會隨著時間的推移而腐爛。你想要最大限度地減少需要保留的量子位數量，」Vaikuntanathan解釋道。
去年八月，他在一次研討會上聽到雷格夫談論他的研究成果。演講結束時，雷格夫提出了一個問題：有人能改進他的電路，使其需要更少的量子位嗎？Vaikuntanathan和Ragavan回答了這個問題。
如果您想了解更多信息，可以單擊視頻下方的連結。
感謝您觀看此視頻。如果您喜歡，請訂閱並點讚。謝謝
原文：https://techxplore.com/news/2024-08-smaller-noise-tolerant-quantum-factoring.html
更多信息：空間高效和噪音穩健的量子因子分析：eprint.iacr.org/2023/1501.pdf
更多信息：節省空間和抗噪量子分解：eprint.iacr.org/2023/1501.pdf
輸油管：