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

1 Introduction

• General-graph matching searches can encounter odd cycles, which Edmonds’ algorithm handles by contracting odd vertex sets into blossoms.The blossoms form a nested, non-crossing family, and dual adjustment makes new useful edges available while preserving feasibility.Source: §1 · pp. 1–2

1.1 The Quantum Random Access Memory (QRAM) Model

• The QRAM model supports classical updates and quantum access in superposition; the running-time accounting includes graph loading and classical data-structure updates.The algorithm also requires modified data structures and procedures, rather than only Grover-style graph traversal.Source: §1.1 · p. 2

1.2 Main Result and Technical Contributions

• The LIQUIDATIONIST adapts Duan, Pettie, and Su’s MWPM algorithm [13] to QRAM and organizes the work into SMALL BLOSSOM LIQUIDATION, FREE VERTEX REDUCTION, and FINALIZATION.Only FREE VERTEX REDUCTION is accelerated; the other two procedures remain classical.Source: §1.2 · p. 3
• For integer weights, weight scaling reveals edge weights over O(log W) scales, after which FINALIZATION obtains an exact maximum-weight perfect matching.The scaling iterations include SMALL BLOSSOM LIQUIDATION and FREE VERTEX REDUCTION.Source: §1.2 · p. 3
• FREE VERTEX REDUCTION calls SEARCHONE τ times, reducing its per-call running time from O(m) classically to eO(√mn) on a quantum computer.The improved SEARCHONE running time is the key accelerated procedure in the algorithm.Source: §1.2 · p. 3
• For simple graphs, a different analysis bounds SMALL BLOSSOM LIQUIDATION by eO(nτ^2 log W) across the scaling iterations.The per-scale bound uses at most τ^2 internal edges per small blossom and at most O(n) total blossom vertices.Source: §1.2 · p. 3
• eO(nm^2/3 log W) improves on the eO(m√n log W) classical bound for m ≥ n^3/2, marking the paper’s first asymptotic quantum improvement for general-graph MWPM.The algorithm’s running time is minimized at τ = m^1/3.Source: §1 · p. 2, §1.2 · p. 3
• QSEARCHONE performs the tasks of classical SEARCHONE, including path augmentation, odd-cycle contraction, dual adjustment, and blossom dissolution, in eO(√mn) time.It searches the original graph and reconstructs the contracted-graph path using maintained blossom information.Source: §1.2 · p. 4

2.1 Blossom Basics

• Blossoms form a forest of nested vertex sets, and an augmenting path in the contracted graph connects free root blossoms by alternating matched and unmatched edges.Such a path lifts to an augmenting path in the original graph between the blossoms’ bases, while blossom-disjoint contracted paths lift to vertex-disjoint original paths.Source: §2.1 · pp. 4–5

2.2 The Primal-Dual Framework and Eligible Edges

• Across distinct root blossoms, Criterion 2 makes matched edges eligible when tight (y(u) + y(v) = w(u, v)) and unmatched edges eligible when almost tight (y(u) + y(v) = w(u, v) − 2).For these cross-root edges, the blossom dual contribution is zero, so eligibility can use y(u) + y(v) in place of the full dual expression.Source: §2.2 · p. 6

2.3 FREE VERTEX REDUCTION Procedure Overview

• QUANTUMPATHSEARCH adapts Gabow–Tarjan’s DFS augmenting-path search, using Grover search over an OUT vertex’s adjacency list to find an eligible unmatched edge.The procedure searches the original graph rather than explicitly constructing the contracted graph; it runs once per scale, and FREE VERTEX REDUCTION consists of τ SEARCHONE iterations.Source: §2.3 · pp. 6–9
• For a new odd cycle, the search creates a temporary blossom in a copied forest Ω′, updates ROOTB by relabeling all but the largest child, and discards the temporary changes afterward.This avoids pointer-following in a classical union-find structure, which cannot be incorporated into Grover search; each vertex’s ROOTB value is updated at most log n times.Source: §2.3 · pp. 7, 10, 11
• QUANTUMPATHSEARCH runs in eO(√mn) time while finding eligible, blossom-disjoint augmenting paths in the original blossom structure.The analysis bounds successful searches by 2n and uses the fact that an edge that becomes non-actionable cannot later become actionable between searches from the same vertex.Source: §2.3 · p. 11
• Task 3 reruns QUANTUMPATHSEARCH with the updated matching, retaining its blossoms rather than discarding them.Because Task 2 guarantees no augmenting path, Task 3 performs only grow steps, temporary blossom contractions, and backtracking; its final UIO labels and ROOTB map are retained for Task 4.Source: §2.3 · p. 12
• At Task 3 termination, every OUT vertex has been completely scanned, leaving no eligible edge to an UNLABELED vertex in a distinct root blossom.Every eligible OUT–OUT edge lies within one final root blossom and has already been absorbed by search-blossom contractions; Task 3 runs in ~O(√mn).Source: §2.3 · p. 12
• Tasks 4 and 5 use the same dual adjustment and blossom dissolution procedures as classical SEARCHONE, with a linear-time bound.A single traversal of all trees in Ω updates the entire ROOTB array when blossoms are dissolved.Source: §2.3 · p. 12
• QSEARCHONE correctly performs the classical SEARCHONE tasks and runs in ~O(√mn) time.The stated running-time analysis also bounds temporary blossom maintenance and changing IN vertices to OUT by O(n), with union-by-size overhead O(n log n).Source: §2.3 · p. 12

