A Quantum Scaling Algorithm for Maximum-Weight Perfect Matching in General Graphs
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 Õ(n m2/3log 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 Õ(m√n log W) in the dense regime, where m≥ n3/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.
Related
- Scalable quantum-enhanced greedy algorithm for the maximum independent set problems on random regular graphs
- Doubly-polylog-time-overhead fault-tolerant quantum computation by a polylog-time parallel minimum-weight perfect matching decoder
- Quantum algorithm for weakly correlated molecular electronic ground states with sub-quintic scaling in the system size
- Post-Quantum Perfect Zero-Knowledge Arguments for NP From Any One-Way Permutation
- Sharp bounds for perfect quantum state classification beyond antidistinguishability
BibTeX
@misc{mirsohi2026quantum,
title = {{A Quantum Scaling Algorithm for Maximum-Weight Perfect Matching in General Graphs}},
author = {Kourosh Mirsohi and Sandy Irani and Michael T. Goodrich},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.39457},
eprint = {2609.39457},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.39457},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Quantum Scaling Algorithm for Maximum-Weight Perfect Matching in General Graphs
AU - Kourosh Mirsohi
AU - Sandy Irani
AU - Michael T. Goodrich
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.39457
UR - https://arxiv.org/abs/2609.39457
AB - 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 Õ(n m^2/3log 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 Õ(m√n log W) in the dense regime, where m≥ 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.
ER -