Skip to content

decoder-core: replace MWPM greedy fallback with scalable matching #7

Description

@DennisWayo

Context

The current in-repo BlossomMWPM backend uses an exact bitmask dynamic-programming solver for small graphs and falls back to a greedy matcher beyond the configured node cap. That is useful as a lightweight implementation, but it makes larger-distance threshold comparisons and neural-guided MWPM results hard to interpret.

This should be addressed before making stronger claims about neural or tensor-network decoder performance.

Proposal

Replace the default greedy fallback path with a scalable minimum-weight perfect matching backend, keeping the current exact solver as a small-instance regression oracle.

Possible implementation routes:

  • integrate a proven Blossom V / Kolmogorov-style backend behind a small adapter,
  • add an optional external matching dependency with a deterministic fallback,
  • keep the current DP path for small test fixtures and cross-checks.

Acceptance Criteria

  • Exact small-instance outputs match the current DP solver for representative d=3/d=5 cases.
  • Larger surface-code cases do not use greedy fallback by default.
  • Decoder behavior is deterministic under fixed seeds.
  • Benchmarks cover at least d=3, d=5, d=7, and one larger distance.
  • CI includes focused regression tests for syndrome reproduction and matching parity.

Notes

This is foundational for mwpm, neural_mwpm, and any future tensor-network or neural comparison work.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions