A Quantum Scaling Algorithm for Maximum-Weight Perfect Matching in General Graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.39457
curl -X POST /api/v1/records/arxiv/2609.39457/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.39457/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'