量子领域最具影响力的投研服务平台

滑动了解更多

30年间首次突破！Peter Shor回应“多维Shor算法”的速度提升

넳 넲

发布时间：2023-10-19

肖尔(Shor)算法将使未来的量子计算机能够快速计算大量数字，从而破坏许多在线安全协议。现在，一位研究人员展示了如何以更快的速度实现这一目标（欲知这一成果的详细信息，可参阅光子盒文章《30年来首次！Shor算法取得质的突破》）。

当时，彼得·肖尔(Peter Shor)的初衷并不是要破坏互联网。但他在20世纪90年代中期开发的一种算法却有可能做到这一点。在一篇具有里程碑意义的论文中，肖尔展示了如何利用量子物理学的“怪异性”，让一台假想的计算机以比任何普通经典机器都快得多的速度，将大数分解为质因数。

论文链接：

https://ieeexplore.ieee.org/document/365700

这一成果的影响远远超出了数学范畴。当时，互联网安全的一个重要组成部分——公钥密码学，依赖于这样一个假设：将大数分解成素数在计算上非常困难，实际上是不可能的。这一假设至今仍是一些关键协议的基础。肖尔的算法表明，在一个拥有强大量子计算机的世界里，这一算法将严重失效。

在过去的30年里，计算机科学家们对肖尔算法进行了精简，以迎接量子技术成熟到足以运行该算法的那一天。但是，纽约大学计算机科学家奥德·雷杰夫(Oded Regev)提出的一种新变体从根本上加快了这一进程：它首次改进了因式分解数字的大小与因式分解所需的量子运算次数之间的关系。

雷杰夫开发了一种多维版本的肖尔算法，运行速度更快

雷杰夫在纽约大学的个人网站：

https://cims.nyu.edu/~regev/

布里斯托尔大学量子计算研究员阿什利·蒙塔纳罗(Ashley Montanaro)评论道：“许多年后，显然有人能够改进这一结果的复杂性，这真的很了不起。这真是令人兴奋！”

瑞典国家通信安全局的密码学家马丁·埃克罗(Martin Ekerå)也认为雷杰夫的论文很有趣，但他提醒说，要在实践中超越现有技术水平，还需要进一步优化。他在一封电子邮件中写道：“肖尔的原始算法已经出奇地高效，因此要想做出重大改进并非易事。”

雷杰夫开发新算法的方法是，利用密码学分支中处理高维几何的技术来增强肖尔的算法。

量子计算机的威力来自其处理信息的特殊方式。经典计算机使用比特，每个比特必须始终处于两种状态之一，即0和1。量子比特可以处于0和1的组合状态，这种现象被称为叠加。还可以将多个量子比特“哄骗”到一个集体叠加态中：一个双量子比特叠加态有四个分量，可以同时进行不同的计算，随着量子比特数量的增加，这些分量的数量呈指数增长。这使得量子计算机可以有效地并行执行指数级的多种不同计算。

但有一个问题：读取叠加计算的结果只能显示一个随机分量计算部分的答案。要想获得叠加计算的好处，必须以某种方式将最终结果映射到一个更简单的状态上，这样才能安全地读取结果。这在大多数情况下是不可能的，起初没有人知道如何让它在任何问题上发挥作用。雷杰夫说：“当时只有极少数人有勇气去思考量子计算。”

互联网安全取决于将大数分解为质因数的计算难度。1994年，彼得·肖尔(Peter Shor)发现了一种可以快速分解大数因数的量子算法。

1994年，肖尔读到了计算机科学家丹尼尔·西蒙(Daniel Simon)的一篇论文，其中展示了如何利用量子叠加来解决一个假想的问题。肖尔想出了如何将西蒙的结果扩展到一个更普遍、更实用的问题上，这个问题被称为“周期查找”：当一个数学函数的输出随着输入的增加而反复循环相同的值时，这个函数就被称为周期函数；一个周期的长度被称为函数的周期。

