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

来源:岁月联盟 编辑:猪蛋儿 时间:2023-01-09

在一项最新研究中[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进行了可疑的“增强”