PaperlayerView exact revision on arXiv

Source-linked AI summary

Fusion Blossom: Fast MWPM Decoders for QEC

Yue Wu, Lin Zhong

arXiv:2305.08307v1quant-phcs.DCcs.DS

TL;DR

Existing MWPM decoders face a speed gap with quantum hardware, motivating online decoders that can keep pace with measurements. The paper introduces Parity Blossom and its parallel version, Fusion Blossom; in the reported 0.1% noise setting, Fusion Blossom reaches one million measurement rounds per second up to code distance 33.

  • Problem

    Existing MWPM implementations cannot keep pace with quantum hardware generating up to one million measurements per second, risking a growing measurement backlog.

    Source: §I · p. 1

  • Method

    The paper introduces Parity Blossom, which works on the decoding graph, and parallelizes MWPM decoding in Fusion Blossom by recursively splitting and fusing subproblems.

    Source: §I · p. 1, §IV · p. 5

  • Results

    At 0.1% circuit-level noise, Fusion Blossom decodes one million measurement rounds per second up to code distance 33 in batch mode.

    Source: §I · p. 1

  • Takeaways & Limitations

    Fusion Blossom provides batch and stream decoding modes, with stream mode maintaining 0.7 ms average latency at code distance 21 regardless of measurement-round count.

    Source: §I · p. 1

Abstract

from arXiv · show

The Minimum-Weight Perfect Matching (MWPM) decoder is widely used in Quantum Error Correction (QEC) decoding. Despite its high accuracy, existing implementations of the MWPM decoder cannot catch up with quantum hardware, e.g., 1 million measurements per second for superconducting qubits. They suffer from a backlog of measurements that grows exponentially and as a result, cannot realize the power of quantum computation. We design and implement a fast MWPM decoder, called Parity Blossom, which reaches a time complexity almost proportional to the number of defect measurements. We further design and implement a parallel version of Parity Blossom called Fusion Blossom. Given a practical circuit-level noise of 0.1%, Fusion Blossom can decode a million measurement rounds per second up to a code distance of 33. Fusion Blossom also supports stream decoding mode that reaches a 0.7 ms decoding latency at code distance 21 regardless of the measurement rounds.

I. INTRODUCTION

The paper presents Fusion Blossom, a parallel online MWPM decoder, and Parity Blossom, a fast sequential solver that works directly on the decoding graph. It motivates these designs by the need for scalable decoding and by the superlinear cost of building and solving the complete syndrome graph in existing approaches.

I. INTRODUCTION

  • The paper frames online decoding as processing all syndrome bits faster than the hardware generates them, while scalability to large code distances supports the desired logical error rate.It identifies the exponential backlog as a concern discussed by Terhal.Source: §I · p. 1
  • At 0.1% circuit-level noise, Fusion Blossom decodes up to d = 33 at one million rounds per second in batch mode and reaches 0.7 ms average latency at d = 21 in stream mode.The stream latency is reported regardless of the number of measurement rounds.Source: §I · p. 1
  • Fusion Blossom recursively divides decoding into independent subproblems and fuses their solutions through a tree, using Parity Blossom as its MWPM solver.Parity Blossom works on the sparse decoding graph rather than constructing the syndrome graph.Source: §I · p. 1

A. Quantum Error Correction (QEC) Codes

  • MWPM is an exact most-likely-error decoder when the error model is representable by a model graph; it finds a minimum-weight perfect matching among syndrome-graph defects.The syndrome graph connects defect vertices using minimum-weight paths derived from the decoding graph.Source: A. Quantum Error Correction (QEC) Codes · p. 2
  • Existing MWPM implementations face a throughput challenge: even fast general-graph approaches scale as O(|V|^2.5) because the syndrome graph is complete.The paper notes that this grows faster than the number of defect stabilizer measurements, |V|.Source: A. Quantum Error Correction (QEC) Codes · p. 2

I. INTRODUCTION

  • Parity Blossom removes syndrome-graph construction and reaches average runtime almost O(|V|) at sufficiently low error rates, but is specialized to QEC decoding graphs rather than general graphs.Its design draws on the relationship between Union-Find and MWPM described in prior work [9].Source: A. Quantum Error Correction (QEC) Codes · p. 2

B. Blossom Algorithm in General

The blossom algorithm formulates MWPM as a linear program and evolves a matching while preserving dual feasibility. For QEC syndrome graphs, a non-negative-vertex-dual result permits a simplified formulation that treats single vertices as blossoms.

