想象一下，你和一些朋友一起参观一个迷宫。你进入后不久就从出口出来了，然后等待了几个小时你的朋友才出来。很自然地，他们会问你走的路——你肯定可以原路返回并向他们展示路线，对吧？
但在一个由量子物理学奇怪定律支配的世界里，情况并非如此。二十年前，量子计算研究人员开发了一种算法，利用这些定律以比在普通经典计算机上运行的任何算法快得多的速度遍历一种特定的数学迷宫。但这种加速是有代价的：快速量子算法找到了出口，但不知道它是如何到达那里的。
研究人员长期以来一直想知道这种权衡是否不可避免。真的不可能在不忘记路径的情况下快速找到出口吗？
关于支持科学新闻
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道 订阅。通过购买订阅，您正在帮助确保有关塑造我们今天世界的发现和想法的具有影响力的故事的未来。
“你甚至需要问这个问题，这真是令人难以置信，” 马里兰州盖瑟斯堡国家标准与技术研究所的计算机科学家 Matthew Coudron 说。
去年 11 月，Coudron 和两位同事朝着解决这个长期存在的问题迈出了一大步：他们 证明，在广泛而自然的快速量子算法类别中，没有任何算法可以找到通过特殊迷宫（称为焊接树图）的路径。结果表明，任何假设的非盲目猜测的寻路算法都必须暂时失去对入口的跟踪，才有成功的机会。看来遗忘是不可避免的。
“我绝对想不到他们竟然能证明这一点，”巴黎国家科学研究中心计算机科学基础研究所的量子计算研究员 Simon Apers 说，并补充说，这一结果“对于说明量子算法能做什么和不能做什么非常有用”。
量子提升
量子计算机的能力部分归功于一种称为叠加的现象，这种现象实际上使它们能够同时探索经典计算机需要单独考虑的许多选项。但这 并没有那么简单，就像同时执行多个计算以节省时间一样。检查选择叠加的结果永远不会揭示结果的叠加——相反，你只会获得一个可能的结果，每个结果都有不同的概率。量子算法依赖于这样一个事实，即对这些概率的贡献可以像池塘表面的波浪一样相互干扰，从而提高获得正确答案的概率，同时降低获得其他每个结果的概率。
由于干涉必须恰到好处地发挥作用，因此并非每个计算任务都适合量子加速，事实上，在量子计算首次被提出几十年后，研究人员仍在研究量子算法可以在哪里提供帮助。但他们取得了一些显著的成功。1994 年，Peter Shor 开发了一种量子算法，用于分解大数——这项任务对于经典计算机来说显然很困难，是现代密码学的基础。Shor 的算法可以快速分解非常大的数字，以至于所有已知的经典算法实际上都将变得毫无用处。
1996 年，计算机科学家 Lov Grover 找到了第二个潜在的实际例子：一种量子算法，用于解决非常通用的搜索问题，类似于在许多相同的盒子中找到隐藏的单个物品。
“在经典方法中，你可以做的就是随机尝试一个，看看它是否好，然后再试一次，看看它是否好，然后你一直尝试，直到找到一个好的元素，”Apers 说。这种方法花费的时间与盒子的数量成正比。将该数字乘以 100，搜索速度将慢 100 倍。
使用量子算法，你可以做得更好。Grover 证明，如果你设置所有盒子的叠加，你可以利用干涉实际上保证算法最终会选择正确的盒子。整个过程花费的时间与盒子数量的平方根成正比：将该数字增加 100 倍只会将运行时间增加 10 倍。
Grover 的算法非常简单地说明了量子叠加的价值，但它实现的加速相对适中——远远超出最佳经典算法范围的任务也会难倒 Grover 的算法。Shor 的分解算法让人们看到了量子计算机和经典计算机能力之间巨大的鸿沟。是否存在 Grover 搜索问题的变体，它像分解一样——对于经典计算机来说实际上是棘手的，但对于量子计算机来说却很容易？
在 20 世纪 90 年代后期，研究人员开始探索这个问题，将其重新表述为关于图的问题——由点或节点组成的网络，由称为边的线连接。任何搜索问题都可以用图论的语言来表达，其中一个节点代表起点，另一个节点代表目的地，边代表沿途每一步的可能选择
例如，Grover 的问题对应于搜索一个图中每个节点都连接到每个其他节点的图（因为你可以按任何顺序打开盒子）。给定搜索问题的不同经典算法相当于一次探索相应图的一个节点的不同策略，而量子算法可以沿多个边以叠加方式移动。
分支扩展
2002 年，一个计算机科学家团队最终确定了一个经典棘手的搜索问题，量子算法可以轻松解决。他们从一个简单的图开始，称为树，其中每个节点发芽两条边，通向另外两个节点，每个节点又分裂成另外两个分支，依此类推。从单个“根”节点开始，树图分支多次，然后在称为“叶子”的最后一层节点中结束。该团队想象取两棵相同的树，并通过将它们定位为叶子彼此面对，然后使用随机过程将一棵树上的每个叶子连接到另一棵树上的两个叶子，从而将它们“焊接”在一起。然后他们提出了以下问题：从焊接树图的一个根开始，你能找到通往另一个根的路吗？
如果没有对图的鸟瞰图，任何尝试解决此搜索问题的经典算法在到达图的中间层后都会彻底迷失——所有边看起来都相同，并且无法区分指向前方的边和指向后方的边。算法可能会意外地偶然发现出口节点，但它花费在徘徊上的平均时间会随着树中层数的增加呈指数增长。
2002 年论文的作者证明，一种简单的量子算法——一种通过叠加许多路径在图中均匀传播的“量子游走”——可以更快地找到通往出口的路。这是因为焊接树图的对称布局导致路径之间发生干涉，从而将流量集中在向前方向。拉脱维亚大学的计算机科学家 Alexander Belov 说，出口节点“就像算法的焦点”。
这种量子游走算法很有可能在与层数成正比的时间内收敛到出口。这使其比任何经典算法都快得多——加速效果与 Shor 的分解算法相当。但是，导致量子加速的干涉也消除了算法在其通往出口的路径上遍历的所有记录。
研究人员想知道是否有可能兼得鱼和熊掌——一种快速算法，可以识别从入口到出口的路径。
“如果仅仅是基本的量子游走以某种方式找到出口，那就行不通，”马里兰大学帕克分校的计算机科学家 Andrew Childs 说，他作为研究生与人合著了 2002 年的论文，并与 Coudron 合作研究了新成果。“但也许你可以以某种方式改进它。”
改进它
最早着手解决这个问题的人之一是 Ansis Rosmanis，他现在是名古屋大学数学研究生院的计算机科学家。在 2010 年的一篇论文中，Rosmanis 开发了一类他称为“量子蛇形游走”的算法，这些算法使用关于它们去过哪里的记忆来补充标准的量子游走算法。
当标准量子游走算法在图中流动时，它的下一步完全取决于它当前所处的位置——它是如何到达那里的并不重要。相比之下，在 Rosmanis 的蛇形游走中，你需要知道过去才能预测未来。具体而言，蛇形游走的演变由“蛇”决定，蛇是游走先前经过的相邻节点串。蛇形游走有很多种，其中在这些蛇的长度在游走过程中如何变化等方面存在差异。
Rosmanis 表明，尽管量子蛇形游走记住了它们的轨迹，但使用多条蛇的叠加的量子蛇形游走仍然可以表现出有益的干涉，并且某些蛇形游走原则上可以找到通往出口的路径。但他找不到一种特定的蛇形游走算法可以快速做到这一点，他也无法证明这种算法不存在。蛇形游走似乎很有希望，但太滑溜了，难以确定。Rosmanis 的工作是近十年来关于寻路问题的最后结论。
然后在 2019 年，Coudron 在不同的背景下遇到了焊接树图：他和一位同事证明，所有找到出口的量子游走算法都缺乏一种在已知可为其他问题产生指数级量子加速的算法中普遍存在的属性。该结果与寻路没有直接关系，但 Coudron 开始怀疑，使他能够证明关于所有焊接树图算法属性的这一概括性陈述的数学技术也可能有助于解决蛇形游走（或其他算法）是否可以找到路径的问题。在那年晚些时候搬到马里兰州后，他与 Childs 开始合作，希望能果断地解决这个问题。
Childs、Coudron 和他们的研究生 Amin Shiraz Gilani 首先做了两个假设来限制问题的范围。首先，他们决定忽略那些试图传送到图中随机点以期偶然发现出口的古怪算法。这种策略就像试图通过寻找漏洞来利用来击败电子游戏——技术上可能，但违背了问题的精神。也很难想象这种行为会有所帮助，因为在大图上，落在正确位置的几率变得微乎其微。忽略随机跳跃的算法使分析剩余的算法变得更容易，作者将这些算法称为“真正的”算法——这些算法包括 Rosmanis 的蛇形游走算法，以及可能还有其他人尚未发现的其他算法。
作者的第二个更实质性的假设是，快速寻路算法将保持“扎根”——也就是说，它将建立一条通往出口节点的路径，而永远不会丢失对入口的跟踪。许多蛇形游走是扎根的，但原则上，非扎根的蛇形游走可能会找到通往出口的路径——它必须从入口节点分离，然后在稍后找到入口和出口。
这三位研究人员证明，对于每个真正的扎根量子算法，他们都可以设计出一种经典算法来模拟其可观察的行为。由于他们还可以证明，没有经典算法可以快速找到出口，因此这足以排除这一大类可能的量子寻路算法。真正的扎根算法根本无法聚集足够的干涉来找到通过迷宫的路径。
前进的道路
新的结果不一定是故事的结局。“即使在研究量子算法相当长一段时间后，它们仍然让我感到惊讶，”米德尔伯里学院的计算机科学家 Shelby Kimmel 在一封电子邮件中写道。可能仍然存在研究人员考虑的类别之外的巧妙寻路算法，只是等待被发现。
虽然非真正的算法似乎极不可能奏效，但非扎根算法或许可以通过从中间某个位置开始构建从入口到出口的路径。“也许你可以将其设置为蛇进入并变得非扎根的方式，但随后不知何故决定伸展开来，”Childs 说。“这仍然没有排除。”
研究人员尚未找到 Childs 和他的同事 20 年前发现的指数级量子加速的实际应用，部分原因是它依赖于焊接树图的特殊对称性，而这种对称性不太可能存在于任何现实世界的网络中。但通常，了解量子算法不能做什么也具有同样的价值。Shor 发现了一种用于分解大数的快速量子算法，这威胁要破坏最先进的密码学，强调了需要已知对量子算法也很难的问题。
一种不受 Shor 算法攻击的密码学依赖于在特定图上难以找到点之间路径的假设。通过焊接树进行寻路的证据对于量子算法来说确实很困难，这可能会激励研究人员开发基于焊接树图的新密码协议，尽管他们到目前为止还没有取得任何成功。
“也许这意味着这个问题中存在的结构类型不适合编码我们关心的那些问题，”Childs 说。“或者也许你只需要以正确的方式看待它。”
经 Quanta 杂志 许可转载，西蒙斯基金会 的编辑独立出版物，其使命是通过报道数学以及物理和生命科学领域的研究进展和趋势来增强公众对科学的理解。阅读此处的原始文章。