PyMatching: Minimum Weight Perfect Matching Decoder

PyMatching is a high-performance Python/C++ library designed for decoding quantum error correcting (QEC) codes using the Minimum Weight Perfect Matching (MWPM) decoder. It is optimized for speed using a 'sparse blossom' algorithm implementation that is significantly faster than previous versions and alternatives like NetworkX.

Key features include:

• MWPM Decoding: Finds the most probable set of errors assuming they are independent and graphlike.
• Broad Code Support: Works with surface codes, subsystem codes, honeycomb codes, and 2D hyperbolic codes.
• High Performance: Version 2 uses a sparse blossom algorithm that is 100-1000x faster than previous versions and scales roughly linearly with the number of nodes.
• Correlated Matching: Supports correlated matching (as of v2.3) to improve accuracy in scenarios with hyperedge errors (e.g., $Y$ errors in surface codes).

Correlated matching is a feature (available since v2.3) that provides better accuracy than standard uncorrelated matching when hyperedge errors are present. In many QEC problems, hyperedge errors (like a $Y$ error) can be decomposed into graphlike edges that are correlated.

PyMatching implements a "two-pass" correlated matching decoder:

1. First Pass: Runs a standard (uncorrelated) sparse blossom to predict a set of edges.
2. Reweighting: Assumes those edges occurred and reweights edges that are correlated with them.
3. Second Pass: Runs the matching algorithm again on the reweighted graph to produce the final result.

To use pymatching in a Bazel project, define the repository in your WORKSPACE file and add the dependency to your BUILD file.

# In WORKSPACE
load("@bazel_tools//tools/build_defs/repo:git.bzl", "git_repository")
git_repository(
    name = "pymatching",
    commit = "eea3501a1c1e2dc2b6d34221c6f1eb51edb06e1e",
    remote = "https://github.com/oscarhiggott/pymatching.git",
)

# In BUILD
cc_binary(
    name = "your_project",
    ...
    deps = [
        "@pymatching//:libpymatching",
    ],
)

You can use the pymatching predict command to solve decoding problems. This typically involves a workflow where you first generate a circuit and error model using stim, then pass the detection events to pymatching.

Workflow steps:

1. Generate Stim circuit: Use stim gen to create a .stim file.
2. Analyze errors: Use stim analyze_errors to create a .dem (error model) file.
3. Detect events: Use stim detect to generate detection events (e.g., in b8 format) and actual observation flips.
4. Predict with PyMatching: Use pymatching predict to generate predicted observation flips.

Example command:

pmatching predict \
    --dem error_model.dem \
    --in detection_events.b8 \
    --in_format b8 \
    --out predicted_obs_flips.01 \
    --out_format 01

To build the pymatching CLI tool from source using CMake, run the following commands in the repository root. The resulting executable will be located at ./pymatching.

cmake .
make pymatching
# result is at ./pymatching

To use pymatching as a dependency in a CMake project, use FetchContent to pull the repository and then link against libpymatching.

FetchContent_Declare(pymatching
        GIT_REPOSITORY https://github.com/oscarhiggott/pymatching.git
        GIT_TAG eea3501a1c1e2dc2b6d34221c6f1eb51edb06e1e)
FetchContent_GetProperties(pymatching)
if(NOT pymatching_POPULATED)
  FetchContent_Populate(pymatching)
  add_subdirectory(${pymatching_SOURCE_DIR})
endif()

# ... later in your project ...
target_link_libraries(YOURLIBRARY libpymatching)

The pymatching animate command produces SVG animation frames of the decoding process. These frames can then be rendered into a video using tools like ffmpeg.

Steps:

1. Generate data: Use stim to create a .stim circuit, a .dem error model, and b8 formatted detection events.
2. Generate frames: Run pymatching animate specifying the input files and output directory.
3. Render video: Use ffmpeg to convert the SVG frames into an .mp4 video.

Example animation command:

pmatching animate \
    --dem_in error_model.dem \
    --dets_in detection_events.b8 \
    --dets_in_format b8 \
    --held_frames_per_event 1 \
    --held_frames_at_start 10 \
    --held_frames_at_end 10 \
    --max_growth_between_frames 25 \
    --pixels_per_unit_length 20 \
    --out_dir out_frames

To run the C++ test suites, use the following commands:

Unit Tests:

cmake .
make pymatching_tests
./pymatching_tests

Performance Benchmarks:

cmake .
make pymatching_perf
./pymatching_perf

Benchmark Flags:

• --target_seconds=#: Change the duration of each benchmark.
• --only=name: Run a specific benchmark by name.
• --only=prefix*: Run all benchmarks starting with a specific prefix.

You can install or upgrade to the latest version of PyMatching using pip from PyPI.

pip install pymatching --upgrade