研究人员提出了一种用于加密的更小 更耐噪声的量子分解电路

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

另一方面，量子计算机有望快速破解传统计算机可能永远无法破解的复杂密码系统。这一前景基于彼得·肖尔 (Peter Shor) 于 1994 年提出的量子因式分解算法，肖尔现在是麻省理工学院的教授。

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

一些研究人员致力于建造更大的量子计算机，而另一些人则试图改进 Shor 算法，使其能够在更小的量子电路上运行。大约一年前，纽约大学计算机科学家 Oded Regev 提出了一项重大的理论改进。他的算法可以运行得更快，但电路需要更多的内存。

基于这些结果，麻省理工学院的研究人员提出了一种两全其美的方法，将 Regev 算法的速度与 Shor 算法的内存效率相结合。这种新算法与 Regev 算法一样快，需要的量子构建块(称为量子位)更少，并且对量子噪声的容忍度更高，这使得它在实践中更可行。

从长远来看，这种新算法可以为开发能够抵御量子计算机密码破译能力的新型加密方法提供参考。

“如果大规模量子计算机真的被建造出来，那么因式分解就完蛋了，我们必须找到其他东西用于加密。但这种威胁有多大?我们能让量子因式分解变得实用吗?

“我们的工作可能让我们更接近实际实施，”福特基金会工程学教授、计算机科学与人工智能实验室 (CSAIL) 成员、描述该算法的论文的高级作者 Vinod Vaikuntanathan 说。

该论文的主要作者是麻省理工学院电气工程与计算机科学系研究生 Seyoon Ragavan。这项研究在 2024 年国际密码学会议(Crypto 2024)上进行了展示。

标签：

版权声明：本文由用户上传，如有侵权请联系删除！