查看原文
其他

中国量子团队将破解RSA?Peter Shor这样回应

光子盒研究院 光子盒 2023-03-04

光子盒研究院出品



在一项最新研究中[1],清华大学等单位的研究人员创建了一种算法,仅使用10个超导量子比特就实现了48位因式分解,并表示一个具有372个物理量子比特和数千深度的量子电路就可以挑战RSA-2048密码,这是一种人类用来保护信息安全的主流密码。

这篇文章在arXiv一经公布,就引发了国内外学界的广泛关注和争议。Peter Shor在转发一条推特时说,这篇论文显然可能有问题(There are apparently possible problems with this paper.)。Shor是第一个提出量子计算机可以用于破解RSA的人,他发明的量子算法被称为Shor算法。

原推文是由谷歌的量子软件工程师Craig Gidney发布的,他说到,这篇论文确实花了很多篇幅,但没有提到它需要的预计电路执行次数。对论文的整个前提来说,对这个数字有一个小小的限制是至关重要的,据我所知,他们并没有谈到这个问题。非常糟糕。


玻色取样和量子计算优越性理论提出者、2020 ACM计算奖获得者Scott Aaronson更是言辞激烈地批评了这篇论文。

Aaronson在其个人博客[2]以“草包量子分解”(Cargo Cult Quantum Factoring)为题发表了自己的看法。以下内容是对其文章的转述

如果经验教会了我什么的话,那就是量子炒作的列车永远不会减速。

在过去的24小时内,至少有四个人通过电子邮件向我询问一篇题为“在超导量子处理器上使用次线性资源分解整数”的新论文,包括安全专家Bruce Schneier。

该论文声称……在如何分解大整数方面取得了决定性的进展,从而使用近期量子计算机破解RSA密码系统。请注意,不是通过使用Shor算法,而是通过使用具有欺骗性的相似名称的Schnorr算法,这是一种基于格的经典算法,作者随后使用称为QAOA的启发式量子优化方法对其进行了“增强”。

对于那些不想进一步阅读的人,我只说一句:不就是不。

下面是我稍微长一点的评论:

Schnorr≠Shor。即使Schnorr算法使用QAOA进行了可疑的“增强”——QAOA是一种量子算法,令人难以置信的是,尽管有数百篇关于它的论文,但还没有令人信服的理由证明它可以为任何问题产生任何加速(除了复制其自身错误模式的问题)。

这篇新论文中,作者们花了一页又一页的篇幅,毫不犹豫地说,使用NISQ(即非容错)量子计算机很可能很快就能破解RSA-2048。他们通过两个久经考验的策略做到了这一点:

对不相关的细节探索(主要是优化量子比特的数量,而忽略门的数量),以及对一个关键点保持沉默。

最后,他们在结论部分的一句话中清楚地说明了一个关键点:

需要指出的是,由于QAOA的收敛性不明确,该算法的量子加速比尚不清楚。

这里的“不清楚”非常轻描淡写。在我看来,与可以在笔记本电脑上运行经典的Schnorr算法相比,这篇论文的方法要产生任何好处都需要奇迹。如果后者能够破解RSA,它早就破解了。

总而言之,这是我25年来见过的最具误导性的量子计算论文之一。话虽如此,但这并不是我第一次遇到这样的奇怪想法,即我们从Shor算法中了解到的整数分解指数量子加速应该以某种方式“蹭”到量子优化启发式算法上,而这些启发算法并没有体现Shor算法的实际见解。由于这个想法需要一个名字,我在此提出Cargo Cult Quantum Factoring。

参考:
[1]https://arxiv.org/abs/2212.12372
[2]https://scottaaronson.blog/?p=6957#comments

盒叔说:


根据公众号平台最新的推送规则,如果不想错过盒叔的文章,记得标星标哦,以前加过的也需要重新添加,这样每次新文章推送才会第一时间出现在你的订阅列表里。



相关阅读:
清华浙大在量子计算破解RSA密码方面取得重要突破
中国的量子存储器成果,将使攻破2048位RSA密码更近一步
最新研究:只需1.3万个量子比特,即可破解2048位RSA加密
Shor算法提出近三十年,为何RSA仍未被终结?

#光子盒视频号开通啦!你要的,这里全都有#
每周一到周五,我们都将与光子盒的新老朋友相聚在微信视频号,不见不散!
你可能会错过:|qu|cryovac>

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存