{"id":"arxiv/2609.39457","url":"https://arxiv.org/abs/2609.39457","tags":["cs.DS","quant-ph"],"score":0,"title":"A Quantum Scaling Algorithm for Maximum-Weight Perfect Matching in General Graphs","domain":"cs.DS","source":"arxiv","authors":["Kourosh Mirsohi","Sandy Irani","Michael T. Goodrich"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}