量子计算新突破：密码学迎来大考
然而，量子计算机则有潜力能够快速破解传统计算机可能永远无法解决的复杂密码系统。这可能会基于1994年由彼得·肖尔（现为麻省理工学院教授）提出的量子分解算法实现。
尽管过去30年研究人员在该领域取得了巨大进展，但科学家们仍未建造出足够强大的量子计算机来运行肖尔的算法。
一些研究人员正在努力建造更大的量子计算机，而另一些研究人员则尝试改进肖尔的算法，以便它可以在较小的量子电路上运行。大约一年前，纽约大学计算机科学家OdedRegev提出了一项重大理论改进。他的算法运行速度更快，但需要更多内存。
基于这些研究结果，麻省理工学院的研究人员提出了一种结合了Regev算法运行速度和肖尔算法内存效率的折中方法。这个新算法与Regev的算法一样快，但需要的量子构件（称为量子比特）更少，并且对量子噪声的容忍度更高，这可能使其在实际中更容易实现。
从长远来看，这种新算法可能为开发能够抵抗量子计算机破解能力的全新加密方法提供指导。
该论文的主要作者是麻省理工学院电子工程与计算机科学系的研究生SeyoonRagavan。这项研究将在2024年国际密码学会议上发表。
为了通过互联网安全地传输信息，电子邮件客户端和消息应用等服务提供商通常依赖于一种名为RSA的加密方案，该方案由麻省理工学院的RonRivest、AdiShamir和LeonardAdleman于上世纪70年代发明（因此得名“RSA”）。该系统基于这样一个想法：分解一个2048位的整数（一个617位的数字）对于计算机来说在合理时间内太难完成。
然而，在1994年，肖尔在贝尔实验室工作时提出了一个算法，证明量子计算机可以快速分解，从而打破RSA加密。
据估计，一台量子计算机大约需要2000万个量子比特才能运行肖尔的算法。而目前，最大的量子计算机大约只有1100个量子比特。
量子计算机通过量子电路执行计算，就像经典计算机使用经典电路一样。每个量子电路由一系列称为量子门的操作组成，这些量子门利用量子比特（量子计算机最小的构件）进行计算。
但量子门会引入噪声，因此减少量子门的数量可以提高机器的性能。研究人员一直在努力改进肖尔的算法，以便它可以在较小的电路上运行，使用更少的量子门。
这正是Regev在一年前提出的电路所做的。肖尔提出的量子电路的大小与所分解数字的平方成正比。这意味着如果要分解一个2048位的整数，电路将需要数百万个量子门。
Regev的电路需要更少的量子门，但它需要更多的量子比特来提供足够的内存，而这带来了一个新的问题。
为了分解一个非常大的数字，量子电路需要多次运行，执行涉及计算幂次的操作，如2的100次方。但是，计算如此大的幂次在量子计算机上成本高昂且难以执行，因为量子计算机只能执行可逆操作。而平方一个数字不是一个可逆操作，所以每次进行平方计算时，必须增加更多的量子内存来计算下一个平方。
麻省理工学院的研究人员找到了一种巧妙的方法，通过使用一系列斐波那契数进行幂次计算，这只需要简单的乘法操作，而乘法是可逆的。他们的方法只需要两个量子内存单元来计算任何幂次。
他们还解决了纠错问题。通过使用一种技术过滤掉错误的结果并仅处理正确的结果，克服了这个问题。
最终结果是一个更节省内存的电路。此外，他们的纠错技术使该算法更具实用性。
未来，研究人员希望使他们的算法更加高效，并有朝一日在真实的量子电路上测试分解。
这项研究得到了Akamai总统奖学金、美国国防部预先研究计划局、国家科学基金会、麻省理工学院—IBM沃森人工智能实验室、Thornton家族教员研究创新奖学金以及西蒙斯研究员奖的资助。（麻省）