4 月公布的一项结果扩大了量子计算机的成功领域。
Quanta 杂志的 Kristina Armitage
1994 年，一位数学家想出了如何让量子计算机完成普通经典计算机无法做到的事情。这项工作表明，原则上，基于量子力学规则的机器可以有效地将大量数字分解为其主要因素——对于经典计算机而言，这是一项非常困难的任务，它构成了当今大部分互联网安全的基础。
随之而来的是一股乐观情绪。也许，研究人员认为，我们将能够发明量子算法来解决大量不同的问题。
但进展停滞不前。卡内基梅隆大学的Ryan O’Donnell说：“这有点令人失望。” “人们会说，‘这太棒了，我相信我们会得到各种其他令人惊叹的算法。’没有。”科学家们仅在称为 NP的标准集中发现了一个单一的、狭窄的问题类别的显着加速，这意味着他们有有效的可验证解决方案——例如因式分解。
这一结果使西蒙能够确定量子计算机在哪些方面具有显着优势的最初迹象之一。但是当他将他的论文提交给一个主要会议时，它被拒绝了。然而，这篇论文确实引起了会议计划委员会的一位初级成员——彼得·肖尔的兴趣，他当时在新泽西州的贝尔实验室工作。 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 将其与进行数据压缩时出现的不同情况进行了比较：当信息被压缩时，两个位可能会意外地挤入同一个位置，从而覆盖它们。提前预测这些碰撞以便避免它们的问题有一些相似之处。 “这是一类基本上看起来像这样的问题，”他说。 “也许这些问题可以在量子上解决。”
人们希望，即使在当今刚刚起步的量子计算机版本上，像新问题这样的非结构化问题也可以解决，从而提供一种测试它们的方法。当时的想法是，非结构化问题可能需要更少的资源来编程，或者对噪声不太敏感，因为它们已经是随机的。但到目前为止，对于现有的量子计算机来说，这个新问题似乎仍然太先进了，无法解决。 “这是一个奇怪的问题。我没想过要定义它，”亚伦森说。 “但回想起来，它有一些非常好的功能。”
该结果提供了第一个在非结构化 NP 问题上具有显着量子优势的例子。量子世界会不会有许多其他问题从实际上无法解决变成可以解决？现在有更多的理由这么认为。
“这在一定程度上颠覆了我们对量子计算机擅长解决哪些问题的看法，”奥唐奈说。
原文： https://www.quantamagazine.org/quantum-algorithms-conquer-a-new-kind-of-problem-20220711/