B. Blossom Algorithm in General

  • The blossom algorithm relaxes the integer MWPM formulation to a linear program, adds constraints preserving optimal integer solutions, and uses the dual formulation.A perfect matching selects exactly one incident edge per non-virtual vertex while minimizing total edge weight.Source: B. Blossom Algorithm in General · pp. 2–3
  • Only tight edges can appear in the final matching, and odd cycles of tight edges define blossoms that can be nested.A blossom is a set with positive dual variable; a node is a blossom or vertex that is not another blossom’s child.Source: B. Blossom Algorithm in General · p. 3

1) Blossom algorithm:

  • The algorithm grows a matching through alternating trees while the dual phase updates variables without violating dual feasibility.The primal phase computes an update direction; the dual phase detects obstacles and reports them before a constraint is violated.Source: 1) Blossom algorithm · p. 3

C. Blossom Algorithm in QEC

  • For independent error sources with probability at most 0.5, vertex dual variables remain non-negative throughout the solution process.This result is the condition used to simplify the QEC decoding formulation.Source: C. Blossom Algorithm in QEC · pp. 3–4
  • The QEC simplification treats a single vertex as a blossom and defines blossoms as odd cycles of blossoms connected by tight edges.The simplified odd-subset set includes both blossoms and single vertices.Source: C. Blossom Algorithm in QEC · p. 4

III. GEOMETRIC INTERPRETATION

The paper interprets blossoms geometrically on the decoding graph, linking them to covers formed from circles around their vertices. This interpretation supports the decoder designs but relies on non-negative weights and dual variables.

III. GEOMETRIC INTERPRETATION

  • The geometric interpretation links syndrome-graph blossoms to covers on the decoding graph, providing a mathematical foundation for the decoder designs.The interpretation relies on non-negative weights and dual variables and does not apply to blossom algorithms on general graphs.Source: §III · p. 4

A. Geometry of Decoding Graph

  • Decoding-graph edges are treated as continuous lines weighted by edge cost, allowing paths and distances to be defined between arbitrary points.Zero-weight edges are used for decoding erasure errors.Source: A. Geometry of Decoding Graph · p. 4
  • A circle around a vertex contains points within a chosen decoding-graph distance, and its boundary consists of points exactly at that distance.The edge between two syndrome-graph vertices has the weight of a minimum-weight decoding-graph path between them.Source: A. Geometry of Decoding Graph · p. 4

1) Geometric Notions:

  • A blossom’s progeny comprises itself and its descendants, while ancestry identifies the blossoms containing a given vertex.A cover is the union of circles centered at a blossom’s vertices, connecting syndrome-graph blossoms to decoding-graph geometry.Source: 1) Geometric Notions · pp. 4–5

2) Obstacle Detection on Decoding Graph:

The paper shows how to detect MWPM obstacles using the decoding graph, then builds Fusion Blossom by dividing decoding problems, solving subproblems, and fusing their solutions. Its fusion trees schedule leaf and fusion operations to trade off decoding time and latency.

2) Obstacle Detection on Decoding Graph:

C. Parity Blossom

  • At low physical error rates, detecting obstacles on the decoding graph has average time complexity roughly O(|V|), versus O(|V|^2) to generate the syndrome graph.For small |V| or large p, the syndrome graph might be faster.Source: C. Parity Blossom · p. 5

IV. FUSION BLOSSOM

  • Fusion Blossom recursively divides decoding problems into independently solved subproblems, then fuses their solutions through a binary tree to produce a global MWPM.Its implementation uses Parity Blossom as the MWPM solver.Source: §IV · p. 5

A. Division

  • A vertex cut Vb divides the decoding graph into subgraphs that share only Vb; division stops when each subproblem is small enough for direct MWPM solving.Subproblems treat Vb vertices as virtual vertices, relaxing their parity constraints until fusion.Source: A. Division · p. 5

B. Fusion

  • Fusion starts from the independently solved subproblems’ intermediate state and invokes the MWPM solver to reach a solution to the original problem.The subproblems’ dual variables, with newly introduced variables set to zero, form a feasible solution to the original dual problem; average fusion time is estimated at no worse than O(p|Vb|), independent of subproblem sizes.Source: B. Fusion · pp. 5–6

