研究人員提出了一種更小、更耐雜訊的密碼學量子分解電路
以下内容翻译自原文：
您最近發送的電子郵件可能是使用經過驗證的方法進行加密的，該方法依賴於這樣的想法：即使是最快的計算機也無法有效地將巨大的數字分解為因子。
另一方面，量子電腦有望快速破解經典電腦可能永遠無法破解的複雜密碼系統。這項承諾是基於 Peter Shor（現任麻省理工學院教授）於 1994 年提出的量子因子分解演算法。
儘管研究人員在過去 30 年裡取得了長足的進步，但科學家尚未建造出足夠強大的量子電腦來運行 Shor 的演算法。
當一些研究人員致力於建造更大的量子電腦時，其他研究人員一直在嘗試改進 Shor 的演算法，以便它可以在更小的量子電路上運行。大約一年前，紐約大學電腦科學家 Oded Regev 提出了一項重大理論改進。他的演算法可以運行得更快，但電路需要更多的記憶體。
在這些結果的基礎上，麻省理工學院的研究人員提出了一種兩全其美的方法，將 Regev 演算法的速度與 Shor 演算法的記憶體效率結合。這種新演算法與 Regev 的演算法一樣快，需要更少的量子構建塊（稱為量子位元），並且對量子雜訊具有更高的容忍度，這可能使其在實踐中更可行。
從長遠來看，這種新演算法可以為新型加密方法的開發提供訊息，這些方法可以承受量子電腦的密碼破解能力。
「如果大規模量子電腦建成，那麼因式分解就完蛋了，我們必須找到其他東西來用於密碼學。但是這種威脅有多真實？我們能讓量子因式分解變得實用嗎？
福特基金會工程教授、計算機科學和人工智慧實驗室 (CSAIL) 成員、描述該演算法的論文的高級作者 Vinod Vaikuntanathan 表示：“我們的工作可能會讓我們更接近實際實現。” 。
論文的主要作者是麻省理工學院電機工程和計算機科學系的研究生 Seyoon Ragavan。該研究已在 2024 年國際密碼學會議（ Crypto 2024 ）上發表。
破解密碼學
為了透過網路安全地傳輸訊息，電子郵件用戶端和訊息應用程式等服務提供者通常依賴RSA，這是由麻省理工學院研究人員Ron Rivest、Adi Shamir 和Leonard Adleman 在20 世紀70 年代發明的加密方案（因此稱為“RSA”）。該系統基於這樣的想法：對 2,048 位元整數（具有 617 位數的數字）進行因式分解對於電腦來說太難了，無法在合理的時間內完成。
1994 年，當時在貝爾實驗室工作的 Shor 引入了一種演算法，證明量子電腦可以足夠快地分解 RSA 密碼，這一想法被徹底顛覆。
「那是一個轉捩點。但在 1994 年，沒有人知道如何建造足夠大的量子電腦。而且我們離那裡還很遠。有些人想知道它們是否會被建造出來，」Vaikuntanathan 說。
據估計，一台量子電腦需要大約 2000 萬個量子位元來運行 Shor 的演算法。目前，最大的量子電腦擁有約 1,100 個量子位元。
量子電腦使用量子電路進行計算，就像經典電腦使用經典電路一樣。每個量子電路都由一系列稱為量子閘的操作組成。這些量子閘利用量子位元（量子電腦的最小構建塊）來執行計算。
但量子閘會引入噪聲，因此減少量子閘將提高機器的性能。研究人員一直在努力增強 Shor 的演算法，以便它可以在具有更少量子閘的更小的電路上運行。
這正是雷格夫對他一年前提出的電路所做的事情。
「這是一個大新聞，因為這是自 1994 年以來對 Shor 電路的第一次真正改進，」Vaikuntanathan 說。
肖爾提出的量子電路的大小與被分解的數字的平方成正比。這意味著如果要分解 2,048 位元整數，電路將需要數百萬個閘。
Regev 的電路所需的量子閘明顯減少，但它需要更多的量子位元來提供足夠的記憶體。這就提出了一個新問題。
「從某種意義上說，某些類型的量子位元就像蘋果或橘子。如果你保留它們，它們會隨著時間的推移而衰減。你希望盡量減少需要保留的量子位元數量，」Vaikuntanathan 解釋道。
去年八月，他在一次研討會上聽到雷格夫談論他的研究結果。在演講結束時，雷格夫提出了一個問題：有人可以改進他的電路，使其需要更少的量子位元嗎？ Vaikuntanathan 和 Ragavan 回答了這個問題。
如果想详细了解，可以点开视频下方的链接。
谢谢观看本视频。要是喜欢，请订阅、点赞。谢谢
原文：https://techxplore.com/news/2024-08-smaller-noise-tolerant-quantum-factoring.html
More information: Space-Efficient and Noise-Robust Quantum Factoring: eprint.iacr.org/2023/1501.pdf
更多資訊：節省空間且抗雜訊的量子分解： eprint.iacr.org/2023/1501.pdf
