中国量子团队将破解RSA？Peter Shor这样回应-天天简讯

在一项最新研究中[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

标签： 量子计算机 这是一种