Source-linked AI summary
PyMatching: A Python package for decoding quantum codes with minimum-weight perfect matching
Oscar Higgott
TL;DR
Quantum-error-correction simulations need fast decoders, while general minimum-weight decoding is difficult and existing implementations can be computationally expensive. The paper introduces PyMatching, combining standard MWPM with a local-matching variant that restricts defect pairings to nearby neighbours. Benchmarks show that local matching can be several orders of magnitude faster than exact implementations while retaining almost identical decoding performance.
Problem
Fast, broadly applicable MWPM decoding is needed for quantum-error-correction simulations, but general minimum-weight decoding is computationally difficult and existing implementations are often code-specific.
Method
PyMatching is an open-source Python package that implements full MWPM and local matching, which builds a sparse syndrome graph using each defect’s m closest neighbours and local Dijkstra searches.
Results
PyMatching’s local matching is several orders of magnitude faster than exact MWPM implementations while retaining almost identical decoding performance in benchmarks.
Takeaways & Limitations
Local matching provides a practical approximation to exact MWPM for fast decoding and simulation of quantum error-correcting codes.
Abstract
from arXiv · showhide
This paper introduces PyMatching, a fast open-source Python package for decoding quantum error-correcting codes with the minimum-weight perfect matching (MWPM) algorithm. PyMatching includes the standard MWPM decoder as well as a variant, which we call local matching, that restricts each syndrome defect to be matched to another defect within a local neighbourhood. The decoding performance of local matching is almost identical to that of the standard MWPM decoder in practice, while reducing the computational complexity approximately quadratically. We benchmark the performance of PyMatching, showing that local matching is several orders of magnitude faster than implementations of the full MWPM algorithm using NetworkX or Blossom V for problem sizes typically considered in error correction simulations. PyMatching and its dependencies are open-source, and it can be used to decode any quantum code for which syndrome defects come in pairs using a simple Python interface. PyMatching supports the use of weighted edges, hook errors, boundaries and measurement errors, enabling fast decoding and simulation of fault-tolerant quantum computing.
1 Introduction
Quantum error-correcting codes require fast decoders, but general minimum-weight decoding is computationally difficult. PyMatching provides an open-source, broadly applicable MWPM decoder with a local-matching variant designed to reduce complexity while preserving practical performance.
- Quantum decoders use syndrome measurements to choose correction operators that remove errors from corrupted quantum states.
- General minimum-weight decoding is NP-complete, while MWPM solves it efficiently for a wide class of quantum codes.
- Fast MWPM implementations are important because accurate logical-error estimates require many Monte Carlo trials.
- PyMatching offers full MWPM and local matching through a simple Python interface, supporting quantum codes beyond decoders tailored to specific codes or noise models.
2 Background
Stabiliser codes define protected quantum states through commuting Pauli operators, and decoding uses measured syndromes to select corrections. MWPM provides an efficient approximation to optimal decoding for important code families, although maximum-likelihood decoding is generally intractable.
- A stabiliser code uses an abelian stabiliser group of Pauli operators that excludes −I, with the codespace as their joint +1-eigenspace.
- Check-operator measurements produce a binary syndrome, while logical errors are undetectable Pauli operators that commute with the stabiliser group but are not in it.
- A decoder succeeds when its correction differs from the error by a stabiliser, thereby returning an operator in the error’s stabiliser coset.
- Maximum-likelihood decoding is optimal but typically inefficient, whereas MWPM efficiently solves minimum-weight decoding for important quantum-code families.
3 Minimum-Weight Perfect Matching Decoder
The MWPM decoder represents eligible errors as weighted paths in a matching graph, then matches syndrome defects or boundaries with minimum total weight. Its standard construction is effective but can scale steeply with code size.
- For CSS decoding, defects are X checks that anticommute with the observed Pauli Z error, and the error is represented by a binary noise vector.
- When each single-qubit error touches two checks, decoding becomes finding the smallest weighted 1-chain whose boundary equals the defect set.
- The syndrome graph contains one node per defect, and MWPM selects a perfect matching with minimum summed edge weight using the blossom algorithm.
- For a distance L surface code, exact MWPM has overall runtime O(L6 log(L)), dominated by the blossom step.
- The matching formulation also applies to binary parity-check matrices whose columns each have weight two, beyond the specific stabiliser-code setting.
4 Local matching
Local matching sparsifies the syndrome graph by connecting each defect to nearby defects, reducing matching complexity. It is usually connected for sufficiently large neighbourhoods, but small neighbourhoods can require enlargement and may not return the exact minimum-weight solution.
- Local matching connects each defect to its m closest defects in the matching graph, using shortest-path distance for both neighbourhood selection and edge weights.
- A local Dijkstra algorithm stops after finding m defects, avoiding full distance exploration for every syndrome defect.
- For m > 10, the local syndrome graph is empirically almost guaranteed to be connected in typical 2D and 3D matching graphs.
- If the local graph is disconnected, PyMatching increases m and recomputes it until connectivity is restored; small m can still yield non-minimum-weight solutions.
- Local matching reduces the blossom complexity to O(N 2m log(N)) for a graph with O(N) vertices and O(Nm) edges.
- Prior runtime-reduction strategies can be difficult to generalise beyond planar codes or may ignore weighted shortest paths between defects.
- Union-Find offers nearly linear runtime but typically has lower surface-code thresholds than MWPM, motivating MWPM’s continued benchmarking role.
5 Benchmarks
The benchmarks show that local matching trades exact minimality for much lower computational cost while retaining near-exact decoding performance across tested toric-code settings.
- Performance: m controls a speed–accuracy trade-off: m = |s| −1 recovers exact matching, whereas a small constant m retains perfect matchings without guaranteeing minimum weight.Despite this loss of optimality, local matching can agree with exact matching with very high probability even for small m.
- Performance: m = 6, 7, 8 produce thresholds slightly higher than exact matching under perfect syndrome measurements, while thresholds converge to 0.10321(1) for m ≥12.With noisy syndrome measurements, the threshold stabilises at around 0.0292 for m ≥16, consistent with exact matching.
- Performance: m ≥16 stabilises the logical error rate for both perfect and noisy syndrome measurements, with no statistically significant differences observed from varying m.The tested settings include L = 60, p = 0.1 for perfect measurements and L = 20, p = 0.029 with noisy measurements.
- Performance: Approximation error decreases exponentially with m and decreases with p; it is less than 10^-6 for m ≥20 with perfect measurements but approximately 10^-3 at m = 20 near the noisy-measurement threshold.Approximation error is the fraction of runs where local and exact matching have different matching weights, and it bounds the logical-error-rate difference from above.
- Speed: O(L^2.1) runtime for local matching with m = 20 compares with O(L^4.4) for NetworkX, and PyMatching can be several orders of magnitude faster.These are empirically determined scalings for the tested toric-code decoding workloads.
- Speed: Blossom V is around 10–20% faster than Lemon for local matching and around 20–30% faster for exact matching, but PyMatching uses Lemon because its license is permissive and open-source.For the tested 3D toric matching graph, local matching is faster than exact matching for L > 7.
6 Usage
PyMatching provides a simple Python interface for constructing matching graphs and decoding syndromes, with support for local or exact matching and several error-model features.
- Basic usage: PyMatching constructs a Matching object from a check matrix or graph, then decodes a binary syndrome into a correction array.The correction array marks qubits on which the correction acts non-trivially.
- Local and exact matching: By default, PyMatching uses local matching with m = 30, while the num neighbours parameter changes the neighbourhood size.For example, setting num neighbours=40 uses m = 40 local matching.
- Local and exact matching: Setting num neighbours=None enables exact matching by computing shortest paths between all node pairs and reusing them across later decodes.Exact matching can also be selected with at least |s| −1 neighbours, but storing all shortest paths may require prohibitive memory for very large graphs.
- Extended error models: Matching graphs can include weighted edges, repeated noisy syndrome measurements, boundary nodes, and hook errors.A hook error is represented by one matching-graph edge corresponding to errors on multiple qubits.
- Boundaries: Boundary nodes allow PyMatching to handle odd-parity syndromes by flipping one boundary node so the graph defects have even parity.A zero-weight boundary edge can connect boundary nodes without representing an error.
7 Conclusions
PyMatching combines flexible MWPM decoding with a local-matching variant designed to reduce computational cost. The reported benchmarks show substantially faster decoding while preserving nearly the same performance as exact MWPM.
- Conclusions: PyMatching’s local matching restricts syndrome-graph nodes to their closest neighbours, making it several orders of magnitude faster than exact MWPM for large matching graphs.The comparison is against exact MWPM implementations using NetworkX or Blossom V.
- Conclusions: Local matching retains almost identical decoding performance to exact MWPM in the presented benchmarks.The package prioritizes flexibility across quantum codes amenable to MWPM rather than code-specific optimisations.
- Conclusions: PyMatching is designed to efficiently decode any quantum error-correcting code amenable to MWPM decoding.The authors identify speed and flexibility as potentially valuable for saving programming time and computational resources.