其他
量子算法能做什么、不能做什么？
光子盒研究院
想象一下，你和几个朋友一起逛迷宫。你进去后不久就从出口出来了，等了好几个小时，你的朋友们才出现。自然而然，他们会问起你走过的路：你当然可以追溯你的脚步，给他们指路，对吗？
在一个由奇特的量子物理定律支配的世界里，情况并非如此。20 年前，量子计算研究人员开发出一种算法，利用这些定律穿越一种特定的数学迷宫，速度比在普通经典计算机上运行的任何算法都要快得多。但这种提速是有代价的：快速量子算法找到了出口，但却不知道它是如何到达那里的。
长期以来，研究人员一直在思考这种权衡是否不可避免。难道真的不可能在快速找到“出口”的同时又不忘记路径吗？
对此，美国国家标准与技术研究所的计算机科学家Matthew Coudron说：“你甚至需要问这个问题，这有点令人震惊。”
去年 11 月，Coudron和两位同事朝着解决这个长期存在的问题迈出了一大步：他们证明，在一类广泛而自然的快速量子算法中，没有一种算法能找到通过这种被称为“焊接树图(welded tree graph)”的特殊迷宫的路径。结果表明，任何不盲目猜测的假想路径寻找算法，都必须暂时失去对入口的追踪，才有可能成功。
看来，遗忘是不可避免的。
巴黎计算机科学基础研究所国家科学研究中心的量子计算研究员Simon Apers说：“我根本想不到他们真的能证明这一点。这一结果对于说明量子算法能做什么和不能做什么非常有用。”
量子计算机的强大部分归功于一种被称为“叠加（superposition）”的现象，这种现象使量子计算机能够同时探索经典计算机需要单独考虑的许多选项。但这并不像同时进行多项计算以节省时间那么简单。检查叠加选择的结果永远不会发现结果的叠加；相反，只能得到可能结果中的一个，而每个结果都有不同的概率。
量子算法所依赖的事实是，对这些概率的贡献可以像池塘表面的波浪一样相互干扰，从而提高得到正确答案的概率、降低其他结果的概率。
事实上，在量子计算首次提出数十年后，研究人员仍在研究量子算法在哪些方面可以提供帮助；现在，他们已经取得了一些显著的成功。1994 年，Peter Shor开发了一种量子算法，用于对大数进行因式分解——对于经典计算机来说，这项任务显然是困难的，而这正是现代密码学的基础。Shor算法可以快速地对大数进行因式分解，以至于所有已知的经典算法实际上都毫无用处。
1996 年，计算机科学家Lov Grover发现了第二个可能实用的例子：一个非常通用的搜索问题的量子算法，这个问题类似于寻找藏在许多相同盒子中的一件物品。
我们可以这样理解量子算法的功效：从经典上讲，我们可以做的只是随机尝试一个，看看它是否好，然后再试一次，看看它是否好，一直试下去......直到找到一个好的元素。这种方法花费的时间与黑盒的数量成正比。将这个数字乘以 100，搜索速度就会减慢 100 倍。
有了量子算法，我们可以做得更好。Grover证明，如果设置了所有盒子的叠加，我们就可以利用干扰来实际保证算法在最后选择正确的盒子。整个过程所需的时间与盒子数量的平方根成正比；将方框数增加 100 倍，运行时间将只增加 10 倍。
Grover算法非常简单地诠释了量子叠加的价值，但它所实现的速度提升却相对有限：那些最好的经典算法都无法完成的任务，Grover算法也同样难以完成。Shor的因式分解算法让人们看到了量子计算机和经典计算机能力之间的巨大差距。Grover搜索问题的变种是否也像因式分解一样，对经典计算机来说几乎难以解决，而对量子计算机来说却轻而易举？
20 世纪 90 年代末，研究人员开始探索这个问题，并将其重新表述为一个关于图的问题：由被称为边的线连接起来的点或节点组成的网络。任何搜索问题都可以用图论语言来表述，一个节点代表起点，另一个节点代表终点，而边则代表沿途每一步的可能选择。
例如，Grover问题就相当于搜索一个图，在这个图中，每个节点都与其他节点相连（因为可以按照任意顺序打开盒子）。针对给定搜索问题的不同经典算法相当于每次探索相应图中一个节点的不同策略，而量子算法可以沿着多条“边”叠加移动。
2002 年，一组计算机科学家终于发现了一个量子算法可以轻松解决的经典难解搜索问题。他们从一个叫做“树”的简单图形入手，在这个图形中，每个节点都会产生两条边，分别通向另外两个节点，而每个节点又会分裂成另外两个分支，如此循环。从一个“根”节点开始，树形图会多次分支，最后形成一层被称为“叶子”的节点。研究小组设想将两棵完全相同的树“焊接”在一起，方法是将树叶朝向对方，然后使用随机过程将一棵树上的每片树叶连接到另一棵树上的两片树叶上。
然后，他们提出了以下问题：从焊接树图的一个树根开始，能找到通往另一个树根的路吗？
如果没有图的鸟瞰图，任何试图解决这一搜索问题的经典算法在到达图的中间层后都会无望地迷失方向：所有的边看起来都是一样的，根本无法区分那些指向前方的边和指向后方的边。算法可能会意外地发现出口节点，但它四处游荡的平均时间会随着树的层数呈指数增长。
2002 年论文中，作者证明，一种简单的量子算法：一种通过在叠加中走许多路径来均匀地在图中扩散的“量子随机游走算法”可以更快地找到出口。这是因为焊接树图的对称布局会导致路径之间产生干扰，从而使流量集中在前进方向。
——出口节点“就像算法的焦点”。
这种量子行走算法很有可能在与层数成正比的时间内收敛到出口。这使得它比任何经典算法都要快上数倍：速度堪比Shor的因式分解算法。但是，导致量子提速的干扰也抹去了算法在到达出口时经过路径的所有记录。
研究人员不禁要问，是否有某种方法可以两全其美？是否有一种快速算法可以识别从入口到出口的路径？
Ansis Rosmanis是最早着手解决这个问题的人之一，他是一名计算机科学家，现就职于名古屋大学数学研究生院。在 2010 年的一篇论文中，Rosmanis开发了一类算法，他将其称为“量子蛇行(quantum snake walks)”，这种算法为标准量子行走算法提供了补充，并能记住它们曾经走过的地方。
当标准量子行走算法在图中流动时，它的下一步完全取决于当前所处的位置——它是如何到达那里的并不重要。相比之下，在Rosmanis的蛇行算法中，我们需要知道“过去”才能“预测”未来。但他找不到一种具体的蛇行算法能快速找到出口，而且他也无法证明这种算法不存在。蛇行似乎很有前途，但又太复杂，难以确定。
Rosmanis的工作是近十年来路径寻找问题的最后定论。
在 2019 年，Coudron 在不同的背景下遇到了焊接树图：他和一位同事证明，所有找到出口的量子随机游走都缺乏一种在已知能对其他问题产生指数量子加速的算法中普遍存在的特性。这一结果与路径寻找并无直接关系，但Coudron 开始怀疑，让他能够证明这一关于所有焊接树图算法特性的概括性声明的数学技术，也可能有助于解决蛇行（或其他算法）能否找到路径的问题。
当年晚些时候搬到马里兰州后，他与Childs建立了合作关系，希望能彻底解决这个问题。
Childs、Coudron 和他们的研究生Amin Shiraz Gilani首先提出了两个假设来限制问题的范围。首先，他们决定忽略那些试图传送到图中随机点以偶然发现出口的“离奇算法(outlandish algorithm)”。这种策略就像试图通过四处寻找漏洞来打败电子游戏一样：技术上也许可行，但却违背了问题的精神。而且很难想象这种行为会有什么帮助，因为在大型图上，找到正确位置的几率变得微乎其微。忽略那些随机跳来跳去的算法，可以更容易地分析剩下的算法：这些算法包括Rosmanis的蛇行算法，或许还有其他尚未被发现的算法。
作者的第二个更实质性的假设是，快速寻路算法会保持 “扎根(rooted)”状态，也就是说，它会建立一条通往出口节点的路径，而不会失去对入口的追踪。许多蛇行都是有根的，但原则上，无根的蛇行也有可能找到通往出口的路径：它必须从入口节点脱离，然后再同时找到入口和出口。
三位研究人员证明，对于每一种真正有根的量子算法，他们都能创造出一种经典算法，模仿其可观察到的行为。由于他们也能证明没有一种经典算法能快速找到出口，这足以排除这一大类可能的量子寻路算法。
真正的扎根算法(rooted algorithm)根本无法产生足够的干扰来找到通过迷宫的路径。
新成果并不一定是故事的终结。
即使研究量子算法已经有相当长的时间了，它们仍然不断给我带来惊喜。在研究人员所考虑的类别之外，可能还有一种巧妙的寻路算法，正等待着我们去发现。
例如，研究人员尚未发现Childs和他的同事们在 20 年前发现的指数量子提速技术的实际应用，部分原因是它依赖于焊接树图的特殊对称性，而这种对称性在现实世界的任何网络中都不太可能存在。但是，了解量子算法无法做到的事情往往同样有价值。
Shor发现了一种快速的大数因式分解量子算法，这种算法有可能破坏最先进的密码学。
一种不受Shor算法影响的密码学依赖于这样一个假设：在特定图形上很难找到点之间的路径。有证据表明，通过焊接树图寻找路径对量子算法来说确实很难，这可能会促使研究人员基于焊接树图开发新的加密协议——尽管他们迄今为止还没有任何收获。
Childs说：“也许这意味着这个问题中的那种结构并不适合我们关心的编码问题。或者，也许你只需要用正确的方法来看待它。”
参考链接：[1]https://www.quantamagazine.org/to-move-fast-quantum-maze-solvers-must-forget-the-past-20230720/[2]https://arxiv.org/abs/2211.12447[3]https://journals.aps.org/pra/abstract/10.1103/PhysRevA.83.022304