PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparse Blossom: correcting a million errors per core second with minimum-weight matching

Oscar Higgott, Craig Gidney

arXiv:2303.15933v2quant-ph

TL;DR

Quantum error-correction decoders must process rapidly generated syndrome data without computationally expensive matching procedures. The paper introduces sparse blossom, a direct MWPM decoder implementation that avoids all-to-all Dijkstra searches; on distance-17 surface-code circuits, it decodes both X and Z bases in under 1µs per round on a single core, matching superconducting quantum-computer data generation.

  • Problem

    Quantum error-correction decoders must keep pace with rapidly generated measurement data, while sequential matching approaches can scale quadratically with the number of detection events.

  • Method

    Sparse blossom directly solves the MWPM decoding problem on the detector graph as a variant of the blossom algorithm, avoiding commonly used all-to-all Dijkstra searches.

  • Results

    Under 0.1% circuit-level noise, sparse blossom decodes both X and Z bases of distance-17 surface-code circuits in under 1µs per error-correction round on a single core.

  • Takeaways & Limitations

    The open-source PyMatching v2 implementation processes around a million errors per second on a single core and matches the syndrome-data generation rate of a superconducting quantum computer for distance-17 codes.

  • Takeaways & Limitations

    For distance-30 surface-code decoding at 0.1% circuit-level noise, sparse blossom is around 3.5× slower than the less-than-1µs-per-round throughput desired for real-time superconducting quantum-computer decoding.

Abstract

from arXiv · show

In this work, we introduce a fast implementation of the minimum-weight perfect matching (MWPM) decoder, the most widely used decoder for several important families of quantum error correcting codes, including surface codes. Our algorithm, which we call sparse blossom, is a variant of the blossom algorithm which directly solves the decoding problem relevant to quantum error correction. Sparse blossom avoids the need for all-to-all Dijkstra searches, common amongst MWPM decoder implementations. For 0.1% circuit-level depolarising noise, sparse blossom processes syndrome data in both $X$ and $Z$ bases of distance-17 surface code circuits in less than one microsecond per round of syndrome extraction on a single core, which matches the rate at which syndrome data is generated by superconducting quantum computers. Our implementation is open-source, and has been released in version 2 of the PyMatching library.

1 Introduction

The paper presents sparse blossom, a direct MWPM decoder implementation designed to overcome the speed limitations of existing decoders and support real-time quantum error correction. It reports substantially faster decoding while retaining the MWPM focus of the work.

  • Motivation: MWPM is a widely used surface-code decoder based on mapping decoding to graph matching and solving it with Edmonds’ blossom algorithm.A naive implementation has worst-case complexity O(N^3 log(N)) and empirically typical running time around O(N^2).
  • Problem: Existing published MWPM implementations had not demonstrated speeds sufficient for real-time decoding at scale.This limitation matters because quantum computers generate measurement data continuously, requiring decoders to keep pace.
  • Approach: Sparse blossom directly solves the MWPM decoding problem on the detector graph instead of using separate sequential graph-construction and matching steps.This design avoids the all-to-all Dijkstra searches commonly used in MWPM implementations.
  • Results: Sparse blossom was reported as orders of magnitude faster than alternative available tools.The paper also compares its scaling and speed against explicit path-graph construction and local matching implementations.
  • Results: For 0.1% circuit-level noise, PyMatching decoded both X and Z bases of distance-17 surface-code circuits in under one microsecond per round on one core.This matched the syndrome-data generation rate of a superconducting quantum processor.

2 Preliminaries

The preliminaries formalize graphlike quantum error models, explain how syndromes and logical errors are represented, and distinguish the decoding problem from traditional MWPM. They also motivate sparse blossom through the computational cost of sequential approaches and describe its blossom updates.

  • 2.1 Detectors and observables: A detector is a parity of measurement outcomes that is deterministic without errors; outcome 1 identifies a detection event.Pauli errors flip detectors or logical observables, while logical observables encode measurements of logical Pauli operators.
  • 2.1 Detectors and observables: Independent error models represent error mechanisms with priors and detector- and observable-check matrices H and L.For an error vector e, the syndrome is s = He; a decoder predicts c satisfying Hc = He and succeeds when L(c⊕e) = 0.
  • 2.2 Detector graphs: The analysis restricts attention to graphlike error models, in which each error mechanism flips at most two detectors.These models cover or approximate surface, repetition, hyperbolic, subsystem, Floquet, and mapped color-code decoding problems.
  • 2.2 Detector graphs: A detector graph represents each detector as a node and each one- or two-detector error mechanism as a half-edge or regular edge.The graph is used with edge weights derived from the independent error model.
  • 2.3 The minimum-weight perfect matching decoder: The decoder solves minimum-weight embedded matching rather than traditional MWPM, because only detection events need matching and the embedded edge set need not be a disjoint perfect matching.The sequential construction can require quadratically many edges in the number of detection events, despite the desired expected linear scaling.
  • 2.5 The blossom algorithm: Sparse blossom grows alternating trees on tight edges, applies primal blossom operations, and uses a multiple-tree fixed-δ dual update strategy.This strategy differs from the single-tree approach used in the cited prior implementations.

