量子算法征服了一种新的题目

编辑 | 白菜叶

1994 年，一位数学家想出了如何让量子计算机完成普通典范计算机无法做到的事情。这项工作表明，原则上，一台基于量子力学规则的机器可以无效地将大量数字分解为其主要因素——对于典范计算机而言，这是一项非常困难的任务，它构成了当今大部分互联网安全的基础。

随之而来的是一股乐观情绪。也许，研讨职员认为，我们将能够发明可以办理大量不同题目的量子算法。

但进展停滞不前。「这有点令人失望。」卡内基梅隆大学的 Ryan O’Donnell 说，「人们会说，『这太棒了，我相信我们会得到各种其他惊人的算法』，事实是没有。」 科学家们仅在称为 NP 的标准集中发觉了单一、狭窄类别题目的显着加速，这意味着他们有无效的可验证办理方案——例如因式分解。

近三年来都是如此。然后在 4 月，研讨职员发明了一种全新的题目，量子计算机应该能够比典范计算机更快地办理该题目。它涉及仅基于其混乱的输入来计算复杂数学过程的输入。这个题目是单独存在的，还是许多其他题目中的第一个题目尚待决定。

「有一种兴奋感。」麻省理工学院的计算机科学家 Vinod Vaikuntanathan 说，「很多人都在思考外面还有什么。」

计算机科学家试图通过研讨代表它们的数学模型，来了解量子计算机在哪些方面做得更好。通常，他们想象一个量子或典范计算机的模型与称为预言机的理想计算机配对。预言机就像简单的数学函数或计算机程序，接受输入并输入预定的输入。

它们可能具备随机行为，如果输入在某个随机范围内（例如，12 到 67）输入「是」，否则输入「否」。或者它们可能是周期性的，因此 1 到 10 之间的输入返回「是」，11 到 20 产生「否」，21 到 30 再次产生「是」，依此类推。

假设您有这些周期性预言之一，但您不知道周期。你所能做的就是给它输入数字，看看它输入了什么。在这些限制条件下，计算机能以多快的速度找到周期？1993 年，当时在蒙特利尔大学的 Daniel Simon 发觉，量子算法可以比任何典范算法更快地计算出密切相关题目的答案。

这一结果使 Simon 能够决定量子计算机在哪些方面具备显着上风的最初迹象之一。但是当他将他的论文提交给一个主要会议时，它被拒绝了。然而，这篇论文确实引起了会议项目委员会的一名初级成员——Peter Shor 的兴趣，他当时在新泽西州的贝尔实验室工作。

Shor 继续发觉他可以调整 Simon 的算法来计算预言机的周期，如果它有的话。然后他意识到他可以再次调整算法，求解一个行为类似于周期性预言的方程：描述因式分解的方程，它是周期性的。

Shor 的结果是历史性的。他发觉的量子算法可以迅速将巨大的数字简化为它们的组成素因数，这是任何已知的典范算法都无法做到的。在随后的几年里，研讨职员发觉了其他无效的量子算法。其中一些，比如 Shor 的算法，甚至提供了指数上风，但没有人能证明在任何非周期性的 NP 题目上具备显着的量子上风。

由于缺乏进展，德克萨斯大学奥斯汀分校的 Scott Aaronson 和拉脱维亚大学的 Andris Ambainis 两位计算机科学家进行了观察。量子上风的证明似乎总是依赖于具备某种非随机结构的预言，例如周期性。2009 年，他们推测随机或非结构化的 NP 题目不会有显着的加速；谁也找不到例外。

他们的猜想限制了量子计算机的能力。但它只说对于特定类型的非结构化 NP 题目——那些回答是或否的题目——没有显着的加速。如果一个题目涉及找出更具体、定量的答案，也就是所谓的搜索题目，那么这个猜想就不适用了。

考虑到这一点，NTT 社会信息学实验室的研讨职员 Takashi Yamakawa 以及 NTT Research 和普林斯顿大学的 Mark Zhandry 决定对一个由 Oded Regev 于 2005 年提出的特定搜索题目进行试验。

想象一组都指向同一个标的目的的风向标。给他们每个人一个有节制的推，然后让阵风影响他们的标的目的。Regev 想根据他们的最终标的目的决定他们最初指向的位置。像这样的题目后来被称为「错误学习」，因为推力和风就像是原始标的目的上的随机误差源。有证据表明，典范算法和量子算法都很难办理。

Yamakawa 和 Zhandry 调整了设置。他们修改了这些起跑的力量，使它们更容易预测。他们还使风由一个随机的神谕决定，因此在某些情况下它甚至更加随机，但在其他情况下则完全休眠。

通过这些修改，研讨职员发觉量子算法可以无效地找到初始标的目的。他们还证明，任何典范算法都必须以指数因子变慢。与 Shor 一样，他们随后调整了算法来办理题目的现实版本，用实际的数学方程代替了预言。

计算机科学家仍在努力理解和办理这个题目。Vaikuntanathan 将其与进行数据压缩时出现的不同情况进行了比较：当信息被压缩时，两个位可能会意外地挤到同一个地方，从而覆盖它们。提前预测这些碰撞以便避免它们的题目有一些相似之处。「这是一类基本上看起来像这样的题目。」他说，「也许这些题目可以在量子上办理。」

人们希望，即使在当今刚刚起步的量子计算机版本上，像新题目这样的非结构化题目也可以办理，从而提供一种测试它们的方法。当时的想法是，非结构化题目可能需要更少的资源来编程，或者对噪声不太敏感，因为它们已经是随机的。但到目前为止，对于现有的量子计算机来说，这个新题目似乎仍然太先进了，无法办理。「这是一个奇怪的题目。我没想过要定义它。」Aaronson 说，「但回想起来，它有一些非常好的功能。」

该结果提供了第一个在非结构化 NP 题目上具备显着量子上风的例子。量子世界会不会有许多其他题目从几乎无法办理变为可以办理？现在有更多的理由这么认为。

「这在一定程度上颠覆了我们对量子计算机擅长办理哪些题目的看法。」O’Donnell 说。

相关报道：https://www.quantamagazine.org/quantum-algorithms-conquer-a-new-kind-of-problem-20220711/