3 Proofs and Pseudocode for FREE VERTEX REDUCTION

• Persistent root blossoms correspond one-to-one with vertices of H and have well-defined labels, while DFS-created temporary blossoms remain local to the search.Source: §3 · p. 13

3.1 Proof of Correctness for Quantum Path Search

• Conditioned on correct GROVERSEARCH calls, QUANTUMPATHSEARCH returns pairwise H-blossom-disjoint eligible augmenting paths forming a maximal set.Each path can be lifted to the original graph in time linear in its expanded length.Source: §3.1 · pp. 13, 18
• Temporary blossom contractions preserve alternating reachability, allowing predecessor paths to be expanded along stored defining cycles into eligible augmenting paths in H.Nested temporary blossoms can be expanded recursively from the search-local blossom structure.Source: §3.1 · p. 13
• The correctness proof shows that every unscanned OUT vertex in the current search tree lies on the current H-blossom search path; after a free-root search, other OUT vertices are fully scanned.Source: §3.1 · p. 17

3.2 Proof for the Running Time of Quantum Path Search

• An incidence that is not actionable at one scan of an OUT vertex cannot become actionable before its next scan, since matching and dual variables remain fixed and contractions only merge search blossoms.These lemmas support the QUANTUMPATHSEARCH running-time bound of eO(√mn).Source: §3.2 · p. 19
• Maintaining root-blossom labels by union-by-size costs O(n log n), while maintaining defining cycles and changing IN vertices to OUT costs O(n).Union-by-size relabels each vertex at most floor(log2 n) times; defining-cycle lengths and monotone IN-to-OUT label changes total O(n).Source: §3.2 · p. 20

3.3 Augmentation

• After augmentation along maximal blossom-disjoint paths, no eligible augmenting path remains in G/Ω.The paths can be lifted to the original graph in time proportional to their total length, then used to update the matching.Source: §3.3 · p. 20

3.4 Task 3: Quantum Blossom Detection

• Task 3 reuses Algorithm 1 without modification, runs in eO(sqrt(mn)), and never reaches the augmenting-path output branch.Because the eligible contracted graph has no augmenting path, Ψ remains empty; newly created search blossoms are promoted at termination.Source: §3.4 · pp. 20, 22
• At Task 3 termination, every OUT vertex is scanned, with no eligible OUT-to-UNLABELED edge or cross-root-blossom OUT–OUT edge remaining.During the task, the predecessor structure is an alternating forest rooted at free blossoms, and each eligible OUT–OUT edge between distinct root blossoms has endpoints in the same tree.Source: §3.4 · p. 21

3.5 Dual adjustment and blossom dissolution

• Dual adjustment and dissolution of zero-z root blossoms take O(n) time.The adjustment and dissolution steps match classical SEARCHONE, and the ROOTB array can be updated by a linear-time traversal.Source: §3.5 · p. 22

3.6 Correctness and running time

• QSEARCHONE correctly performs the tasks of classical SEARCHONE and has total running time eO(sqrt(mn)).Path search and blossom detection each take eO(sqrt(mn)); dual adjustment and blossom dissolution take O(n).Source: §3.6 · p. 22

4.1 The QLIQUIDATIONIST Algorithm Overview

• The algorithm retains the classical LIQUIDATIONIST framework, implementing the complete FREE VERTEX REDUCTION through QSEARCHONE while leaving inherited-blossom processing, SMALL BLOSSOM LIQUIDATION, Perfection, and FINALIZATION classical.Conditioned on correct quantum searches, the resulting algorithm returns a maximum-weight perfect matching.Source: §4.1 · pp. 24–25

