量子计算新突破：密码学迎来大考

你最近发送的电子邮件很可能是使用一种经典加密方法进行加密的，这种方法基于这样一个想法：即使是最快的计算机也无法高效地将一个巨大的数字分解成因数。

然而，量子计算机则有潜力能够快速破解传统计算机可能永远无法解决的复杂密码系统。这可能会基于1994年由彼得·肖尔（现为美国麻省理工学院教授）提出的量子分解算法实现。

尽管过去30年来研究人员取得了巨大进展，但科学家们仍未建造出足够强大的量子计算机来运行肖尔的算法。

一些研究人员正在努力建造更大的量子计算机，而另一些研究人员则尝试改进肖尔的算法，使得它可以在较小的量子电路上运行。大约一年前，纽约大学计算机科学家奥德·雷格夫提出了一项重大理论改进。他的算法运行速度更快，但需要更多内存。

基于这些研究结果，麻省理工学院的研究人员提出了一种结合了奥德·雷格夫算法速度和肖尔算法内存效率的折中方法。这个新算法与奥德·雷格夫的算法一样快，但需要更少的量子构件（称为量子比特），并且对量子噪声的容忍度更高，这可能使其在实际中更容易实现。

从长远来看，这种新算法可能为开发能够抵抗量子计算机破解能力的全新加密方法提供指导。 “如果大规模的量子计算机最终被建造出来，那么分解算法就失效了，我们必须找到其他的加密方法。但这真的会是个威胁吗？ 我们能让量子分解算法变得实用吗？我们的研究可能让我们离实用化更近了一步。”福特基金会工程学教授、计算机科学与人工智能实验室（CSAIL）成员兼该论文的资深作者维诺德说。

该论文的主要作者是麻省理工学院电子工程与计算机科学系的研究生拉加万。这项研究将在2024年国际密码学会议上发表。

破解密码学

为了通过互联网安全地传输信息，电子邮件客户端和消息应用等服务提供商通常依赖于一种名为RSA的加密方案。

然而，在1994年，肖尔在贝尔实验室工作时提出了一个算法，证明量子计算机可以快速分解，从而打破RSA加密。

“ 那是一个转折点。但在1994年， 没人知道如何建造足够大的量子计算机。而我们现在还远远没有实现这一目标。有些人甚至怀疑它们是否真的会被建造出来。”维诺德说。

据估计， 一台量子计算机大约需要2000万个量子比特才能运行肖尔的算法。而目前，最大的量子计算机大约只有1100个量子比特。

量子计算机通过量子电路执行计算，就像经典计算机使用经典电路一样。每个量子电路由一系列称为量子门的操作组成，这些量子门利用量子比特（量子计算机最小的构件）进行计算。

但量子门会引入噪声，因此减少量子门的数量可以提高机器的性能。研究人员一直在努力改进肖尔的算法，以便它可以在较小的电路上运行，使用更少的量子门。

这正是雷格夫在一年前提出的电路所做的。

“这是一个大新闻，因为这是自1994年肖尔提出的电路以来的首次真改进。”维诺德说。

肖尔提出的量子电路的大小与所分解数字的平方成正比。这意味着如果要分解一个2048位的整数，电路将需要数百万个量子门。

雷格夫的电路需要显著更少的量子门，但它需要更多的量子比特来提供足够的内存，而这带来了一个新的问题。

“从某种意义上说，有些类型的量子比特就像苹果或橙子。如果你长时间保留它们，它们会衰减。你希望尽量减少需要保留的量子比特的数量。”

他在2023年8月的一个研讨会上听到了雷格夫的讲座。在讲座结束时，雷格夫提出了一个问题：有人能改进他的电路以减少所需的量子比特吗？

量子乒乓

为了分解一个非常大的数字，量子电路需要多次运行，执行涉及计算幂次的操作，如2的100次方。

但是，计算如此大的幂次在量子计算机上成本高昂且难以执行，因为量子计算机只能执行可逆操作。而平方一个数字不是一个可逆操作，所以每次进行平方计算时，必须增加更多的量子内存来计算下一个平方。

麻省理工学院的研究人员找到了一种巧妙的方法，通过使用一系列斐波那契数进行幂次计算，这只需要简单的乘法操作，而乘法是可逆的。他们的方法只需要两个量子内存单元来计算任何幂次。

“这有点像乒乓球比赛，我们从一个数字开始，然后在两个量子内存寄存器之间来回弹跳进行乘法运算。”维诺德补充道。

他们还解决了纠错问题。肖尔和雷格夫提出的电路要求每个量子操作都必须是正确的，算法才能正常工作。但在真实机器上实现无误的量子门是不可行的。

他们通过使用一种技术过滤掉错误的结果并仅处理正确的结果，克服了这个问题。

最终结果是一个显著更节省内存的电路。此外，他们的纠错技术使该算法更具实用性。

“作者解决了之前量子分解算法中的两个最重要瓶颈。尽管仍然不够实用，但他们的工作让量子分解算法更接近现实。”雷格夫补充道。

未来，研究人员希望使他们的算法更加高效，并有朝一日在真实的量子电路上测试分解。 （综合整理报道）（策划/克珂）