摘要：研究人员以具有里程碑意义的算法为基础，提出了一种使较小且更具噪声的量子保理电路进行加密术的方法。...

您发送的最新电子邮件很可能是使用久经考验的方法加密的，该方法依赖于这样的想法，即即使是最快的计算机也无法有效地将巨大的数字分解为因素。

另一方面，量子计算机有望快速破解古典计算机可能永远无法解开的复杂加密系统。该诺言基于1994年彼得·谢尔（Peter Shor）提出的量子保理算法，他现在是麻省理工学院的教授。

但是，尽管研究人员在过去30年中取得了长足的进步，但科学家尚未建造足够强大的量子计算机来运行Shor的算法。

当一些研究人员努力构建较大的量子计算机时，其他人一直在尝试改善Shor的算法，以便它可以在较小的量子电路上运行。大约一年前，纽约大学计算机科学家ODED REGEV提出了重大的理论改进。他的算法可以更快地运行，但是电路需要更多的内存。

麻省理工学院的研究人员建立了这些结果，提出了一种最佳的世界方法，该方法将Regev算法的速度与Shor的记忆效率相结合。这种新算法与Regev一样快，需要更少的量子构件称为Qubits，并且对量子噪声具有更高的容忍度，这可能使实践中实现更可行。

从长远来看，这种新算法可以为可以承受量子计算机的破坏代码功能的新型加密方法的开发提供信息。

“如果大规模量子计算机构建，那么考虑吐司，我们必须找到其他用于加密术的东西。但是，这种威胁是如何真实的？我们可以使量子考虑实用吗？我们的工作可能会使我们更接近实践实施一步，这是一位高级工程学的工程学教授，即计算机科学的成员。描述算法。

该论文的主要作者是塞扬·拉加万（Seyoon Ragavan），他是麻省理工学院电气工程和计算机科学系的研究生。该研究将在2024年国际密码学会议上介绍。

破裂的密码学

为了通过Internet安全传输消息，诸如电子邮件客户端和消息传递应用程序之类的服务提供商通常依赖RSA，这是MIT研究人员Ron Rivest，Adi Shamir和Leonard Adleman在1970年代发明的加密方案（因此名称为“ RSA”）。该系统基于这样的想法：考虑到2,048位整数（具有617位数字的数字）对于计算机来说太难在合理的时间内进行。

1994年，当时在贝尔实验室（Bell Labs）工作的Shor引入了一种算法，证明量子计算机可以迅速考虑以打破RSA加密术，这一想法被倒在头上。

Vaikuntanathan说：“那是一个转折点。但是在1994年，没人知道如何制造一台足够大的量子计算机。我们仍然离那里很远。有些人想知道它们是否会被建造。”

据估计，量子计算机将需要大约2000万QUAT来运行Shor的算法。目前，最大的量子计算机有约1,100吨。

量子计算机使用量子电路执行计算，就像经典计算机使用经典电路一样。每个量子电路由称为量子门的一系列操作组成。这些量子门利用量子计算机是量子计算机的最小构建块来执行计算。

但是量子门会引入噪音，因此较少的大门可以改善机器的性能。研究人员一直在努力增强Shor的算法，因此它可以在较小的量子门的较小电路上运行。

这正是Regev对他一年前提出的巡回赛所做的。

Vaikuntanathan说：“这是大新闻，因为这是1994年从Shor巡回赛的第一个真正的改进。”

提议的量子电路的大小与所考虑的数字的平方成正比。这意味着，如果要考虑一个2,048位整数，则该电路将需要数百万个大门。

Regev的电路需要更少的量子门，但是它需要更多的量子位才能提供足够的内存。这提出了一个新问题。

Vaikuntanathan解释说：“从某种意义上说，某些类型的Qubits就像苹果或橙子一样。如果将它们保持在附近，它们会随着时间的推移而衰减。您想最大程度地减少需要保持的量子数量。”

他听到Regev在去年八月的一个研讨会上谈到了他的结果。在谈话结束时，Regev提出了一个问题：有人可以改善他的赛道，以便更少的Qubits吗？ Vaikuntanathan和Ragavan提出了这个问题。

量子乒乓球

要考虑一个非常大的数字，量子电路需要运行多次，执行涉及计算功率的操作，例如1对100的功率。

但是，在量子计算机上计算如此大的功率是昂贵且难以执行的，因为量子计算机只能执行可逆操作。平方数字不是可逆的操作，因此每次平方时，都必须添加更多的量子内存来计算下一个正方形。

麻省理工学院的研究人员找到了一种使用一系列需要简单乘法的斐波那契数字来计算指数的巧妙方法，这是可逆的，而不是平方。他们的方法仅需要两个量子内存单元来计算任何指数。

Vaikuntanathan补充说：“这有点像乒乓球游戏，我们从数字开始，然后来回反弹，乘以两个量子内存寄存器。”

他们还解决了错误纠正的挑战。 Vaikuntanathan说，Shor和Regev提出的电路要求每个量子操作都可以正确使用算法。但是，在真实机器上，无错误的量子门是不可行的。

他们使用一种技术克服了此问题来滤除损坏结果，仅处理正确的结果。

最终结果是一个明显更高的记忆效率的电路。另外，他们的错误校正技术将使算法更实用。

Regev补充说：“作者在早期的量子保理算法中解决了这两个最重要的瓶颈。尽管仍然不立即实用，但他们的工作使量子保理算法更接近现实。”

将来，研究人员希望使其算法更加有效，并有一天使用它来测试在实际量子电路上的保理。

“这项工作之后的大象在室内问题是：它实际上是否使我们更接近打破RSA密码学？这还不清楚；目前这些改进只有当整数大得多时才大于2,048位，我们才能推动此算法并使Shor比Shor更可行，甚至比Shor更为可行。拉加万说。

这项工作由Akamai总统奖学金，美国国防高级研究项目局，国家科学基金会，MIT-IBM Watson AI实验室，Thornton家庭教师研究创新奖学金和Simons研究员奖的资助。