⚛️ 量子物理

Polynomial-Space Quantum Algorithms from Classical Branching: Colouring, Domination and Monotone Local Search

本文提出了一种无需量子随机存取存储器（quantum random access memory）的多项式空间量子算法，通过利用经典分支技术和一种新型的量子单调局部搜索形式，显著改善了包括图着色、支配问题以及单调局部搜索任务在内的多种 NP 难问题的指数时间界限。

原作者： Sebastian Senge

发布于 2026-11-10

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Sebastian Senge

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一个这样的世界：解决一个复杂的谜题需要逐一检查每一种可能的排列组合。对于许多涉及网络、地图或调度的问题，其排列组合的数量如此庞大，以至于即使是最快的超级计算机也需要花费比宇宙年龄还要长的时间才能找到答案。这就是指数级时间问题的领域，在这种领域中，难度增长得极其迅速，仅仅增加几个项目就会让任务突然变得无法完成。几十年来，计算机科学家们一直接受这样一个事实：即某些问题无论使用多么巧妙的方法，都无法快速解决。然而，一种新的方法正在改变这一格局，它展示了量子计算机——通过利用亚原子世界的奇特规则运行——如何在不需要在内存中存储每一条路径的情况下，比经典计算机更快速地穿梭于这些庞大的可能性之林。

核心挑战在于我们如何寻找解决方案。在经典计算机中，寻找解决方案的过程往往感觉就像是在一个巨大的、分支繁多的迷宫中行走。你选择一条路径，撞到死胡同，然后必须退回到上一个选择点，尝试另一条路线。如果迷宫有数十亿个分支，这个过程将耗费极长的时间。量子计算机提供了另一种穿梭迷宫的方式。它们不是一次走一条路径，而是可以同时探索许多路径，利用一种技术来“感知”正确的出口，从而更快地找到它。这项新研究表明，对于一类特定且重要的问题——包括地图着色、寻找网络中的高效节点组或删除图中的特定部分以修复结构——即使在内存非常有限的情况下，也可以实现这种量子加速。研究人员构建的算法运行在多项式空间内，这意味着它们不需要存储搜索的完整历史，这是对实用量子设备的一个关键约束。

该论文重点讨论了三种在计算机科学和数学中频繁出现的各类问题。第一种是图着色问题，它询问是否可以用有限数量的颜色为一张地图着色，使得两个相邻区域的颜色不同。第二种涉及支配问题，即寻找网络中能够“监视”或连接到所有其他点的最小点集。第三类问题包括必须移除一些特定元素以打破环路或修复结构的问题，例如寻找删除最少数量的顶点以消除网络中所有回路的方法。针对每种问题，研究人员采用了现有的最优已知经典算法（这些算法虽然已经很快，但仍需指数级时间），并将其适配于量子计算机。他们之所以能做到这一点，是因为他们证明了这些经典算法的逐步逻辑构成了一种特定类型的树状结构。这种结构允许量子计算机使用“量子行走”来寻找解，其所需时间大约是经典计算机所需时间的平方根。

结果显示，解决这些问题所需的时间得到了显著降低。对于经典的四色问题，新算法找到解的时间与顶点数 $n$ 的 $1.3032^n$ 成正比。这比之前最好的量子估计值 $1.3231^n$ 有了明显的改进。对于需要更多颜色的问题（如五色或多达十八色），新方法始终优于旧有的极限，且随着颜色数量的增加，所需时间增长得更为缓慢。对于支配问题，改进效果更为惊人。寻找支配集的所需时间从之前的约 $1.4969^n$ 降至 $1.2235^n$ ，而寻找独立支配集的时间则降至 $1.1583^n$ 。这些数字看起来可能很抽象，但在指数级增长的世界里，底数的微小减少意味着在大规模网络中实际计算时间的巨大节省。