C. Schedule Design: Leaf Partitions and Fusion Tree

  • Leaf partitions contain M consecutive measurement rounds and invoke the MWPM solver when those rounds are ready; the fusion tree schedules their solutions.Balanced, linear, and mixed trees offer different time-latency tradeoffs; mixed-tree height can be selected to minimize latency for the setup.Source: C. Schedule Design: Leaf Partitions… · pp. 6–7
  • For batch decoding, the balanced tree minimizes the longest leaf-to-root path; in stream decoding, a linear tree can be preferable when the last leaf’s path sets latency.Stream decoding begins when a leaf has enough measurement rounds ready, so latency can be shorter than decoding time.Source: C. Schedule Design: Leaf Partitions… · pp. 6–7

V. IMPLEMENTATION

The implementation uses a shared framework for matching-decoder variants and builds Parity Blossom’s dual module around Pseudo-Covers to detect tight edges on the decoding graph. It also identifies a trade-off continuum between Union-Find and Parity Blossom by limiting alternating-tree size.

A. Unified Framework for Matching Decoders

  • The unified framework lets a primal module pair with any dual module, supports code reuse, and exposes variants with different accuracy–speed trade-offs.Limiting alternating-tree size yields a continuum from Parity Blossom at an infinite limit to the Union-Find decoder at zero.Source: A. Unified Framework for Matching… · p. 7, Figure 6 · p. 7

B. Parity Blossom

1) Parity Dual Module:

  • The Parity dual module tracks cover boundaries to update covers efficiently as dual variables change.It checks decoding-graph edges for qualifying Pseudo-Cover intersections and reports detected obstacles to the primal module.Source: 1) Parity Dual Module · pp. 7–8
  • Pseudo-Covers keep each vertex in at most one cover and let the dual module detect tight edges by checking where Pseudo-Covers meet on decoding-graph edges.The theorem guarantees detection of a qualifying tight edge, while the implementation reports at most one obstacle per decoding-graph edge.Source: 1) Parity Dual Module · p. 8
  • The implementation enumerates all edges rather than using priority queues to process edges in order of when they become tight.The authors note that this omits an optimization used by Sparse Blossom [3] and Blossom V [15].Source: 1) Parity Dual Module · p. 8

2) Standard Primal Module:

The implementation combines a modular blossom solver with a fusion-tree scheduler and several memory and runtime optimizations. The evaluation specifies the noise model, hardware, baselines, and timing measures used to assess the decoders.

2) Standard Primal Module:

  • The Standard primal module supports virtual vertices, handles all reported obstacles per invocation, and grows alternating trees simultaneously, which explores fewer edges on average [3].It is based on Blossom V and the authors say its optimizations can be useful beyond Parity Blossom.Source: 2) Standard Primal Module · p. 8

C. Fusion Blossom

  • A manager schedules fusion-tree jobs once both child jobs return, and worker threads run each job’s Parity Blossom MWPM solver.Fusion Blossom is implemented using the Rayon parallel programming library.Source: C. Fusion Blossom · p. 8
  • Parent solvers reuse child solver data structures, and can invoke child solvers to update the small region around fusion-boundary vertices.The data structures remain in place and are organized hierarchically along the fusion tree.Source: C. Fusion Blossom · p. 8

D. Other Optimizations

  • The optional dangerous_pointer feature bypasses Rust safety checks when deemed algorithmically safe and yields approximately 2x speedup.A timestamp scheme also makes decoder reset O(1) by resetting invalid edges only when accessed.Source: D. Other Optimizations · pp. 8–9

VI. EVALUATION

  • Correctness was checked against the Blossom V library over millions of randomized cases with tractable code distances up to 19.Source: §VI · p. 9

1) Noise Model:

  • The evaluation uses a 0.1% circuit-level noise model on a rotated surface code and measures speed on a 64-core server.Initialization time is excluded; each shot defaults to 10^5 measurement rounds, and reset overhead is included.Source: 1) Noise Model · p. 9, 2) Measurement · p. 9

3) Baseline:

  • Sparse Blossom is run through its Python binding with batch optimization; Blossom V uses a precomputed virtual-boundary graph with edges that cannot be selected removed.Source: 3) Baseline · p. 9

4) Metrics:

  • Throughput is N/T and decoding time per measurement round is T/N; the figures use the latter because it is easier to compare with hardware measurement cycles.Figures 7 and 8 report single-thread and parallel decoding time, respectively, with lower values better.Source: 4) Metrics · p. 9, Figure 7 · p. 9, Figure 8 · p. 9

B. Results

Fusion Blossom’s throughput, latency, and fusion-time results support fast parallel decoding, while its scalability analysis specifies the resources and conditions needed at larger code distances. The section also contrasts its design with prior MWPM approaches.

