中国的一个研究团队公布了一项技术，该技术在理论上可以使用一台简陋的量子计算机破解用于确保数字隐私的最常用方法。
研究人员报告称，该技术在一个小规模的演示中奏效，但其他专家怀疑该程序能否扩大规模，从而在任务中击败普通计算机。尽管如此，他们警告说，上个月底发布在 arXiv 知识库上的这篇论文提醒人们注意在线隐私的脆弱性。
众所周知，量子计算机对当前的加密系统构成潜在威胁，但这项技术仍处于起步阶段。研究人员通常估计，量子计算机需要很多年才能比普通计算机更快地破解密码密钥——加密算法中用于保护数据的字符字符串。
支持科学新闻报道
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道 订阅。通过购买订阅，您将帮助确保未来能够继续报道关于发现和塑造我们当今世界的想法的具有影响力的故事。
研究人员在 20 世纪 90 年代意识到，量子计算机可以利用物理学的独特性来执行似乎超出“经典”计算机能力的任务。 Peter Shor，一位现任职于马萨诸塞州剑桥市麻省理工学院的数学家，在 1994 年展示了如何将量子叠加现象（描述原子大小的物体同时存在于多种状态的组合中的能力）和量子干涉（类似于池塘中的波浪如何相互叠加或抵消）应用于将整数分解为质数，即不能在没有余数的情况下进一步除法的整数。
Shor 算法将使量子计算机在破解基于大质数的加密系统（称为 Rivest-Shamir-Adleman 或 RSA，以其发明者的姓名首字母命名）以及其他一些流行的密码技术（目前保护在线隐私和安全）方面比经典计算机快指数级。但是，实施 Shor 技术需要比现有原型更大的量子计算机。量子计算机的大小以量子比特或 qubits 衡量。研究人员表示，可能需要一百万甚至更多的量子比特才能破解 RSA。目前最大的量子计算机——IBM 于 11 月发布的 Osprey 芯片——拥有 433 个量子比特。
一种新的方法
北京量子信息科学研究院的魏世杰及其合作者采取了不同的途径来击败 RSA，这种途径并非基于 Shor 算法，而是基于 Schnorr 算法——一种由德国法兰克福歌德大学数学家 Claus Schnorr 在 20 世纪 90 年代也设计出的整数分解过程。Schnorr 算法旨在在经典计算机上运行，但魏的团队在量子计算机上实现了该过程的一部分，使用了一种称为量子近似优化算法或 QAOA 的程序。
在尚未经过同行评审的论文中，作者声称他们的算法可以使用仅 372 个量子比特破解强大的 RSA 密钥——超过 600 位十进制数字的数字。在中国清华大学物理学家龙桂鲁代表所有作者发送给自然杂志的电子邮件中，他警告说，拥有大量量子比特是不够的，并且当前的量子计算机仍然过于容易出错，无法成功完成如此大的计算。“仅仅增加量子比特数量而不降低错误率是无济于事的。”
中国科学技术大学（合肥）构建量子计算机的物理学家陆朝阳（未参与该项目）表示，在如此小的机器上运行 QAOA 算法将要求 372 个量子比特中的每一个都以 99.9999% 的时间无错误地工作。最先进的量子比特几乎才达到 99.9% 的精度。
该团队在一个 10 量子比特的量子计算机上演示了这项技术，以分解更容易管理的 15 位数字 261,980,999,226,229。（它分解为两个质数，即 15,538,213 × 16,860,433。）研究人员表示，这是迄今为止借助量子计算机分解出的最大数字——尽管它比现代网络浏览器使用的加密密钥小得多。
有争议的论文
问题在于，没有人知道 QAOA 是否比仅仅在笔记本电脑上运行 Schnorr 的经典算法更快地分解大数字。“应该指出的是，该算法的量子加速尚不清楚，”作者写道。换句话说，虽然 Shor 算法保证在足够大的量子计算机可用时（如果可用）有效地破解加密，但基于优化的技术可以在小得多的机器上运行，但它可能永远无法完成任务。
加拿大滑铁卢大学的数学家 Michele Mosca 也指出，QAOA 并非第一个已知能够使用少量量子比特分解整数的量子算法。他和他的合作者在 2017 年描述过一个。因此，研究人员已经知道，没有任何基本原理要求量子计算机非常大才能分解数字。
其他研究人员抱怨说，尽管最新的论文可能是正确的，但关于速度的警告仅在论文的最后才出现。“总而言之，这是我 25 年来见过的最误导性的量子计算论文之一，”德克萨斯大学奥斯汀分校的量子计算理论家 Scott Aaronson 在博客中写道。
龙桂鲁在他的电子邮件中表示，他和他的合作者计划修改论文，并将警告移到更靠前的位置。“我们欢迎同行评审以及与世界各地科学家的交流，”声明补充说。
即使基于 Schnorr 的技术不会破坏互联网，量子计算机最终也可能通过运行 Shor 算法做到这一点。安全研究人员一直忙于开发许多被认为不太容易受到量子攻击的替代密码系统，称为后量子或量子安全。但是，研究人员未来也可能发现更好的量子算法，这些算法可以击败这些系统，从而造成灾难性的后果。
“对数字基础设施的信心将崩溃，”Mosca 说。“我们将突然从通过技术生命周期管理来管理量子安全迁移，转变为危机管理，”他补充道。“无论如何，这都不会好看。”
本文经许可转载，并于 2023 年 1 月 6 日首次发布。