研究人员还将这种逻辑应用于一种称为单调局部搜索的技术，该技术用于处理那些从部分解开始并尝试将其扩展为完整解的问题。通过将此技术与量子搜索相结合，他们创造了一种新方法，用于解决诸如寻找删除最少顶点以打破图中所有环路等问题。对于这个特定问题，新的量子时间约为 $1.3081^n$ ，这代表了该方法已知的第一个量子界限，因为此前尚未提出过任何单调局部搜索的量子形式。或许最有趣的是，团队展示了这种方法不仅适用于寻找完美的精确解，也适用于寻找“足够好”的近似解。例如，他们展示了一种寻找顶点覆盖问题解的方法，其结果仅比完美答案大 10%，但寻找它的时间与 $1.0555^n$ 成正比。这比寻找精确解更快，为现实应用中通常只需要近乎完美答案的情况提供了实用的权衡。

这项工作的关键方面是对内存的严格限制。这些算法被设计为以多项式空间运行，这意味着随着问题的增大，它们所需的内存增长速度是可控的。这是一个至关重要的约束，因为目前的及近未来的量子计算机将无法拥有其他依赖“量子随机存取存储器”的理论量子算法所要求的海量内存。通过避开这一需求，研究人员为那些真正存在的硬件开辟了一条路径。他们通过数学证明和计算机模拟验证了结果，检查了算法在随机图上的表现是否正确，以及时间估算是否经得起审查。这项工作并不声称解决了这些问题使其变得容易，而是推向了可能性的边界，展示了量子机器可以如何以一种此前被认为需要比可行内存更多的效率，来应对这些困难的指数级时间谜题。

这些发现的影响超出了具体的数值本身。这项研究建立了一个清晰的蓝图，展示了如何将现有的、高度优化的经典算法转化为量子版本，而不损失其效率或要求不可能实现的资源。它表明，对于广泛的难题，获得量子优势的路径可能不需要发明全新的数学理论，而是需要仔细重新设计我们在搜索空间中的移动方式。随着量子硬件的不断发展，这些多项式空间算法为这些机器能实现的目标提供了具体的目标。这项工作证实了这种加速是真实且可衡量的，让我们得以窥见这样一个未来：届时，目前对经典计算机而言难以处理的问题，只要我们能制造出运行这些特定、高效内存路径的机器，便有可能迎刃而解。

技术摘要：基于经典分支算法的多项式空间量子算法

问题陈述
本研究旨在为图与集合上的指数级时间组合问题设计量子算法，特别关注 $k$ -着色（ $k$ -Colouring）、支配问题（Domination problems）以及单调局部搜索（Monotone Local Search）变体。这些算法在严格的约束下运行：必须具有有界误差、仅使用多项式空间，并且至关重要的是，不利用量子随机存取存储器（QRAM）。目标是在该特定模型下，改进此前依赖于经典算法归约或通用搜索技术的已知最佳量子时间复杂度。

方法论
核心方法论利用了这样一个观察结果：许多针对 NP-困难问题的有效经典精确算法在结构上表现为回溯树（backtracking trees）。本文将 [31] (Montanaro) 的量子行走算法应用于这些树。如果一个经典算法探索一棵拥有 $T$ 个节点的搜索树，量子行走可以在 $O(\sqrt{T} \cdot \text{poly}(n))$ 的时间内判定是否存在标记叶节点（即解），且仅需多项式空间。

该方法包含三个主要技术组成部分：

树验证（Tree Verification）： 证明特定的经典分支算法（源自 [43], [45], [33], [34], [7] 等）可以被视为回溯树，且其节点数被限制在 $c^n$ 以内（其中 $c$ 为某个基数）。
量子加速（Quantum Speedup）： 将经典运行时间 $O(c^n)$ 应用平方根加速，得到量子时间 $O(c^{n/2})$ 。
针对 $k$ -着色的递归评估： 对于 $k \ge 6$ 的 $k$ -着色问题，本文利用了 [36] 的归约框架。通过使用带有安全余量的浮点数评估来替换精确最大值，从而计算控制运行时间的递归关系。这使得构建具有经过验证的时间复杂度的显式量子过程成为可能。
单调局部搜索（Monotone Local Search）： 本文将“单调局部搜索”范式 [17] 扩展到量子领域。它将针对随机样本的振幅放大与针对扩展算法回溯树的量子行走相结合。如果经典扩展问题的树规模为 $c^k$ ，则产生的量子运行时间为 $(2 - 1/c)^{n/2}$ 。

