1994年，一位数学家想出了如何让量子计算机做普通经典计算机做不到的事情。这项工作表明，原则上，基于量子力学规则的机器可以有效地将大数分解为它们的主要因素——这对于构成当今互联网安全基础的经典计算机来说是一项非常艰巨的任务。随之而来的是一股乐观情绪。研究人员认为，也许我们将能够发明能够解决大量不同问题的量子算法。但进展停滞不前。“这有点令人失望，”卡内基梅隆大学的瑞安奥唐奈说。“人们说，‘这太棒了，我相信我们会得到各种其他令人惊叹的算法，’但事实并非如此。”科学家们仅在称为NP的标准集中发现了单一、狭窄类别的问题的显着加速，这意味着他们拥有有效的可验证解决方案——例如因式分解。这种情况已经持续了将近三年。然后在4月，研究人员发明了一种全新的问题，量子计算机应该能够比传统计算机更快地解决这个问题。它涉及仅根据其混沌输出来计算复杂数学过程的输入。这个问题是孤立的，还是许多其他问题中的第一个，还有待确定。“有一种兴奋感，”麻省理工学院的计算机科学家VinodVaikuntanathan说。“很多人都在想外面有什么。”更好的。通常，他们想象一个量子或经典计算机的模型与一个称为oracle的理想计算机配对。预言机就像简单的数学函数或计算机程序，它们接受输入并输出预定的输出。它们可能具有随机行为，如果输入在某个随机范围内（例如，12到67），则输出“是”，否则输出“否”。或者它们可以是周期性的，因此1到10之间的输入返回yes，11到20返回no，21到30再次返回yes，依此类推。假设您有这些周期性神谕之一，但您不知道周期。你所能做的就是给它输入数字，然后看看它输出什么。鉴于这些限制，计算机能以多快的速度找到周期？1993年，当时在蒙特利尔大学的丹尼尔·西蒙(DanielSimon)发现，量子算法可以比任何经典算法更快地计算出密切相关问题的答案。这一结果使西蒙能够确定量子计算机可以在哪些方面具有显着优势的最初迹象之一。但当他将论文提交给一个重要会议时，却被拒绝了。然而，这篇论文确实引起了会议程序委员会初级成员PeterShor的兴趣，他当时在新泽西州的贝尔实验室工作。Shor继续发现他可以调整Simon的算法来计算oracle的周期，如果它有的话。然后他意识到他可以再次调整算法来求解一个表现得像周期性神谕的方程：一个描述因式分解的方程，它是周期性的。Shor的结果具有历史意义。他发现的量子算法可以快速将巨大的数字简化为构成它们的质因数，这是任何已知的经典算法都无法做到的。在随后的几年里，研究人员发现了其他有效的量子算法。其中一些算法，如Shor算法，甚至提供指数优势，但没有一个能够在任何非周期性NP问题中展示显着的量子优势。由于缺乏进展，得克萨斯大学奥斯汀分校的ScottAaronson和拉脱维亚大学的AndrisAmbainis两位计算机科学家看了一下。量子霸权的证明似乎总是依赖于具有某种非随机结构的神谕，例如周期性。2009年，他们推测随机或非结构化NP问题不会有明显的加速；谁也找不到例外。他们的猜想限制了量子计算机的能力。但它只是说对于特定类型的非结构化NP问题——那些答案为是或否的问题——没有显着的加速。如果问题涉及寻找更具体、定量的答案（称为搜索问题），则此猜想不适用。考虑到这一点，NTT社会信息学实验室的研究人员TakashiYamakawa以及NTTResearch和普林斯顿大学的MarkZhandry决定对OdedRegev在2005年提出的一个特定搜索问题进行实验。想象一组风向标都指向同一方向。给他们每个人一个有节制的推动，让阵风影响他们的方向。Regev想要根据他们的最终方向确定他们最初指向的位置。像这样的问题后来被称为“错误学习”，因为推力和风在原始方向上的作用就像随机误差源。有证据表明经典算法和量子算法都难以求解。Yamakawa和Zhandry调整了设置。他们修改了这些起始力，使它们更容易预测。他们还让风由随机神谕决定，因此在某些情况下它甚至更加随机，但在其他情况下则完全处于休眠状态。通过这些修改，研究人员发现量子算法可以有效地找到初始方向。他们还证明，任何经典算法都必须呈指数级变慢。像Shor一样，他们随后采用算法来解决问题的现实版本，用实际的数学方程式代替oracle。计算机科学家仍在努力理解和解决这个问题。Vaikuntanathan将此与压缩数据时发生的不同情况进行了比较：压缩信息时，两个位可能会意外挤入同一位置，从而覆盖它们。在提前预测这些碰撞以避免它们的问题上有一些相似之处。“这是一类基本上看起来像这样的问题，”他说，“也许这些问题可以用量子来解决。”希望即使在今天刚刚起步的量子计算机上，也可以解决新问题文化化问题等非结构化问题，从而提供一种测试方法。当时的想法是，非结构化问题可能需要更少的编程资源，或者对噪音不那么敏感，因为它们已经是随机的。但到目前为止，对于现有的量子计算机来说，这个新问题似乎仍然过于先进，无法解决。“这是一个奇怪的问题。我没想过要定义它，”Aaronson说，“但现在回想起来，它有一些非常好的特性。”量子霸权的一个例子。量子世界还会有许多其他问题，从几乎无法解决到可解决吗？现在有更多的理由这么认为。“这颠覆了我们对量子计算机擅长解决哪些问题的看法，”奥唐奈说。
