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

（来源：MIT News）

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

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

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

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

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

从长远来看，这种新算法可能为开发能够抵抗量子计算机破解能力的全新加密方法提供指导。

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

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

破解密码学

为了通过互联网安全地传输信息，电子邮件客户端和消息应用等服务提供商通常依赖于一种名为 RSA 的加密方案，该方案由麻省理工学院的 Ron Rivest、Adi Shamir 和 Leonard Adleman于上世纪 70 年代发明（因此得名“RSA”）。该系统基于这样一个想法：分解一个 2048 位的整数（一个 617 位的数字）对于计算机来说在合理时间内太难完成。

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

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

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

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

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

这正是 Regev 在一年前提出的电路所做的。

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

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

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

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

他在去年 8 月的一个研讨会上听到了 Regev 的讲座。在讲座结束时，Regev 提出了一个问题：有人能改进他的电路以减少所需的量子比特吗？Vaikuntanathan 和 Ragavan 接受了这个挑战。

量子乒乓

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

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

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

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

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

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

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

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

未来，研究人员希望使他们的算法更加高效，并有朝一日在真实的量子电路上测试分解。

“在这项工作之后，不可忽视的问题是：这是否真的让我们更接近破解 RSA 加密？目前还不清楚；这些改进目前只有在整数远大于 2048 位时才会显现效果。我们能否推动这个算法，使其比肖尔的算法在分解 2048 位整数时更具可行性？”Ragavan 说。

这项研究得到了 Akamai 总统奖学金、美国国防高级研究计划局、国家科学基金会、麻省理工学院-IBM 沃森人工智能实验室、Thornton 家族教员研究创新奖学金以及西蒙斯研究员奖的资助。

https://news.mit.edu/2024/toward-code-breaking-quantum-computer-0823