3 Sparse Blossom

Sparse blossom directly solves the embedded matching problem relevant to quantum error correction by discovering compressed edges only when the blossom algorithm needs them. Its graph-fill regions, alternating trees, blossoms, matches, and compressed edges maintain the structures needed for decoding while exploiting sparse detector graphs.

  • Sparse blossom directly solves the minimum-weight embedded matching problem relevant to quantum error correction.
  • Shortest-path information is recovered during alternating-tree growth rather than through a separate Dijkstra step.Only edges needed by the blossom algorithm are discovered and stored.
  • For typical QEC problems, sparse blossom inspects only a small subset of detector-graph nodes and edges because detection events are sparse and can be paired locally.
  • Graph fill regions: A graph-fill region contains detector-graph nodes within a specified radius of a detection event or a blossom surface.Regions may be trivial when they contain one detection event or nontrivial when their source is a blossom.
  • Compressed edges: Compressed edges represent shortest paths between detection events or between a detection event and the boundary while retaining endpoints and logical-observable information.They provide constant-size representations independent of the represented path length.
  • Alternating trees and blossoms: Alternating trees connect touching active regions, while collisions within one tree form odd-length blossom cycles whose regions become blossom-children.Blossom radii represent growth since formation, and matched regions are frozen and joined by match edges.

3.2 Architecture

Sparse blossom separates matching logic, detector-graph exploration, and event scheduling into a matcher, flooder, and tracker. The matcher updates alternating trees and blossoms in response to collisions and implosions, including matching, blossom formation, and blossom shattering.

  • Architecture: Sparse blossom comprises a matcher, flooder, and tracker with separate responsibilities for tree structure, graph-region dynamics, and event ordering.
  • Architecture: Every detection event initially creates a growing region and trivial alternating tree, which explores the graph until regions become matched to regions or the boundary.
  • Architecture: The flooder constructs collision edges from local collision information and passes them to the matcher for alternating-tree updates.
  • Alternating tree events: When a growing region hits a matched region, the matched pair is incorporated into the alternating tree with alternating growth and shrinkage roles.
  • Alternating tree events: When growing regions from different trees collide, they become matched and all regions in both trees become frozen.
  • Alternating tree events: A collision between growing regions in one tree forms an odd-length blossom cycle, while a zero-radius blossom shatters into an alternating path and matches.
  • Alternating tree events: When a trivial region shrinks to zero radius, it forms a three-region blossom from its parent, itself, and child.
  • Alternating tree events: Boundary collisions match the growing region to the boundary and convert the remaining tree structure into matches.

3.4 The flooder

The flooder grows, shrinks, and collides graph-fill regions while the tracker schedules only relevant future events. Local node information supports event timing and efficient recovery of compressed-edge endpoints and observables.

  • Flooder events: The flooder handles region growth, shrinkage, collisions, and implosions, while notifying the matcher only when tree structure may change.
  • Flooder events: ARRIVE and LEAVE events do not change alternating-tree or blossom structure, so the flooder processes them without notifying the matcher.
  • Flooder events: COLLIDE and IMPLODE events can change region growth rates, requiring coordination between matcher and flooder and possible event rescheduling.
  • Event timing: The local radius of a detector node measures how far its owning regions have grown beyond that node and determines ARRIVE or COLLIDE times along an edge.
  • Event timing: With even integer edge weights, all flooder events, including collisions between growing regions, occur at integer times.
  • Shrinking regions: Shrinking a region is cheaper than growing it because the flooder inspects the shell-area stack instead of enumerating detector-graph edges.
  • Event timeline: A flooder timeline example shows regions initialized at t = 0, regions separated by weight 8 colliding at t = 4, and another region reaching a node and boundary at t = 6.
  • Compressed tracking: During growth, each detector node stores its source detection event and crossed observables, allowing collision-edge endpoints and observable bitmasks to be recovered locally.

3.5 Tracker

The tracker reduces scheduling overhead by placing reminders for the next event at each node or region rather than every potential flooder event. This avoids retaining invalidated neighboring-edge events in the priority queue.

  • Tracker: Adding every potential neighboring-edge event to a priority queue would create substantial chaff.
  • Tracker: The tracker instead queues look-at-node and look-at-region reminders for the next event at each node or region.
  • Tracker: Invalidated potential events along neighboring edges are not added to the queue.
  • Tracker: The tracker further reduces chaff by selectively adding reminders after the flooder computes ARRIVE, COLLIDE, LEAVE, or IMPLODE times.
  • Correspondence: A valid state of traditional blossom corresponds to a valid sparse-blossom state at the appropriate point in the event timeline.