1) Throughput:

  • Parity Blossom and Sparse Blossom scale almost linearly with qubit count, unlike blossom V, while Fusion Blossom stays steady as rounds grow and beats Parity Blossom for N ⩾ 10^3.The authors attribute the latter result to cache locality and use M = 100 as the empirically optimal leaf partition size.Source: 1) Throughput · p. 9
  • With 128 hyper-threads, Fusion Blossom reaches 0.3 us decoding time per round and decodes up to d = 33 at p = 0.1% in less than 1 us per round.Throughput increases almost linearly with thread count up to the processor’s 128 hyper-threads.Source: 1) Throughput · p. 10

2) Latency:

  • In stream decoding, average latency is roughly 0.7 ms regardless of measurement rounds, whereas batch-decoding latency grows linearly with N.The stream test emulates a 1 us stabilizer measurement cycle, with M = 20 rounds per leaf.Source: 2) Latency · p. 10

3) Fusion Time:

  • At low physical error rates, fusion time grows with boundary size |Vb| = O(d^2), not the number of rounds M; tree structure also affects fusion time.Mean fusion time rises with leaf count for balanced trees but largely stays constant for linear trees, because nearby leaf partitions are more likely to be fused.Source: 3) Fusion Time · p. 10

4) Scalability:

  • Given enough resources, Fusion Blossom can meet throughput requirements at any code distance when p is well below threshold; the analysis requires K = Ω(d^2.68) parallel resources.The scaling factors were empirically derived from code distances up to 100, a range the paper says is orders of magnitude beyond near-term practical consideration.Source: 4) Scalability · p. 10

VII. RELATED WORK

  • Fusion Blossom eliminates communication between partitions and synchronizes them only during fusion, minimizing communication and supporting scalability; general-graph MWPM work does not exploit QEC structure and has larger time complexity on QEC decoding.Peterson and Karalekas [29] designed and implemented a distributed MWPM algorithm with O(|V |4) time complexity.Source: §VII · p. 11

APPENDIX A FACTS & LEMMAS

The appendix states properties of decoding-graph weights and blossom dual variables, then uses them to establish nonnegative vertex duals throughout the algorithm.

APPENDIX A FACTS & LEMMAS

  • For physical error probabilities at most 50%, decoding-graph weights are nonnegative, and syndrome-graph weights inherit nonnegativity and the triangle inequality.For probabilities above 50%, the passage describes an equivalent always-happening error followed by decoding with positive weights.Source: Appendix A · p. 12
  • The blossom algorithm starts with feasible dual variables and maintains feasibility; when a dual decreases, two “+” nodes increase their variables by the same amount.Different nodes do not share vertices or descendants, and the algorithm maintains blossoms with positive dual variables.Source: Appendix A · p. 12
  • The appendix states ancestry identities for nodes and uses disjoint ancestry sets to simplify dual-variable summations.The listed identities include A(v) = Dv(Root(v)) and the distinct-root relation A(u\v) = A(u).Source: Appendix A · p. 12

APPENDIX B LP SIMPLIFICATION

  • The Non-negative Vertex Dual theorem states that yv remains nonnegative throughout blossom when every independent error probability is at most 0.5.The proof uses feasible initialization and dual updates, concluding that a vertex dual cannot decrease below zero.Source: Appendix B · p. 12

APPENDIX C PROOFS OF DECODING GRAPH

These lemmas characterize how circles on the decoding graph intersect weighted edges, including the finite edge segments and incident points covered by a circle.

APPENDIX C PROOFS OF DECODING GRAPH

  • The edge-distance argument uses the bound that distances from a point to the edge’s endpoints differ by at most the edge weight.The passage parameterizes distance along the edge by w1 and expresses the point-to-edge distance as the minimum of paths through either endpoint.Source: Appendix C · p. 13
  • A decoding-graph circle covers finitely many vertices and edge segments, with incident points represented as a finite union of closed intervals.The edge cases include portions that lie inside or outside the circle and boundaries where distance equals the radius.Source: Appendix C · p. 13
  • An edge may lie wholly inside or outside a circle, or be partitioned at one or two points whose distance from its center equals the radius.With two such points, the middle edge segment lies outside and the two outer segments lie inside.Source: Appendix C · p. 13

APPENDIX D PROOFS OF BLOSSOM

The appendix relates blossom dual variables to geometric circles on the decoding graph and establishes when syndrome-graph edges are tight.

