您发送的最新电子邮件很可能使用一种久经考验的方法加密，该方法依赖于这样的理念：即使是最快的计算机也无法有效地将一个巨大的数字分解为因子。
另一方面，量子计算机有望快速破解传统计算机可能永远无法破解的复杂密码系统。这一前景基于彼得·肖尔(PeterShor)于1994年提出的量子因式分解算法，肖尔现在是麻省理工学院的教授。
然而，尽管研究人员在过去30年中取得了巨大进步，但科学家尚未建造出足够强大的量子计算机来运行Shor算法。
一些研究人员致力于建造更大的量子计算机，而另一些人则试图改进Shor算法，使其能够在更小的量子电路上运行。大约一年前，纽约大学计算机科学家OdedRegev提出了一项重大的理论改进。他的算法可以运行得更快，但电路需要更多的内存。
基于这些结果，麻省理工学院的研究人员提出了一种两全其美的方法，将Regev算法的速度与Shor算法的内存效率相结合。这种新算法与Regev算法一样快，需要的量子构建块(称为量子位)更少，并且对量子噪声的容忍度更高，这使得它在实践中更可行。
从长远来看，这种新算法可以为开发能够抵御量子计算机密码破译能力的新型加密方法提供参考。
“如果大规模量子计算机真的被建造出来，那么因式分解就完蛋了，我们必须找到其他东西用于加密。但这种威胁有多大?我们能让量子因式分解变得实用吗?
“我们的工作可能让我们更接近实际实施，”福特基金会工程学教授、计算机科学与人工智能实验室(AIL)成员、描述该算法的论文的高级作者VinodVaikuntanathan说。
该论文的主要作者是麻省理工学院电气工程与计算机科学系研究生SeyoonRagavan。这项研究在2024年国际密码学会议(Crypto2024)上进行了展示。
破解密码
为了安全地在互联网上传输信息，电子邮件客户端和消息应用程序等服务提供商通常依赖RSA，这是麻省理工学院研究人员RonRivest、AdiShamir和LeonardAdleman在20世纪70年代发明的一种加密方案(因此得名“RSA”)。该系统基于这样的理念：对2,048位整数(617位数字)进行因式分解对于计算机来说太难了，无法在合理的时间内完成。
1994年，当时在贝尔实验室工作的肖尔(Shor)提出了一种算法，证明了量子计算机可以快速分解并破解RSA密码，这一想法被彻底颠覆。
“那是一个转折点。但在1994年，没有人知道如何建造一台足够大的量子计算机。而我们距离那个目标还很远。有些人怀疑它们是否能被建造出来，”Vaikuntanathan说。
据估计，量子计算机需要大约2000万个量子比特才能运行Shor算法。目前，最大的量子计算机大约有1100个量子比特。
量子计算机使用量子电路进行计算，就像传统计算机使用传统电路一样。每个量子电路由一系列称为量子门的操作组成。这些量子门利用量子位(量子计算机的最小构建块)来执行计算。
但量子门会引入噪音，因此减少门的数量可以提高机器的性能。研究人员一直在努力增强Shor算法，以便能够在更小的电路上运行，减少量子门的数量。
这正是雷格夫一年前提出的电路所做的事情。
“这是个大新闻，因为这是自1994年以来Shor赛道的第一次真正改进，”Vaikuntanathan说。
Shor提出的量子电路的大小与被分解的数的平方成正比。这意味着，如果要分解一个2,048位整数，该电路将需要数百万个门。
Regev的电路需要的量子门数量明显较少，但需要更多的量子比特来提供足够的内存。这带来了一个新问题。
“从某种意义上说，某些类型的量子比特就像苹果或橘子。如果你保留它们，它们会随着时间的推移而衰减。你想尽量减少需要保留的量子比特数量，”Vaikuntanathan解释道。
去年8月，他在一次研讨会上听Regev介绍了他的成果。在演讲结束时，Regev提出了一个问题：有人能改进他的电路，让它需要更少的量子比特吗?Vaikuntanathan和Ragavan回答了这个问题。
量子乒乓
为了分解一个非常大的数字，量子电路需要运行多次，执行涉及计算能力的运算，例如2的100次方。
但计算如此大的幂的成本高昂，而且在量子计算机上很难完成，因为量子计算机只能执行可逆运算。对一个数进行平方不是可逆运算，因此每次对一个数进行平方时，都必须添加更多的量子内存来计算下一个平方。
麻省理工学院的研究人员找到了一种巧妙的方法，利用一系列斐波那契数来计算指数，只需进行简单的乘法(可逆)，而不是平方。他们的方法只需要两个量子存储单元即可计算任何指数。
“这有点像乒乓球游戏，我们从一个数字开始，然后来回反弹，在两个量子存储寄存器之间相乘，”Vaikuntanathan补充道。
他们还解决了纠错难题。Vaikuntanathan表示，Shor和Regev提出的电路要求每个量子操作都正确，这样他们的算法才能正常工作。但在真实机器上，无错误量子门是不可行的。
他们使用一种技术过滤掉损坏的结果并只处理正确的结果来克服这个问题。
最终结果是电路的内存效率显著提高。此外，他们的纠错技术将使该算法更易于部署。
“作者解决了早期量子因式分解算法中最重要的两个瓶颈。尽管目前还不能立即投入使用，但他们的工作使量子因式分解算法更接近现实，”Regev补充道。
未来，研究人员希望使他们的算法更加高效，并有朝一日用它来测试真实量子电路的分解。
“这项工作之后，一个显而易见的问题是：它是否真的能让我们更接近破解RSA密码学?目前还不清楚;这些改进目前只有在整数远大于2,048位时才会发挥作用。我们能否推动这种算法，使其比Shor算法更可行，即使对于2,048位整数也是如此?”Ragavan说。