4 Data structures

Sparse blossom represents detector-graph decoding with explicit structures for regions, alternating trees, blossoms, and scheduled events. Its monotone event timeline supports an efficient priority queue.

  • Each detector node stores adjacent edge weights, observable-flip masks, and neighboring-node pointers, including boundary pointers.
  • Occupied detector nodes retain source-event, observable-path, region, ownership, and arrival-radius information.
  • Graph fill regions encode blossom ancestry, cycle edges, child connections, and the detector nodes contained in each region.
  • Alternating-tree nodes link growing regions with shrinking parents, tree parents, and child regions.
  • Tracker fields prevent redundant priority-queue events by recording desired and already queued inspection times.
  • Because dequeued events are monotone in time, sparse blossom uses a radix heap and a cyclic priority window.

5 Expected running time

Sparse blossom has roughly linear expected running time below threshold because decoding work separates into typically small, weakly connected cluster regions. Its observed scaling remains only slightly worse than linear above threshold.

  • Sparse blossom empirically shows almost-linear running time for surface codes below threshold.At low physical error rates, typical error configurations consist of small isolated clusters.
  • Exponentially decreasing cluster-size probabilities combined with polynomial per-cluster work yield constant expected cost per cluster and linear total running time.
  • Separated cluster regions can be decoded independently while producing the same solution as decoding the full detector graph.
  • Above threshold, the observed complexity is O(n^1.32), only slightly worse than linear.
  • The shared radix heap does not change the overall theoretical complexity because insertion is O(1) and extract-min is amortized O(B).Here B = 32 bits for the priority representation.
  • Very large instances incur more cache misses and increased processing time per detection event under the timeline and multiple-tree priority-queue design.The approach nevertheless touches less of the detector graph than a single-tree alternative in the described example.

6 Computational results

PyMatching v2 benchmarks show fast, near-linear sparse-blossom decoding across surface-code simulations and experimental data. It reaches sub-microsecond per-round processing in a representative distance-17 case and substantially outpaces prior implementations.

  • Less than 1 microsecond per round processes both X and Z bases of distance-17 surface-code circuits at 0.1% circuit-level depolarising noise on one core.This matches the syndrome-data generation rate of superconducting quantum computers.
  • Roughly linear PyMatching v2 scaling at low physical error rates is a quadratic improvement over an implementation that explicitly constructs the path graph.
  • For 0.1%-1% physical error rates and distance 29 and larger, PyMatching v2 is >100,000× faster than a pure Python exact-MWPM implementation.
  • Compared with local matching, PyMatching v2 is around 100× faster near threshold and almost 1000× faster below threshold while remaining exact.The comparison covers error rates of 0.5%-1% near threshold and p = 0.1% below threshold.
  • For distance-17 circuits at p = 0.1%, mean running time is 0.62 microseconds per round, with 97.4% of one million shots below 1 microsecond per round.
  • On an M2 chip, PyMatching v2 decoded 7 million experimental shots in 71 seconds versus 3 hours 43 minutes for PyMatching v0.7.

7 Conclusion

Sparse blossom directly solves the MWPM decoding problem while avoiding commonly used all-to-all Dijkstra searches. It reaches sub-microsecond decoding for distance-17 surface-code circuits and introduces compressed tracking that also simplifies Union-Find, while distance-30 real-time throughput remains an open challenge.

  • Conclusion: Around a million errors per second can be processed on a single core with sparse blossom in PyMatching version 2.The implementation is open-source and available in the PyMatching Python package.
  • Conclusion: 97.4% of shots run below 1 microsecond per round for distance-17 circuits at 0.1% circuit-level depolarising noise.The histogram uses 17-round circuits and a 0.01-microsecond bin width.
  • Conclusion: Compressed tracking significantly simplifies Union-Find by storing compressed paths and eliminating spanning-tree construction during peeling.The representation retains path endpoints and the logical observables crossed as a bitmask.
  • Conclusion: For distance-30 surface-code decoding at 0.1% circuit-level noise, sparse blossom is around 3.5× slower than the desired < 1µs per round throughput.The authors identify parallel CPU or FPGA implementations as a direction for reaching real-time decoding at scale.

Contributions

The authors jointly designed sparse blossom, with Oscar Higgott writing the paper and most of the code and Craig Gidney guiding the project and implementing final optimisations.

  • Contributions: Both authors worked together on the design of the sparse blossom algorithm.Their contributions included distinct writing, coding, project-guidance, and optimisation roles.
  • Contributions: Oscar Higgott wrote the paper and the majority of the code.
  • Contributions: Craig Gidney guided the project and implemented final optimisations such as the radix heap.