要使用量子计算机找出给定函数的周期，首先要建立一个非常大的叠加，其中每个分量都要计算不同输入的函数输出。然后使用肖尔方法将该大型叠加转换为更简单的状态，并读取结果。这时，经典计算机就可以接手，快速完成计算。总体而言，肖尔的周期寻找算法比任何经典替代方法都要快上数倍，因为它可以利用叠加同时计算周期函数的不同输出。

在肖尔为他的量子周期查找算法寻找应用领域时，他重新发现了一个以前已知但晦涩难懂的数学定理：对于每一个数字，都存在一个周期函数，其周期与数字的质因数有关。因此，如果你想求一个数字的素因子，你可以计算出相应的函数，然后用周期查找法来解决问题。

——“这正是量子计算机所擅长的。”雷杰夫说。

在经典计算机上，这将是一种令人痛苦、缓慢方法，甚至比尝试所有可能的因数还要慢。但肖尔的方法却以指数级的速度加快了这一过程，使发现成为构建快速量子因式分解算法的理想方法。

肖尔的算法是早期的几项关键成果之一，它将量子计算从理论计算机科学的一个晦涩难懂的子领域转变为了今天的庞然大物。但将该算法付诸实践是一项艰巨的任务，因为量子计算机出了名的容易出错：除了执行计算所需的量子比特外，它们还需要许多其他的量子比特做额外的工作，以防止它们出错。Ekerå和谷歌研究员克雷格·吉德尼(Craig Gidney)曾估计，使用肖尔算法来计算一个安全标准的2048位数(约600位数长)，需要一台拥有2000万量子比特的量子计算机——而目前最先进的计算机最多只有几百个量子比特。

这就是为什么一些关键的互联网协议仍然依赖于大数因式分解的难度，但研究人员并不想过于自满。理论和技术创新可以进一步降低所需的量子比特数，而且也没有证据证明肖尔的算法是最优的：也许还有更好的量子因式分解算法，但没有人发现。

如果是这样，雷杰夫说，“我们应该尽早知道，以免为时已晚”。

雷杰夫的学术生涯始于20世纪90年代末，当时密码学家们正在寻找一种不受肖尔算法影响的新型公钥密码学。最有前途的方法被称为基于格的密码学，它依赖于涉及高维点阵或网格的计算问题的明显难度；其中一个问题类似于在森林中找到最靠近随机点的树。

加州大学戴维斯分校的数学家格雷格·库珀伯格(Greg Kuperberg)说：“如果是百维森林，那就比二维森林复杂得多。”

雷杰夫在博士后期间开始研究基于格的密码学，起初是作为攻击者：他想通过找到量子计算机可以利用的弱点来对新方法进行压力测试。但他没能取得任何进展，很快他就想知道这是否有更深层次的原因。2005年，他找到了一种方法，将这些失败的攻击转化为一种优于所有其他变体的基于格的密码学。

“奥德在格方面绝对是个天才。”库珀伯格说。

多年来，雷杰夫把肖尔算法教给了一代又一代的学生，他发现自己在想，他用来攻击基于格的密码学的技术是否真的能在因式分解算法中派上用场。这是因为，肖尔算法最后经典阶段的一个步骤相当于在一维网格中寻找最近的点。这个一维问题非常简单，但它与数百维度的类似问题的相似之处却显而易见，而数百维度的类似问题正是基于格的密码学的基础。

雷杰夫说：“如果你和我一样是研究格的人，你就会想，‘好吧，这里面肯定有什么格问题’。但我并不清楚如何利用这一点。”

多年来，他一直在“玩弄”新的量子因式分解算法的其他想法，但始终没有进展；去年冬天，他又回到了这个问题上，决心找出因式分解和基于格的密码学之间的诱人联系。

这一次，他成功了。

雷杰夫知道，他需要从将肖尔算法核心的周期函数从一维推广到多维开始。

在肖尔算法中，该函数涉及将一个随机数（称为g）与自身重复相乘。但是，这个函数的周期——在函数输出开始重复之前必须与g相乘的次数，可能非常大；这意味着量子计算机必须在它用来计算周期函数的叠加的某些成分中乘以大数：这些大乘法是肖尔算法中计算成本最高的部分。

