中國量子團隊將破解RSA？Peter Shor這樣回應-資訊推薦

光子盒研究院出品

在一項最新研究中[1]，清華大學等單位的研究人員創(chuàng)建了一種算法，僅使用10個超導量子比特就實現(xiàn)了48位因式分解，并表示一個具有372個物理量子比特和數(shù)千深度的量子電路就可以挑戰(zhàn)RSA-2048密碼，這是一種人類用來保護信息安全的主流密碼。

(資料圖片)

這篇文章在arXiv一經(jīng)公布，就引發(fā)了國內(nèi)外學界的廣泛關注和爭議。Peter Shor在轉(zhuǎn)發(fā)一條推特時說，這篇論文顯然可能有問題（There are apparently possible problems with this paper.）。Shor是第一個提出量子計算機可以用于破解RSA的人，他發(fā)明的量子算法被稱為Shor算法。

原推文是由谷歌的量子軟件工程師Craig Gidney發(fā)布的，他說到，這篇論文確實花了很多篇幅，但沒有提到它需要的預計電路執(zhí)行次數(shù)。對論文的整個前提來說，對這個數(shù)字有一個小小的限制是至關重要的，據(jù)我所知，他們并沒有談到這個問題。非常糟糕。

玻色取樣和量子計算優(yōu)越性理論提出者、2020 ACM計算獎獲得者Scott Aaronson更是言辭激烈地批評了這篇論文。

Aaronson在其個人博客[2]以“草包量子分解”（Cargo Cult Quantum Factoring）為題發(fā)表了自己的看法。以下內(nèi)容是對其文章的轉(zhuǎn)述：

如果經(jīng)驗教會了我什么的話，那就是量子炒作的列車永遠不會減速。

在過去的24小時內(nèi)，至少有四個人通過電子郵件向我詢問一篇題為“在超導量子處理器上使用次線性資源分解整數(shù)”的新論文，包括安全專家Bruce Schneier。

該論文聲稱……在如何分解大整數(shù)方面取得了決定性的進展，從而使用近期量子計算機破解RSA密碼系統(tǒng)。請注意，不是通過使用Shor算法，而是通過使用具有欺騙性的相似名稱的Schnorr算法，這是一種基于格的經(jīng)典算法，作者隨后使用稱為QAOA的啟發(fā)式量子優(yōu)化方法對其進行了“增強”。

對于那些不想進一步閱讀的人，我只說一句：不就是不。

下面是我稍微長一點的評論：

Schnorr≠Shor。即使Schnorr算法使用QAOA進行了可疑的“增強”——QAOA是一種量子算法，令人難以置信的是，盡管有數(shù)百篇關于它的論文，但還沒有令人信服的理由證明它可以為任何問題產(chǎn)生任何加速（除了復制其自身錯誤模式的問題）。

在

這篇新論文

中，作者們花了一頁又一頁的篇幅，毫不猶豫地說，使用NISQ（即非容錯）量子計算機很可能很快就能破解RSA-2048。他們通過兩個久經(jīng)考驗的策略做到了這一點：

對不相關的細節(jié)探索（主要是優(yōu)化量子比特的數(shù)量，而忽略門的數(shù)量），以及對一個關鍵點保持沉默。

最后，他們在結論部分的一句話中清楚地說明了一個關鍵點：

需要指出的是，由于QAOA的收斂性不明確，該算法的量子加速比尚不清楚。

這里的“不清楚”非常輕描淡寫。在我看來，與可以在筆記本電腦上運行經(jīng)典的Schnorr算法相比，這篇論文的方法要產(chǎn)生任何好處都需要奇跡。如果后者能夠破解RSA，它早就破解了。

總而言之，這是我25年來見過的最具誤導性的量子計算論文之一。話雖如此，但這并不是我第一次遇到這樣的奇怪想法，即我們從Shor算法中了解到的整數(shù)分解指數(shù)量子加速應該以某種方式“蹭”到量子優(yōu)化啟發(fā)式算法上，而這些啟發(fā)算法并沒有體現(xiàn)Shor算法的實際見解。由于這個想法需要一個名字，我在此提出Cargo Cult Quantum Factoring。

參考：

[1]https://arxiv.org/abs/2212.12372

[2]https://scottaaronson.blog/?p=6957#comments

盒叔說：

關鍵詞： 中國量子團隊將破解RSAPeter Shor這樣回應 量子計算機