量子核算新打破：密码学迎来大考
（来历：MIT News）
你最近发送的电子邮件很或许是运用一种经典加密办法进行加密的，这种办法根据这样一个主意：即使是最快的核算机也无法高效地将一个巨大的数字分化成因数。
可是，量子核算机则有潜力能够快速破解传统核算机或许永久无法处理的杂乱暗码体系。这或许会根据 1994 年由彼得·肖尔（现为麻省理工学院教授）提出的量子分化算法完结。
虽然曩昔 30 年来研讨人员取得了巨大发展，但科学家们仍未制作出满足强壮的量子核算机来运转肖尔的算法。
一些研讨人员正在尽力制作更大的量子核算机，而另一些研讨人员则测验改善肖尔的算法，以便它能够在较小的量子电路上运转。大约一年前，纽约大学核算机科学家 Oded Regev 提出了一项严重理论改善。他的算法运转速度更快，但需求更多内存。
根据这些研讨成果，麻省理工学院的研讨人员提出了一种结合了 Regev 算法速度和肖尔算法内存功率的折中办法。这个新算法与 Regev 的算法相同快，但需求更少的量子构件（称为量子比特），而且对量子噪声的容忍度更高，这或许使其在实践中更简略完结。
从长远来看，这种新算法或许为开发能够反抗量子核算机破解才干的全新加密办法供给辅导。
“假如大规模的量子核算机终究被制作出来，那么分化算法就失效了，咱们有必要找到其他的加密办法。但这真的会是个要挟吗？咱们能让量子分化算法变得有用吗？咱们的研讨或许让咱们离有用化更近了一步，”福特基金会工程学教授、核算机科学与人工智能实验室（CSAIL）成员兼该论文的资深作者 Vinod Vaikuntanathan 说。
该论文的首要作者是麻省理工学院电子工程与核算机科学系的研讨生 Seyoon Ragavan。这项研讨将在 2024 年世界暗码学会议上宣布。
破解暗码学
为了经过互联网安全地传输信息，电子邮件客户端和音讯运用等服务供给商一般依赖于一种名为 RSA 的加密方案，该方案由麻省理工学院的 Ron Rivest、Adi Shamir 和 Leonard Adleman于上世纪 70 时代创造（因而得名“RSA”）。该体系根据这样一个主意：分化一个 2048 位的整数（一个 617 位的数字）关于核算机来说在合理时间内太难完结。
可是，在 1994 年，肖尔在贝尔实验室作业时提出了一个算法，证明量子核算机能够快速分化，然后打破 RSA 加密。
“那是一个转折点。但在 1994 年，没人知道怎么制作满足大的量子核算机。而咱们现在还远远没有完结这一方针。有些人乃至置疑它们是否真的会被制作出来。”Vaikuntanathan 说。
据估计，一台量子核算机大约需求 2000 万个量子比特才干运转肖尔的算法。而现在，最大的量子核算机大约只要 1100 个量子比特。
量子核算机经过量子电路履行核算，就像经典核算机运用经典电路相同。每个量子电路由一系列称为量子门的操作组成，这些量子门运用量子比特（量子核算机最小的构件）进行核算。
但量子门会引进噪声，因而削减量子门的数量能够进步机器的功能。研讨人员一直在尽力改善肖尔的算法，以便它能够在较小的电路上运转，运用更少的量子门。
这正是 Regev 在一年前提出的电路所做的。
“这是一个大新闻，由于这是自 1994 年肖尔提出的电路以来的初次真改善。”Vaikuntanathan 说。
肖尔提出的量子电路的巨细与所分化数字的平方成正比。这意味着假如要分化一个 2048 位的整数，电路将需求数百万个量子门。
Regev 的电路需求明显更少的量子门，但它需求更多的量子比特来供给满足的内存，而这带来了一个新的问题。
“从某种意义上说，有些类型的量子比特就像苹果或橙子。假如你长期保存它们，它们会衰减。你期望尽量削减需求保存的量子比特的数量。”Vaikuntanathan 解说说。
他在上一年 8 月的一个研讨会上听到了 Regev 的讲座。在讲座结束时，Regev 提出了一个问题：有人能改善他的电路以削减所需的量子比特吗？Vaikuntanathan 和 Ragavan 接受了这个应战。
量子乒乓
为了分化一个非常大的数字，量子电路需求屡次运转，履行触及核算幂次的操作，如 2 的 100 次方。
可是，核算如此大的幂次在量子核算机上本钱昂扬且难以履行，由于量子核算机只能履行可逆操作。而平方一个数字不是一个可逆操作，所以每次进行平方核算时，有必要添加更多的量子内存来核算下一个平方。
麻省理工学院的研讨人员找到了一种奇妙的办法，经过运用一系列斐波那契数进行幂次核算，这只需求简略的乘法操作，而乘法是可逆的。他们的办法只需求两个量子内存单元来核算任何幂次。
“这有点像乒乓球竞赛，咱们从一个数字开端，然后在两个量子内存寄存器之间来回弹跳进行乘法运算。”Vaikuntanathan 弥补道。
他们还处理了纠错问题。肖尔和 Regev 提出的电路要求每个量子操作都有必要是正确的，算法才干正常作业，Vaikuntanathan 说。但在实在机器上完结无误的量子门是不行行的。
他们经过运用一种技能过滤掉过错的成果并仅处理正确的成果，克服了这个问题。
终究成果是一个明显更节约内存的电路。此外，他们的纠错技能使该算法更具有用性。
“作者处理了之前量子分化算法中的两个最重要瓶颈。虽然依然不行有用，但他们的作业让量子分化算法更挨近实际。”Regev 弥补道。
未来，研讨人员期望使他们的算法愈加高效，并有朝一日在实在的量子电路上测验分化。
“在这项作业之后，不行忽视的问题是：这是否真的让咱们更挨近破解 RSA 加密？现在还不清楚；这些改善现在只要在整数远大于 2048 位时才会闪现作用。咱们能否推进这个算法，使其比肖尔的算法在分化 2048 位整数时更具可行性？”Ragavan 说。
这项研讨得到了 Akamai 总统奖学金、美国国防高档研讨方案局、国家科学基金会、麻省理工学院-IBM 沃森人工智能实验室、Thornton 宗族教员研讨立异奖学金以及西蒙斯研讨员奖的赞助。
原文链接：
https://news.mit.edu/2024/toward-code-breaking-quantum-computer-0823