类似的二维函数使用的是一对数字，即g1和g2。它需要将g1与自身相乘多次，然后再与g2相乘。这个函数的周期也是二维的：它由g1乘以和g2乘以的次数来定义，这两次乘以和g2乘以使函数的输出开始重复。有许多不同的g1和g2乘法组合可以实现这一目的。

雷杰夫通过技术细节将算法推广到任意维数，而不仅仅是两个维数，但他的初步结果并不令人鼓舞。要计算多个维度的周期函数，量子计算机仍然需要将许多数字相乘。每个数字不需要像在一维情况下那样被相乘很多次，但有更多不同的数字需要相乘。

整件事情似乎就是一场洗牌。

“你会想，‘太好了，我刚刚在高维情况下做了所有事情，运行时间和肖尔的完全一样’，”雷杰夫说：“我被这种想法困住了一段时间。”后来，他意识到可以通过改变乘法的顺序来解决这个问题。在量子计算的过程中，一个乘积会逐渐变大，他没有重复地将数字加到一个乘积上，而是从成对的小数字开始，将乘积相乘，然后继续向上运算。乘法的总数没有太大变化，但现在几乎所有乘法都涉及相对较小的数字，从而使计算速度更快。

起初，雷杰夫似乎只是用一个问题替换了另一个问题。他通过增加维数加快了周期函数的量子计算速度，但随后提取周期所需的经典计算现在类似于在高维空间中定位最近的格点：人们普遍认为这是一项艰巨的任务。与基于格的密码学的类比似乎注定了他的新方法会失败。

三月份一个寒冷的早晨，在前往普林斯顿大学参加研讨会之前，雷杰夫发现自己正在等与他拼车的同事。他说：“我早到了，他却迟迟没有来取车。就在他坐着等待的时候，最后一块拼图突然浮现在他眼前。就在那一刻，一切都水到渠成了，不过还得烘烤一段时间。”

这一切都归结于正确的维数。当晶格维数过低时，他的算法就无法充分利用小数乘法的加速优势；当维度过高时，量子计算速度很快，但经典部分却需要解决一个难得要命的晶格问题。

雷杰夫从一开始就知道，要想有成功的希望，他必须在两者之间进行努力，但他并不清楚是否存在一个“甜蜜点”。三月的那个早晨，他意识到如何调整算法的细节，使其在几十个维度中快速运行。

改进是深远的。当对一个n位数进行因式分解时，雷杰夫算法量子部分的基本逻辑步骤数为n^1.5，而不是肖尔算法中的n^2。该算法的量子部分要重复几十次，然后将结果组合起来，绘制出一个高维网格，从中可以推导出周期和因数。因此，整个算法可能不会运行得更快，但通过减少所需步骤的数量来加快量子部分的速度，可以使其更容易付诸实践。

当然，运行量子算法所需的时间只是几个考虑因素之一。同样重要的是所需的量子比特数，它类似于普通经典计算中存储中间值所需的内存。肖尔算法计算一个n位数的因数所需的量子比特数与n成正比，而雷杰夫算法的原始形式所需的量子比特数与n^1.5成正比，这对于2048位数来说是一个很大的差别。

在经典计算中，速度通常是比内存更重要的考虑因素，因为经典比特具有极高的鲁棒性：你可以将文件保存在电脑上，而不用担心以后再次打开时文件会随机改变；量子计算研究人员并不总是那么幸运。

吉德尼说：“我们的量子比特一直在试图分崩离析，而我们也在努力阻止它们分崩离析。”这就像你想在沙子上写字，风却把它吹走了。这意味着雷杰夫算法所需的额外量子比特可能是一个重大缺陷。

但雷杰夫的论文并不是故事的结尾。两周前，Vaikuntanathan和他的研究生Seyoon Ragavan找到了减少算法内存使用的方法。他们的雷杰夫算法变体与肖尔的原始算法一样，需要的量子比特数与n成正比、而不是 n^1.5。埃克洛在一封电子邮件中写道，这项工作“让我们更接近于在实践中更高效的实现”。