主要贡献与结果

$k$ -着色：
- 4-着色： 本文表明，将 [43] 中的多项式空间分支算法与 [45] 中的终止算法结合，构成了一个回溯树。这产生了 $O(1.3032^n)$ 的量子时间，优于此前最佳的 $O(1.3232^n)$ [36]。仅使用 [43] 则可实现 $O(1.3100^n)$ 。
- $k \ge 5$ ： 通过使用新的 3-着色和 4-着色基准情况来评估 [36] 的递归，作者为 $k \in \{5, 7, \dots, 18\}$ 提供了改进的量子时间界限。例如，5-着色问题的求解时间从 $O(1.4695^n)$ 降至 $O(1.4518^n)$ ，18-着色问题为 $O(1.9233^n)$ 。这些指数是通过带有余量的浮点运算得出的，以确保其严谨性。
支配问题：
- 作者证明了关于支配集（Dominating Set）、独立支配集（Independent Dominating Set）、**边支配集（Edge Dominating Set）以及最小极大匹配（Minimum Maximal Matching）**的经典分支归约算法的判定版本均为回溯树。
- 支配集： 从 $O(2^{n/2})$ [42] 改进至 $O(1.2235^n)$ 。
- 独立支配集： 改进至 $O(1.1583^n)$ 。
- 边支配集 / 最小极大匹配： 改进至 $O(1.1501^n)$ 。
- 这些结果依赖于 [33, 34, 7, 24] 中建立的经典基数的平方根。文中指出，虽然存在更快的经典算法（例如 [24] 针对支配集），但它们的结构并不属于本文所使用的回溯树框架；如果它们属于该框架，将会产生更快的量子界限。
单调局部搜索：
- 引入了一种单调局部搜索的量子形式。如果扩展问题具有规模为 $c^k$ 的回溯树，则子集问题以 $(2 - 1/c)^{n/2}$ 的复杂度解决。
- 精确界限： 这为反馈顶点集（Feedback Vertex Set）（ $O(1.3081^n)$ ）、簇顶点删除（Cluster Vertex Deletion）（ $O(1.2033^n$ ）、3-击中集（3-Hitting Set）（ $O(1.2405^n$ ）、适当区间顶点删除（Proper Interval Vertex Deletion）（ $O(1.3541^n$ ）、树上多切口（Multicut on Trees）（ $O(1.1647^n)$ ）以及 Min-Ones $d$ -SAT（ $O((2-1/d)^{n/2})$ ）带来了改进。
- 近似算法： 该框架被扩展到指数时间近似算法。例如，**顶点覆盖（Vertex Cover）**的 1.1-近似在 $O(1.0555^n)$ 内实现，反馈顶点集在 $O(1.2161^n)$ 内实现。这些界限严格低于相同问题的量子精确算法界限。

意义与主张
本文在多项式空间、无 QRAM 模型下，为这些特定问题提供了量子算法，改进了已知的量子界限（如支配集的 $O(2^{n/2})$ ），并在适用时改进了已知最佳基于回溯树的经典算法的平方根。

严谨验证： 作者强调， $k \ge 6$ 的指数不仅是理论极限，也是一个显式算法的运行时间上界。这些数值是使用远超舍入误差的浮点算术计算得出的，并使用 Lean 定理证明器验证了特定的不等式。
范围限定： 作者明确指出，其结果适用于可以建模为回溯树的算法。作者指出，涉及在调用尾部调用之前计算子部分最优解（例如某些 3-击中集算法）或多元局部搜索形式的更快经典算法并不在本文框架的覆盖范围内。因此，量子改进是相对于符合回溯树模型的特定经典算法而言的。
近似算法的新颖性： 本文强调，在此之前尚未有人针对此类问题的指数时间近似提出专门设计的量子算法。所提供的近似界限是该模型中的首创。

这项工作充当了桥梁，展示了在多项式空间、无 QRAM 模型下，通过量子行走的平方根加速，经典多项式空间分支算法的改进如何直接转化为改进的量子算法。

类似论文