rmatching 0.4.0

Rust minimum-weight perfect-matching decoder for detector-error-model workflows
Documentation
# rmatching

[![Workspace CI](https://github.com/nzy1997/rust-qec/actions/workflows/ci.yml/badge.svg)](https://github.com/nzy1997/rust-qec/actions/workflows/ci.yml)

A Rust implementation of the Sparse Blossom minimum-weight perfect matching (MWPM) decoder for quantum error correction, ported from [PyMatching](https://github.com/oscarhiggott/PyMatching).

Add the decoder library from crates.io:

```toml
[dependencies]
rmatching = "0.4.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

```rust
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](https://github.com/nzy1997/rust-qec/blob/master/examples/rust-consumer/src/main.rs).

## 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`](https://github.com/nzy1997/rust-qec/blob/master/docs/showcases/benchmark-evidence.md).

### 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](https://github.com/nzy1997/rust-qec/blob/master/.github/workflows/ci.yml) is the authoritative
check for this crate and the rest of RustQEC.

Run the full Rust suite:

```bash
cargo test
```

List available Rust tests:

```bash
cargo test -- --list
```

### Benchmark Prerequisites

The Python benchmark drivers compare `rmatching` against PyMatching and require:

```bash
python3 -m pip install numpy pymatching stim
```

Build the benchmark binary first:

```bash
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:

```bash
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:

```bash
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:

```bash
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:

```bash
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`](LICENSE) for the full license text.