最近发送的电子邮件很可能是用一种可靠的方法加密的，这种方法依赖于这样一种想法:即使是最快的计算机也无法有效地将一个巨大的数字分解成因子。
另一方面，量子计算机有望快速破解传统计算机可能永远无法破解的复杂密码系统。这一前景基于1994年由Peter Shor提出的量子因子分解算法，Peter Shor现在是麻省理工学院的教授。
但是，尽管研究人员在过去30年里取得了巨大的进步，但科学家们还没有制造出一台足够强大的量子计算机来运行肖尔的算法。
当一些研究人员致力于建造更大的量子计算机时，另一些研究人员一直在试图改进肖尔的算法，使其能够在更小的量子电路上运行。大约一年前，纽约大学计算机科学家Oded Regev提出了一个重大的理论改进。他的算法可以运行得更快，但电路需要更多的内存。
在这些结果的基础上，麻省理工学院的研究人员提出了一种两全其美的方法，将Regev算法的速度与Shor算法的内存效率结合起来。这种新算法与Regev的算法一样快，需要更少的量子构建块(称为量子位)，并且对量子噪声具有更高的容忍度，这可能使其在实践中更可行。
从长远来看，这种新算法可以为开发新的加密方法提供信息，这些方法可以承受量子计算机的密码破解能力。
“如果大规模量子计算机建成，那么分解就完蛋了，我们必须找到其他东西来用于密码学。”但这种威胁有多真实?我们能使量子因子分解成为现实吗?我们的工作可能会让我们离实际应用更近一步，”福特基金会工程学教授、计算机科学与人工智能实验室(CSAIL)成员、一篇描述该算法的论文的资深作者维诺德·瓦伊昆塔纳坦说。
这篇论文的主要作者是Seyoon Ragavan，他是麻省理工学院电子工程和计算机科学系的研究生。这项研究将在2024年国际密码学会议上发表。
破解密码
为了在互联网上安全地传输信息，电子邮件客户端和消息传递应用程序等服务提供商通常依赖于RSA，这是麻省理工学院研究人员罗恩·里vest、阿迪·沙米尔和伦纳德·阿德勒曼在20世纪70年代发明的一种加密方案(因此得名“RSA”)。该系统基于这样一种想法，即对2,048位整数(617位数字)进行分解对计算机来说在合理的时间内很难完成。
1994年，当时在贝尔实验室工作的肖尔引入了一种算法，证明量子计算机可以足够快地分解RSA密码，这一想法被颠覆了。
“那是一个转折点。但在1994年，没有人知道如何建造一台足够大的量子计算机。我们离那还很远。有些人想知道它们是否会被建造出来。”
据估计，一台量子计算机将需要大约2000万个量子比特来运行肖尔的算法。目前，最大的量子计算机大约有1100个量子比特。
量子计算机使用量子电路进行计算，就像经典计算机使用经典电路一样。每个量子电路由一系列称为量子门的操作组成。这些量子门利用量子比特来执行计算，量子比特是量子计算机最小的组成部分。
但是量子门会带来噪音，所以减少量子门会提高机器的性能。研究人员一直在努力改进肖尔的算法，使其能够在更小的电路上运行，拥有更少的量子门。
这正是雷格夫在一年前提出的电路中所做的。
“这是个大新闻，因为这是肖尔赛道自1994年以来第一次真正的改进，”瓦伊昆塔纳坦说。
肖尔提出的量子电路的大小与被分解的数字的平方成正比。这意味着如果要分解2,048位的整数，电路将需要数百万个门。
Regev的电路需要更少的量子门，但它需要更多的量子比特来提供足够的内存。这就提出了一个新问题。
“从某种意义上说，某些类型的量子比特就像苹果或橙子。如果你把它们放在身边，它们会随着时间的推移而腐烂。你想要最小化你需要保持的量子位的数量，”Vaikuntanathan解释说。
去年8月，他在一个研讨会上听到Regev谈论他的研究结果。在演讲结束时，雷格夫提出了一个问题:有人能改进他的电路，使其需要更少的量子比特吗?Vaikuntanathan和Ragavan回答了这个问题。
量子乒乓球
要分解一个非常大的数字，量子电路需要运行很多次，执行涉及计算能力的操作，比如2的100次方。
但是，在量子计算机上计算如此大的功率既昂贵又困难，因为量子计算机只能执行可逆操作。平方一个数字不是可逆的操作，所以每平方一个数字，就必须增加更多的量子内存来计算下一个平方。
麻省理工学院的研究人员发现了一种聪明的方法来计算指数，使用一系列斐波那契数，需要简单的乘法，这是可逆的，而不是平方。他们的方法只需要两个量子存储单元来计算任何指数。
“这有点像乒乓球游戏，我们从一个数字开始，然后来回反弹，在两个量子存储器寄存器之间相乘，”Vaikuntanathan补充道。
他们还解决了纠错的挑战。Vaikuntanathan说，Shor和Regev提出的电路要求每个量子运算都是正确的，这样他们的算法才能工作。但在真正的机器上，没有错误的量子门是不可行的。
他们使用一种技术来过滤掉损坏的结果，只处理正确的结果，从而克服了这个问题。
最终的结果是一个显著提高内存效率的电路。此外，他们的纠错技术将使该算法的部署更加实用。
“作者解决了早期量子分解算法中两个最重要的瓶颈。虽然还不能立即付诸实践，但他们的工作使量子分解算法更接近现实，”Regev补充道。
在未来，研究人员希望使他们的算法更有效，有一天，用它来测试一个真正的量子电路上的分解。
“在这项工作之后，一个显而易见的问题是:它真的能让我们更接近破解RSA密码吗?”这一点目前还不清楚;这些改进目前只在整数远远大于2048位时才会生效。我们能否推动这个算法，使它比肖尔的算法更可行，甚至对于2,048位的整数?”Ragavan说。
这项工作由Akamai总统奖学金、美国国防高级研究计划署、国家科学基金会、麻省理工学院- ibm沃森人工智能实验室、桑顿家族教师研究创新奖学金和西蒙斯研究员奖资助。
本文来自作者[admin]投稿，不代表飞流互动立场，如若转载，请注明出处：https://exlove.cn/zlan/202506-286.html
评论列表（4条）
我是飞流互动的签约作者“admin”！
希望本篇文章《破解密码的量子计算机》能对你有所帮助！
本站[飞流互动]内容主要涵盖：国足,欧洲杯,世界杯,篮球,欧冠,亚冠,英超,足球,综合体育
本文概览： 最近发送的电子邮件很可能是用一种可靠的方法加密的，这种方法依赖于这样一种想法:即使是最快的计算机也无法有效地将一个巨大的数字分解成因子。...