A Quantum Scaling Algorithm for Maximum-Weight Perfect Matching in General Graphs

技术摘要：一种针对一般图中最大权完美匹配的量子缩放算法

问题陈述
本文研究了一般无向图中具有整数边权的最大权完美匹配（MWPM）问题。给定一个具有 $n$ 个顶点、$m$ 条边且边权上限为 $W$ 的图 $G=(V, E)$，目标是找到一个使边权之和最大的完美匹配 $M$。虽然量子加速在许多图问题（如最短路径、最小生成树和二部图中的匹配）中已经得到实现，但在一般图中具有整数权重的 MWPM 问题仍然是一个显著的例外。其主要难点在于如何处理奇环（花朵/blossoms）以及在寻找增广路径的过程中维护复杂的数学结构（花朵的层级族和对偶变量）。目前已知的最优经典组合算法是由 Duan、Pettie 和 Su 提出的，其运行时间为 $\tilde{O}(m\sqrt{n} \log W)$。

方法论
作者提出了一种量子算法，在稠密区域（$m \ge n^{3/2}$）内改进了经典界限。该算法基于 Duan、Pettie 和 Su 的经典“LIQUIDATIONIST”框架，该框架利用了在 $O(\log W)$ 个尺度上的权重缩放方法。算法将工作划分为三个过程：

1. 小花朵清算（Small Blossom Liquidation）： 处理小型收缩子图。
2. 自由顶点归约（Free Vertex Reduction）： 通过寻找增广路径迭代减少自由顶点的数量。
3. 最终化（Finalization）： 在所有尺度处理完成后完成匹配。

核心创新在于将 自由顶点归约 过程替换为量子子程序 QSEARCHONE，同时保持其他过程为经典过程。该过程在每个尺度上执行 $\tau$ 次，其中 $\tau$ 是一个可调参数。

关键技术贡献

• QRAM 模型实现： 该算法在量子随机存取存储器（QRAM）模型下运行，允许在叠加态下相干地访问经典数据结构（邻接表、对偶变量、花朵结构）。这确保了输入加载和数据结构更新被计入运行时间中，避免了忽略输入访问成本的方法。
• 量子路径搜索（QUANTUMPATHSEARCH）： 作者将用于增广路径的 Gabow-Tarjan 深度优先搜索（DFS）适配到量子设置中。算法不是显式地构建并维护收缩图 $G/\Omega$（因为这代价过高），而是在原始图 $G$ 中进行搜索，同时维护一个 ROOTB 数组来追踪每个顶点所属的根花朵。
  • Grover 搜索： 算法使用 Grover 式搜索（具体为 BBHT 变体）来寻找当前 DFS 栈中相邻的符合条件的边。符合条件的判定标准（准则 2）取决于对偶变量和边权。
  • 处理花朵： 量子搜索通过处理“增长事件”（发现新顶点）和“花朵事件”（检测奇环）来工作，而无需显式构建收缩图。当形成花朵时，算法使用“按大小合并”策略来高效更新 ROOTB 数组，确保顶点的标签更新次数最多为 $O(\log n)$ 次。
• 经典过程的替代分析： 作者对 小花朵清算 过程进行了精细化分析。通过观察大小为 $\tau$ 的小花朵内部的边数至多为 $\tau^2$，他们推导出了该步骤更紧凑的界限 $\tilde{O}(n\tau^2 \log W)$，而非原有的 $\tilde{O}(\tau m \log W)$。
• $\tau$ 的优化： 总运行时间是 $\tau$ 的函数。作者通过优化该参数来平衡三个过程的成本。

结果
所提出的量子算法 QLIQUIDATIONIST 实现了如下运行时间：
$$\tilde{O}(nm^{2/3} \log W)$$
在 $m \ge n^{3/2}$ 的稠密区域内，这相对于已知最优的经典组合界限 $\tilde{O}(m\sqrt{n} \log W)$ 实现了渐近改进。

运行时间分解如下：

• 自由顶点归约： $\tilde{O}(\tau \sqrt{mn} \log W)$（相比于 $\tilde{O}(\tau m \log W)$ 实现了量子加速）。
• 小花朵清算： $\tilde{O}(n\tau^2 \log W)$（改进的分析）。
• 最终化： $\tilde{O}(\frac{nm}{\tau} \log W)$。
• 经典开销： $\tilde{O}(m \log W)$。

通过设置 $\tau = m^{1/3}$，主导项变为 $\tilde{O}(nm^{2/3} \log W)$。论文指出，对于 $m = \Theta(n^{3/2})$，量子和经典界限在渐近意义上是等价的，但当 $m = \omega(n^{3/2})$ 时，量子界限严格更好。

意义与声明
本文声称提出了第一个在一般图中针对 MWPM 问题获得优于最佳经典组合算法渐近改进的量子算法。作者强调，他们的方法不仅仅是利用 Grover 搜索进行的图遍历加速；它需要对经典数据结构进行重大修改（特别是处理花朵的层级族和对偶变量），并对经典算法的复杂度进行重新分析。

作者对其改进范围持谨慎态度，指出其加速效果仅限于稠密区域。他们指出，依赖于优先级队列驱动的 Edmonds 搜索（PQSEARCH）的 小花朵清算 和 最终化 步骤仍是剩余的瓶颈。他们表示，直接的 Grover 搜索无法轻易替代 PQSEARCH 的动态事件调度，因此设计用于事件管理的量子模拟器仍是一个开放性问题。因此，本文并不声称在所有 MWPM 领域都具有普适性的量子加速，而是针对稠密情况下的特定且可证明的改进。