量子计算机破解关键加密所需资源远低于此前预期

两篇独立撰写的白皮书得出结论：构建一台能够破解椭圆曲线这一重要密码系统的实用级量子计算机，所需资源远低于一两年前的预期。其中一篇论文展示了将中性原子用作可重构量子比特的方案，这些量子比特之间可以自由交互。研究人员进一步表明，这种方案可让量子计算机在10天内破解256位椭圆曲线密码学（ECC），所需开销比此前估算低100倍。另一篇来自谷歌研究人员的论文则展示了如何在不到9分钟内破解比特币及其他加密货币区块链所使用的ECC保护机制，同时将资源消耗降低20倍。

综合来看，这两篇论文是密码学相关量子计算（CRQC）在实用规模上取得实质性进展的最新信号。这些进步在很大程度上源于物理学家和计算机科学家开发的全新量子架构，其目标是打造即便在量子比特与外部环境交互产生错误的情况下仍能正确运行的量子计算机。另一关键推动力是不断优化的算法，这些算法持续强化了Shor算法的能力。Shor算法是1994年提出的一组方程，证明量子计算可以在多项式时间（具体为立方时间）内破解ECC和RSA密码系统，比当今经典计算机所需的指数级时间快得多。

目前，这两篇论文均尚未经过同行评审。

密码学工程师布莱恩·拉马基亚表示："研究社区在实现高效实用的CRQC所必需的物理量子比特和量子算法两方面，都在持续稳步推进。"他曾在2015年至2022年间主导微软的后量子过渡工作，现就职于Farcaster咨询集团。他补充道："我认为这两篇论文都没有给出我们何时能拥有实用CRQC的确切时间节点，但它们都提供了证据，表明我们正在持续向可实现的CRQC迈进，且这一进程并未放缓。"

获得最多关注的那篇论文采用了一种相对新颖的方法来实现容错量子计算（FTQC），可将破解ECC所需的物理量子比特数量减少至原来的百分之一。与更常见的超导方案不同，研究人员利用中性原子构建物理量子比特。该过程通过激光冷却原子，将单个原子捕获在被称为"光学镊子"的高度聚焦光束中，每把光学镊子捕获一个原子。借助光学多路复用技术，研究人员可以构建由大量被捕获原子组成的阵列。

这种方案的优势在于，所有物理量子比特之间均可相互交互。这种"非本地"通信方式与超导方案中的量子比特交互方式有着根本性的区别——在超导方案中，量子比特排列在二维网格上，每个量子比特只能与紧邻的四个量子比特相互作用。量子比特能够与远距离量子比特交互，使得纠错效率大幅提升，因为非本地通信可以显著增加容错检查的数量和全面性。

因此，这篇题为《Shor算法最少只需1万个可重构原子量子比特即可实现》的论文指出，量子计算机只需不到3万个物理量子比特即可在10天内破解ECC-256，比此前的估算高效数个数量级。另一个独立研究团队去年已证明，他们能够构建超过6000个量子比特的中性原子捕获阵列。结合大规模高保真量子操作的进展，中性原子具备运行容错量子计算的潜力。

研究人员在论文中写道："尽管还需要大量工作将这些进展整合到完整装置中并将系统规模扩展至所需水平，但我们的分析表明，经过适当设计的中性原子架构有望支持Shor算法在密码学相关场景下的实现。这一发现进一步强调了当前推动广泛部署的密码系统向后量子标准过渡的重要性，而这些标准正是为了抵御量子攻击而设计的。"

Q&A

Q1：椭圆曲线密码学（ECC）为什么难以被破解？量子计算机是如何做到的？

A：ECC依赖椭圆曲线离散对数问题的数学难题，传统计算机需要指数级时间才能破解。而量子计算机利用Shor算法，可在多项式时间（立方时间）内完成破解，效率远超经典计算机。最新研究表明，使用中性原子架构的量子计算机仅需不到3万个物理量子比特，就能在10天内破解256位ECC，所需资源比此前估算低100倍。

Q2：中性原子量子比特和超导量子比特有什么区别？

A：超导量子比特排列在二维网格上，每个量子比特只能与紧邻的四个量子比特交互，通信受限。而中性原子量子比特通过光学镊子捕获单个原子，所有量子比特之间可自由交互，支持"非本地"通信，这使得纠错效率大幅提升，容错检查更加全面，从而显著降低了实现实用量子计算所需的资源开销。

Q3：这些研究成果意味着现有的加密系统马上就不安全了吗？

A：目前尚不意味着立即失效。两篇论文均未经同行评审，且研究人员也指出，将现有进展整合到完整系统并扩展至所需规模仍需大量工作。但这些进展表明，实用级密码破解量子计算机的到来并非遥不可期，因此推动密码系统向抗量子攻击的后量子标准过渡的工作显得尤为迫切。