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

arXiv:2609.39457 · cs.DS, quant-ph · Submitted 2026-09-30 · Read on arXiv

cs.DS, quant-ph

Submitted: 2026-09-30

Updated: 2026-09-30

Terminology

• Quantum Random Access Memory — 6× in this paper
• Query Complexity — 5× in this paper · explained in 2 episodes
• Adaptation — 2× in this paper · explained in 1 episode
• Combinatorial Optimization — 2× in this paper · explained in 2 episodes
• Trace — 2× in this paper · explained in 2 episodes
• Adjacency Matrix — 1× in this paper · explained in 1 episode
• IEEE Symposium on Foundations of Computer Science — 1× in this paper
• Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms — 1× in this paper

Sources

• Scaling Algorithms for Weighted Matching in General Graphs

Related papers

• Cascaded Learned Bloom Filter for Optimizing Model-Filter Size Balance and Fast Rejection
• Edge-Private Matching Kernels Through Local Decoding
• Local Node Differential Privacy
• Cheaper by the Batch: Shared Traversal for Genotype Graph Editing
• Scalable Algorithms for Approximate DNF Model Counting
• On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions