Shor算法30年来首次重大改进！更快破解密码

（图片来源：网络）

1994年，美国麻省理工学院 (MIT) 的应用数学家 Peter Shor 实现了量子计算机的第一个实际应用：破译密码。他展示了在查找大质数的质因子时，量子计算机比传统计算机要快得多，查找速度呈指数级增加。这些大质数通常用作密钥，加密保护通过互联网发送的大部分信息。

尽管今天量子计算机的量子比特数量还不够多或不够可靠，无法实现大规模的Shor算法，但30年来，对Shor算法的研究一直经久不衰。现在，一位计算机科学家研发了一种比Shor算法更好的新量子算法。8月12日首次发布到arXiv服务器的预印本中，纽约大学的Oded Regev提出了一种方案，可以大大减少分解非常大的质数所需的逻辑门或逻辑步骤的数量。原则上，该方案可以让小规模的量子计算机找出密钥，或者让中等规模的量子计算机更快地解码。

评估过这项工作的独立密码学家也很感兴趣。例如下个月Regev将召开他的新算法座谈会，麻省理工学院的计算机科学家 Vinod Vaikuntanathan 预计，届时会座无虚席。Vaikuntanathan 表示：“在量子计算领域，自Shor算法提出的30年里，已经出现了两到三个新想法。虽然不能每天都会出现新想法，但这让我们充满希望。”杜克大学量子计算研究员 Kenneth Brown 对此表示赞同：“大家都花费很长时间研究Shor算法，而这个新结果是令人惊讶的，而且超级酷。”

与所有量子算法一样，Shor 算法依赖于量子比特的神秘属性，它不仅可以设置为 0 和 1 的值，还可以同时设置为 0 和 1 的“叠加态”。量子比特可以拼接成量子门，执行逻辑运算。为了分解n位长的数字，Shor 算法需要n^2 个门的量子电路。

现在大多数互联网加密都依赖于至少2048比特的二进制质数，相当于617位长的十进制数字。因此，要用Shor算法找到它们的质因数，需要至少有400万个量子门的量子计算机。但迄今为止最大的量子计算机只有数百个量子比特。Brown说：“它们的规模都远不及我们完成破解所需要的数字。”

更糟糕的是，环境噪声常常破坏量子比特微妙的叠加态，从而破坏其运行计算。Vaikuntanathan 说：“噪声可以通过纠错来解决，但这需要更多的量子比特，数量达数百万甚至数十亿。量子比特的数量因为纠错需要爆炸式增长了，这就是为什么我们离真正能够分解2048位数字还很远。加强纠错会有所帮助，但改进Shor算法也会有帮助。”

Regev找到了一种方法来实现这一点。由于Shor算法是一维的，它通过将单个数字进行高次幂来搜索素因数。在得出结果之前，必须将许多大数相乘。Regev意识到他可以将多个不同维度的数字相乘。尽管这两种算法需要的乘法总数大致相同，但 Regev 的多维特征意味着在得出结果之前，乘法数字不会变得那么大。最后，他发现只需要n^1.5 个门即可分解一个n位整数。Vaikuntanathan 表示，这是 30 年来对 Shor 算法的首次重大改进。

但瑞典政府的量子计算研究员 Martin Ekerå 表示，Regev 的算法也存在缺陷。Regev 的算法需要量子存储器在计算过程中存储中间值，这意味着需要更多高质量的量子比特，这增加了算法的成本。Regev 承认对量子内存的需求，但表示当量子内存更便宜时，该算法最终仍然会有价值。”

当量子计算机准备好通过实施 Regev 或 Shor 算法来找到质因数时，互联网加密算法也在继续发展。联邦机构和安全领导人已经开始转向替代方案，包括所谓的“晶格密学”，它可以免受使用量子计算机的黑客攻击。即便如此，像 Regev 和 Shor 这样的算法可以用来解密当前和已经存下来的信息。

量子密码学一直在努力寻求重大突破。无论如何，Brown相信Regev工作的新颖性可能会激发量子密码学领域的其他新想法。他说：“我正在思考如何进一步推动这一目标。”

编译：卉可

编辑：慕一

特此说明：量子前哨翻译此文仅作信息传递和参考，并不意味着同意此文中的观点与数据。