4.2 Running-time contributions

• An alternative analysis bounds total SMALL BLOSSOM LIQUIDATION time by eO(nτ^2 log W), compared with the original eO(τm log W) bound.This analysis enables optimization of τ for the full algorithm.Source: §4.2 · p. 25
• Each scale performs exactly τ QSEARCHONE calls for FREE VERTEX REDUCTION, with each call taking eO(√mn) time.These calls replace the classical SEARCHONE calls in this procedure.Source: §4.1 · p. 24, §4.2 · p. 26
• Classical bookkeeping and memory updates cost eO(m+n) per scale, including graph storage, weight updates, and updates to arrays later read coherently.The bound covers large-blossom liquidation, reweighting, and Perfection.Source: §4.2 · p. 27

4.3 Proof of the main theorem

• For simple graphs admitting a perfect matching with integer weights bounded by W, QLIQUIDATIONIST returns an MWPM with probability at least 1−n^-c in eO(nm^2/3 log W) time.The runtime is obtained by optimizing the running-time bound for the full algorithm.Source: §4.3 · pp. 27–28

5 Discussion and Open Problems

• Eligibility- and label-constrained adjacency-list scans in FREE VERTEX REDUCTION have explicit search spaces and local reversible predicates suited to Grover-style search.The surrounding routine can preserve its classical invariants.Source: §5 · p. 28
• PQSEARCH globally schedules competing events by priority, so direct Grover search over adjacency lists does not replace its minimum-key event mechanism.This explains why SMALL BLOSSOM LIQUIDATION and FINALIZATION remain classical.Source: §5 · pp. 28–29
• A quantum analogue of PQSEARCH event management could improve the current eO(m) cost and potentially enable MWPM speedups beyond the dense regime.The paper identifies this as its most immediate open problem.Source: §5 · p. 29

A.1 Classical algorithms on exact MWPM

• Edmonds’ blossom algorithm is a primal–dual method that maintains a feasible matching and dual variables, contracting odd cycles into blossoms when they obstruct augmentation.Dual adjustments preserve feasibility while creating tight edges.Source: §A.1 · p. 33
• For integer weights, weight scaling reveals edge weights gradually while maintaining a matching and dual solution satisfying approximate complementary slackness at each scale.Inherited blossoms must also be managed across scales.Source: §A.1 · p. 33
• Duan, Pettie, and Su’s LIQUIDATIONIST framework gives the current best exact combinatorial bound and organizes each scale around three procedures; this work replaces FREE VERTEX REDUCTION with a quantum-enhanced version.The procedures are SMALL BLOSSOM LIQUIDATION, FREE VERTEX REDUCTION, and FINALIZATION.Source: §A.1 · p. 33
• Algebraic methods use fast matrix multiplication for randomized exact algorithms polynomial in W and n^ω, and are structurally different from the combinatorial primal–dual approach.The passage describes them as most competitive in dense regimes.Source: §A.1 · p. 33

A.2 Quantum algorithms on matching problems

• The result is a time bound in the adjacency-list model, and the first quantum speedup for weighted matching in general graphs.Unlike query complexity, a time bound counts total running time; prior quantum speedups covered easier settings such as bipartite graphs or uniform edge weights.Source: §A.2 · p. 34
• The table summarizes selected quantum matching results across models, with n = |V|, m = |E|, and W the maximum integer edge weight when applicable.The passage identifies the table’s scope and parameter meanings, but does not supply its individual entries.Source: Table 3 · p. 34, §A.2 · p. 34
• Dörn’s results cover maximum cardinality matching in general graphs and maximum-weight matching in bipartite graphs, leaving this paper to combine general graphs with weights.The respective bounds are O(n√m log2 n) and O(n√m W log2 n).Source: §A.2 · p. 34
• Dörn’s weighted quantum algorithm has linear dependence on W, while scaling-based classical algorithms have logarithmic dependence on the weight range.The paper states that no quantum speedups were previously known for matching algorithms using the scaling framework.Source: §A.2 · pp. 34–35

B.1 The SMALL BLOSSOM LIQUIDATION call-count bound

• O(n(B)) calls to PQSEARCH restricted to B are made during SMALL BLOSSOM LIQUIDATION at one scale.The bound applies to a maximal old small blossom B, where n(B) is its number of vertices.Source: §B.1 · p. 35
• Each call either matches at least two more vertices in B or strictly enlarges the set of free vertices in B having maximum y-value.Each process can occur only O(n(B)) times, yielding the call-count bound.Source: §B.1 · p. 35
• The authors import this classical fact as the only nontrivial classical fact needed for Lemma 18’s proof.The remaining argument is described as an elementary estimate for a small blossom.Source: §B.1 · p. 35

