arXiv:2609.39457
A Quantum Scaling Algorithm for Maximum-Weight Perfect Matching in General Graphs
Kourosh Mirsohi, Sandy Irani, Michael T. Goodrich
Abstract
Quantum speed-ups have been obtained for many fundamental graph problems, including most variants of matching. A notable exception, however, is the maximum-weight perfect matching (MWPM) problem in general graphs with integer edge weights, which is arguably the most challenging variant of matching. We present a quantum algorithm for MWPM in general graphs that runs in $\widetilde{O}(n m^{2/3}\log W)$ time, where $W$ is an upper bound on the magnitude of the edge weights. This is an improvement over the best known classical combinatorial bound of $\widetilde{O}(m\sqrt n \log W)$ in the dense regime, where $m\ge n^{3/2}$. To the best of our knowledge, this is the first quantum algorithm to obtain an asymptotic improvement over the best classical combinatorial algorithm for the MWPM problem in general graphs. The running time of our method accounts for QRAM initialization and access overheads up to polylogarithmic factors, as well as all classical updates to the data structures. At a high level, our algorithm is based on a classical framework due to Duan, Pettie, and Su, but our algorithm requires replacing certain classical tasks with quantum methods, alternative analysis of classical procedures, and the use of alternative data structures that can be implemented effectively in the QRAM model.
AI Summary
The paper studies exact maximum-weight perfect matching in general graphs with integer edge weights, addressing a variant for which no quantum speedup over the best classical combinatorial bound was previously known. For a simple graph admitting a perfect matching, with $n$ vertices, $m$ edges, and weight magnitudes bounded by $W$, it gives a quantum algorithm running in $\widetilde{O}(nm^{2/3}\log W)$ time. Compared with the classical combinatorial bound $\widetilde{O}(m\sqrt n\log W)$, this is an asymptotic improvement when $m=\omega(n^{3/2})$; for $m=\Theta(n^2)$, the bounds are $\widetilde{O}(n^{7/3}\log W)$ and $\widetilde{O}(n^{5/2}\log W)$, respectively. The algorithm adapts the Duan–Pettie–Su weight-scaling framework. Grover/BBHT searches accelerate augmenting-path discovery and blossom detection, reducing a repeated search routine from $\widetilde{O}(m)$ to $\widetilde{O}(\sqrt{mn})$. Searches operate on the original graph rather than explicitly maintaining its blossom contraction. Vertex-indexed blossom labels, union-by-size updates, and ordered-DFS invariants support correctness and runtime analysis. A revised analysis of classical small-blossom liquidation, combined with threshold $\tau=m^{1/3}$, yields the overall bound. Search amplification gives success probability at least $1-n^{-c}$ for any fixed constant $c>0$. The runtime assumes QRAM with coherent reads and includes graph loading and classical data-structure updates. The advantage is restricted to dense graphs and comparison with classical combinatorial algorithms. Priority-queue-driven searches remain classical bottlenecks; accelerating them and extending the approach to approximate weighted matching are stated open directions.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 41 pages, 6 figures, 3 tables