APPENDIX D PROOFS OF BLOSSOM

  • A node’s cover consists of circles associated with its vertices, and covers of two nodes overlap in only a finite set.The appendix states the finite-overlap result for distinct nodes and uses the node-cover relation in the tight-edge argument.Source: Appendix D · pp. 13–14
  • A syndrome-graph edge is tight if and only if the corresponding decoding-graph circles overlap.The paper’s overlay maps a syndrome-graph vertex dual variable to a circle of the same radius on the decoding graph.Source: Appendix D · p. 13, Figure 11 · p. 13
  • The proof connects geometric overlap to edge slackness using minimum-weight paths and the triangle inequality for decoding-graph distance.The theorem’s necessity argument starts from a tight syndrome-graph edge and a minimum-weight path between its endpoints.Source: Appendix D · p. 14

APPENDIX E PROOFS OF FUSION BLOSSOM

Fusion Blossom partitions a decoding graph at boundary vertices into disjoint MWPM subproblems. The proof shows that solutions to these subproblems yield feasible dual variables for the original problem.

APPENDIX E PROOFS OF FUSION BLOSSOM

  • A boundary vertex set that disconnects the decoding graph separates the MWPM problem into two disjoint subproblems.Each subproblem uses the edges and blossoms restricted to its vertex set and the boundary vertices.Source: Appendix E · p. 15
  • Solving the two disjoint subproblems and setting omitted blossom dual variables to zero gives a feasible solution to the original dual problem.The subproblem dual-variable values are retained for blossoms in either subproblem.Source: Appendix E · p. 15
  • For edges spanning the two parts, the proof uses a minimum-weight path through a boundary vertex to relate its weight to the two subproblem edge weights.This argument supports feasibility of the original dual constraints for edges not included in either subproblem.Source: Appendix E · p. 15

APPENDIX F PROOFS OF PA R I T Y DUAL MODULE

The appendix proves that Pseudo-Covers can replace Covers for detecting tight edges, despite complications from zero edges and graph partitioning. It establishes the needed boundary and touching properties, and illustrates how valid Pseudo-Covers expose an obstacle.

APPENDIX F PROOFS OF PA R I T Y DUAL MODULE

  • Zero edges complicate Pseudo-Covers because connected vertices can belong to multiple Covers, and partitioning can leave some zero edges unknown when a subproblem Pseudo-Cover is built.The appendix motivates proving that Pseudo-Covers remain effective for obstacle detection under these conditions.Source: Appendix F · p. 15
  • An island consists of vertices at zero distance from a vertex and is non-trivial only when zero edges are present.Occupancy is the set of nodes whose Cover includes a vertex; if a vertex has multiple occupiers, it lies on the boundary of each occupier's Cover.Source: Appendix F · pp. 15–16
  • Figure 12 shows that removing boundary vertices from a negative-direction Cover and absorbing boundary vertices into a positive-direction Cover can make Pseudo-Covers touch and detect an obstacle.In the example, the initial Pseudo-Covers do not touch on a decoding-graph edge because another Cover isolates them.Source: Figure 12 · p. 16
  • When two occupiers have directions whose sum is positive, some pair of their Pseudo-Covers borders each other.The proof uses the island's occupancy and handles cases where the island overlaps another Pseudo-Cover or only one Pseudo-Cover.Source: Appendix F · pp. 16–17
  • Pseudo-Covers detect a tight edge between nodes with positive combined direction exactly when two qualifying Pseudo-Covers meet on a decoding-graph edge.The proof relates this condition to overlap of the corresponding Covers, including cases where a shared point is a vertex.Source: Appendix F · p. 17

APPENDIX G PARITY BLOSSOM EXAMPLE

The example walks through Parity Blossom's primal and dual phases, from initial directions and obstacle detection to matching and MWPM output. It illustrates how the phases overcome obstacles and form a blossom along the way.

APPENDIX G PARITY BLOSSOM EXAMPLE

  • The figure presents the procedure from receiving defect vertices through calculating the MWPM.It is identified as an example of Parity Blossom's whole procedure.Source: Appendix G · p. 17
  • The example proceeds through primal and dual phases until all nodes are matched, then expands blossoms and outputs an MWPM.The dual phase detects obstacles; the primal phase changes directions, builds an alternating tree and blossom, and matches nodes.Source: Figure 13 · p. 18, Appendix G · p. 18
  • Starting with all directions +1 and dual variables zero, the dual phase finds an obstacle, which the primal phase overcomes by matching a defect to a virtual vertex.Later obstacles lead to an alternating tree and a blossom S = {a, b, c}.Source: Figure 13 · p. 18, Appendix G · p. 18

Related papers

Loading 2305.08307v1…