A Compressed tracking in Union-Find

Compressed tracking represents Union-Find cluster trees using detection events and compressed paths rather than every detector node. It preserves logical-observable information while making peeling more efficient.

  • A Compressed tracking in Union-Find: During cluster growth, each detector node tracks its source detection event and the logical observables crossed along its path.Observable tracking is updated using XOR as nodes are added to a cluster.
  • A Compressed tracking in Union-Find: Compressed cluster-tree nodes correspond to detection events, while edges represent detector-graph paths between them.Unlike sparse-blossom compressed edges, these paths are not generally minimum-length paths.
  • A Compressed tracking in Union-Find: Path compression combines the logical-observable sets of the compressed edges along the replaced tree path.The same modification can be applied to path splitting or path halving.
  • A Compressed tracking in Union-Find: When clusters collide, the collision edge and its logical-observable set are constructed from local source and path information.The collision-edge observable set combines the observables tracked at both endpoints and on the collision edge.
  • A Compressed tracking in Union-Find: After clusters reach even parity, compressed peeling returns highlighted compressed edges and the logical observables they flip.The decoder aggregates observable bitmasks over highlighted edges without constructing a spanning tree.
  • A Compressed tracking in Union-Find: Compressed peeling is linear in the number of compressed cluster-tree edges and avoids conventional spanning-tree construction.The procedure recursively returns parity and the observables flipped by highlighted descendant edges.

B Worst-case running time

The paper derives a loose worst-case running-time bound for sparse blossom by counting unmatched-event reductions and bounding operations across algorithmic stages.

  • B Worst-case running time: Each alternating tree contains exactly one unmatched detection event, while tree collisions reduce unmatched events by two and boundary events reduce them by one.Growth, blossom formation, and shattering do not change the number of unmatched detection events.
  • B Worst-case running time: Each stage forms or shatters at most O(q) blossoms and adds at most O(q) matches to alternating trees.The bound uses q, the number of detection events.
  • B Worst-case running time: Blossom formation can cost O(nq) per operation, while adding a match and rescheduling growth events each cost O(m) within a stage.The tracker contributes constant-time work per operation and does not dominate the overall bound.

C Handling negative edge weights

Negative edge weights arise when error probabilities exceed 0.5, so sparse blossom uses a transformation that enables MWPM decoding with non-negative adjusted weights. The resulting correction remains a minimum-weight solution for the original problem.

  • Why negative weights matter: p[i] > 0.5 makes w[i] = log((1 −p[i])/p[i]) negative, requiring negative-edge handling for correct decoding.The example shows that negative weights select the more probable higher-Hamming-weight correction.
  • Transformation: The procedure marks every negative-weight edge in b and flips its sign to form non-negative adjusted weights v.It also adjusts the syndrome to s′ = s + Hb.
  • Transformation: Sparse blossom then finds c′ satisfying Hc′ = s′ with minimal adjusted weight.The adjusted problem is constructed so sparse blossom can serve as a subroutine despite its non-negative-weight restriction.
  • Correctness: Returning c := c′ + b produces a correction satisfying Hc = s with minimal total original weight.The equivalence follows because the binary-field sum removes weights for bits set in both c′ and b.
  • Correctness: The transformation reframes mechanisms with error probability above 50% as predicting that they did not occur.This provides the intuition behind complementing the negative-weight components.

D Example of detectors and observables for a repetition code

The repetition-code example represents detectors, logical observables, and error mechanisms for a two-round [[2,1,2]] bit-flip memory experiment. It then relates these circuit features to matrices and a detector graph.

  • Circuit example: The example uses a [[2,1,2]] bit-flip repetition code with stabilizer group ⟨ZZ⟩, transversal Z-basis initialization and measurement, and two syndrome-extraction rounds.Figure 16 presents the corresponding detectors, logical observable, and error mechanisms.
  • Detectors and observables: Three detectors are represented through Z-type detecting regions, where anticommuting errors flip the corresponding detector.These regions identify which circuit errors affect each detector.
  • Detectors and observables: A logical Z observable is represented by a Z-type sensitivity region, whose anticommuting errors flip the logical measurement outcome.For the surface-code analogue, this sensitivity region becomes a two-dimensional sheet in spacetime.
  • Error mechanisms: Under standard circuit-level depolarising noise, the circuit has eight error-mechanism classes classified by the detectors and logical observables they flip.The figure illustrates representative single-qubit X errors for these classes, while other Pauli errors can belong to the same class.
  • Matrix and graph representation: When H has column weight at most two, detector-check-matrix columns can be represented as detector-graph edges or boundary half-edges.Edges also carry the logical observables they flip and a probability-derived weight.
Loading 2303.15933v2…