Skip to content

Latest commit

 

History

History
178 lines (127 loc) · 6.16 KB

README.md

File metadata and controls

178 lines (127 loc) · 6.16 KB

rmatching

Workspace CI

A Rust implementation of the Sparse Blossom minimum-weight perfect matching (MWPM) decoder for quantum error correction, ported from PyMatching.

Add the decoder library from crates.io:

[dependencies]
rmatching = "0.3.0"

Highlights

  • Full Sparse Blossom algorithm with alternating trees and blossom contraction/shattering
  • Standalone graphlike DEM (Detector Error Model) text parser — no external dependencies
  • Negative edge weight support
  • Decode API: decode, decode_batch, decode_to_edges

The standalone parser constructs matching edges from one- and two-detector DEM error components. Matching::from_dem returns an error for higher-degree hyperedges instead of silently dropping them. Decompose errors into graphlike components before using rmatching. DEM probabilities must satisfy 0 <= p < 1; zero-probability components preserve dimensions but add no edges. Probability-1 components are explicitly unsupported instead of overflowing the integer weight representation.

Cargo Features

This crate has no Cargo features. Repository benchmarks use the private rmatching-bench-tools workspace package, which is not part of the published rmatching package.

rmatching has no rsinter feature and does not implement an rsinter Decoder trait. The consuming rsinter crate owns that integration: enable its rmatching-runner feature when using its adapter.

Quick Start

use rmatching::Matching;

fn main() {
    // From a DEM string
    let mut m = Matching::from_dem("error(0.1) D0 D1 L0\nerror(0.1) D0\nerror(0.1) D1\n").unwrap();
    let prediction = m.decode(&[1_u8, 1]);
    assert_eq!(prediction, vec![1]);
    assert!(Matching::from_dem("error(0.1) D0 D1 D2\n").is_err());

    // Or build manually
    let mut m = Matching::new();
    m.add_edge(0, 1, 2.2, &[0], 0.1);
    m.add_boundary_edge(0, 2.2, &[0], 0.1);
    m.add_boundary_edge(1, 2.2, &[], 0.1);
    let prediction = m.decode(&[1_u8, 0]);
}

Matching is mutable because it reuses solver state and allocation buffers between calls. Syndromes and predictions use one u8 per bit (0 or 1). The current observable mask supports at most 64 observables. For the full rstim → decomposed DEM → rmatching path, run the repository's external-consumer example.

Architecture

Module Description
util Varying (time-varying values), Arena (index-based allocator), RadixHeapQueue
flooder DetectorNode, MatchingGraph, GraphFillRegion, GraphFlooder
matcher AltTreeNode (alternating trees), Mwpm (MWPM solver)
search SearchGraph, SearchFlooder (bidirectional Dijkstra path extraction)
interop CompressedEdge, MwpmEvent, FloodCheckEvent, QueuedEventTracker
driver UserGraph, DEM parser, Matching (public decode API)

Benchmark Snapshot

Snapshot date: 2026-03-14. These numbers come from a fresh local rerun of benchmarks/minimal_results.csv and benchmarks/surface_dem_results.csv at commit 33faf6c. The CSV files are overwritten on each benchmark run, so treat this section as a point-in-time snapshot instead of a stable baseline.

For the full benchmark evidence and reproduction context, see the workspace benchmark evidence showcase.

Minimal DEM Cases

DEM Accuracy rmatching mean decode PyMatching mean decode Notes
boundary-2 100% match, 0 mismatches 1.203 us 1.450 us rmatching slightly faster
square-4 100% match, 0 mismatches 10.397 us 14.538 us rmatching faster
blossom-3 100% match, 0 mismatches 3.369 us 7.863 us rmatching faster

Surface-Code DEM Cases

DEM Accuracy rmatching mean decode PyMatching mean decode Notes
surface-d5-p0.001 100% match, 0 mismatches 65.319 us 11.208 us rmatching slower
surface-d17-p0.001 100% match, 0 mismatches 1943.961 us 552.951 us rmatching slower

Running Tests And Benchmarks

Rust Test Suite

The workspace CI workflow is the authoritative check for this crate and the rest of RustQEC.

Run the full Rust suite:

cargo test

List available Rust tests:

cargo test -- --list

Benchmark Prerequisites

The Python benchmark drivers compare rmatching against PyMatching and require:

python3 -m pip install numpy pymatching stim

Build the benchmark binary first:

cargo build --release -p rmatching-bench-tools --bin rmatching_microbench

Minimal DEM Benchmark Suite

Runs the small hand-written DEM cases and writes:

  • benchmarks/minimal_results.csv
  • benchmarks/minimal_mismatches.json

Command:

python3 benchmarks/run_minimal_benchmark.py --warmup-rounds 20 --measure-rounds 80

Surface-Code DEM Benchmark Suite

Runs the fixed surface-code DEM cases (d=5 and d=17 by default) and writes:

  • benchmarks/surface_dem_results.csv
  • benchmarks/surface_dem_mismatches.json

Command:

python3 benchmarks/run_surface_dem_benchmark.py --shots 64 --seed 12345 --warmup-rounds 10 --measure-rounds 30

Benchmark Driver Unit Tests

The Python harness itself has unit tests:

python3 -m unittest benchmarks.test_run_minimal_benchmark -v
python3 -m unittest benchmarks.test_run_surface_dem_benchmark -v

The fixed d17 regression check used during performance work is:

python3 -m unittest benchmarks.test_run_surface_dem_benchmark.RunSurfaceDemBenchmarkTest.test_rmatching_decodes_known_d17_regression_syndrome -v

License

Apache-2.0. This crate follows the RustQEC workspace license policy; see LICENSE for the full license text.