B.2 The free-vertex bound after one scale

• O(n/τ) free vertices remain after FREE VERTEX REDUCTION following one LIQUIDATIONIST scale.The bound is imported from the classical analysis in [13].Source: §B.2 · p. 35
• The classical proof depends on maintained framework properties and SEARCHONE’s postcondition, which QSEARCHONE satisfies by performing the same five tasks.The authors therefore apply the same free-vertex bound to the quantum-enhanced algorithm.Source: §B.2 · p. 35
• Summing over O(log W) scales yields the bound used in Lemma 20, with free vertices potentially appearing in FINALIZATION.Source: §B.2 · p. 35

Matchings, blossoms, and dual variables

• MWPM seeks a perfect matching M ⊆ E that maximizes its weight; the edge variables xe indicate whether each edge is selected.The integer program is relaxed by dropping integrality, but that basic LP relaxation is not integral in general graphs.Source: C Matchings, blossoms, and dual… · pp. 35–36
• Odd-set inequalities address the parity obstruction: on odd sets, a matching can use at most the stated internal-edge limit, and adding these inequalities gives Edmonds’ exact LP formulation.An odd cycle can satisfy degree constraints fractionally without yielding an integral perfect matching.Source: C Matchings, blossoms, and dual… · p. 36
• Blossoms are odd sets contracted during alternating-tree search, and the maintained blossoms form a laminar family handled hierarchically.Source: C Matchings, blossoms, and dual… · p. 36
• The dual uses free vertex variables y(v) and nonnegative odd-set variables z(S), maintained for the current laminar blossom family.An edge’s slack is defined from these dual weights, and an edge is tight when its slack is zero.Source: C Matchings, blossoms, and dual… · p. 37
• Complementary slackness requires used edges to be tight and active odd sets with positive z-value to be tight.Source: C Matchings, blossoms, and dual… · p. 37
• The algorithm searches for augmenting structure among tight edges while maintaining dual feasibility; bipartite graphs omit odd-set inequalities, unlike general graphs.In bipartite graphs the dual consists only of vertex potentials y, while general graphs must track odd sets explicitly.Source: C Matchings, blossoms, and dual… · p. 37

• The appendix presents two simple reductions to justify the main body's problem formulation.Source: D Reduction remarks · p. 37

D.1 From maximum-weight matching to maximum-weight perfect matching

• A matching in G extends to a perfect matching in H by using both edge copies and pairing unmatched vertices with vertical edges.Source: §D.1 · p. 38
• OPTPM(H) = 2 OPTM(G) for the constructed instance, and projecting a perfect matching onto either copy yields an optimal matching in G.The construction duplicates each vertex and edge, adds zero-weight vertical edges, and enlarges the instance by only a constant factor.Source: §D.1 · p. 38

D.2 Maximum-weight versus minimum-weight perfect matching

• Maximum-weight and minimum-weight perfect matching are equivalent under an affine edge-weight transformation because every perfect matching has |V|/2 edges.The transformed objective differs by a constant across perfect matchings, so minimizing it is equivalent to maximizing the original weight.Source: §D.2 · pp. 38–39

E Contracted and original graph paths

• A lifted augmenting path traverses each internal blossom through its base and becomes an augmenting path between the bases of the free endpoint blossoms.The contracted path's alternating boundary edges determine the internal segments used in each blossom.Source: E Contracted and original graph paths · pp. 39–40
• An alternating path inside a blossom connects its base to any vertex, and recursive expansion takes time linear in the number of output edges.For nontrivial blossoms, the route uses the stored odd alternating cycle and recursively expanded child segments.Source: E Contracted and original graph paths · p. 39
• Augmenting along a lifted path preserves each blossom's valid base, alternating defining cycle, laminar vertex sets, and at-most-one matched boundary edge.Source: E Contracted and original graph paths · p. 40
• Lifting a blossom-disjoint set of contracted augmenting paths yields vertex-disjoint paths in the original graph.Each lift uses only vertices contained in the root blossoms on its contracted path.Source: E Contracted and original graph paths · p. 40
• A blossom contains at most one unmatched vertex; if present, it is the base, and the blossom is free.The proof uses the odd defining cycle, whose matched edges pair all non-base children.Source: E Contracted and original graph paths · pp. 40–41