Frontier decoder for quantum LDPC codes

Frontier is a pruned dynamic-programming decoder for sparse quantum decoding problems, including quantum LDPC parity-check matrices and detector-error-model matrices. This Frontier decoder approximates logical maximum-likelihood decoding by processing fault variables in an order, merging prefixes with the same active residual syndrome and logical label, and pruning a scored frontier of boundary states.

For a short human-readable and agent-readable orientation card, see docs/FRONTIER_CARD.md.

Why Frontier?

• approximates logical/coset posterior inference, not only most-likely-error search;
• merges equivalent boundary states before pruning;
• is geometry-agnostic at the matrix/DEM level;
• supports BB144/Gross and surface-code DEM workflows in this repository.

Decoder style	Retained object	Degeneracy handling	Typical role
BP / min-sum	Tanner-graph messages and local beliefs	Mostly implicit through local marginals	Fast iterative baseline or preconditioner
BP+OSD / BP+LSD	BP reliabilities plus an ordered or localized postprocessing list	Searches around BP-ranked candidates	Strong sparse-matrix decoder family
Beam / representative search	Candidate error representatives	Tracks high-scoring representatives rather than full cosets	Heuristic search over likely errors
Tensor-network / variable elimination	Tensors, separators, or eliminated-variable tables	Sums over eliminated variables, exactly or with truncation	Near-ML reference for structured or low-width instances
Frontier	Boundary states keyed by active residual syndrome and logical label	Merges equivalent prefixes and sums scores before pruning	Pruned logical/coset posterior decoder for supported QLDPC and DEM matrices

See docs/DECODER_POSITIONING.md for a short guide to classifying Frontier relative to BP+OSD, representative search, beam search, Tesseract-like search, tensor-network decoding, and variable elimination.

30-second quickstart

python3 -m venv .venv
source .venv/bin/activate
python -m pip install -U pip setuptools wheel
python -m pip install -e .
python setup.py build_ext --inplace
python -m pytest -q
frontier-smoke --K 16 --Delta 100 --shots 3

Canonical citation

If you use this software, please cite this repository using CITATION.cff and cite the associated paper arXiv:2606.20513, "Approximating optimal decoding of quantum LDPC codes with narrow frontiers."

For agents

Start with README.md, docs/FRONTIER_CARD.md, docs/DECODER_POSITIONING.md, docs/ARCHITECTURE.md, and AGENTS.md. Use llms.txt for a compact summary intended for LLM agents and indexing tools. Do not infer removed research modules, and do not fabricate benchmark values.

Scope

This repo is scoped to running the frontier decoder on BB/Gross and surface-code detector-side matrices. It intentionally ships only:

• frontier Python wrappers and the C++ native extension
• BB144/Gross, generalized-bicycle, rotated-surface, and planar surface-code matrix/DEM builders
• DEM inspection, replay, smoke, and BB144/Gross benchmark CLIs
• small tests and reproducibility notes

Legacy BP/min-sum decoder families, triangle-quotient decoders, polar DEM experiments, and old research benchmark harnesses are not part of this export. See docs/FILE_SCOPE.md for the file-by-file audit.

Repository Map

• docs/FRONTIER_CARD.md: short human/agent-readable decoder card.
• docs/DECODER_POSITIONING.md: short positioning guide relative to BP+OSD, beam/representative search, tensor-network decoding, and variable elimination.
• docs/ARCHITECTURE.md: architecture guide for humans and agents.
• docs/FILE_SCOPE.md: retained-file audit and removed-file categories.
• docs/COMMANDS.md: console-script command index.
• docs/ENVIRONMENT.md: supported environment variables and native debug toggles.
• docs/REPRODUCIBILITY.md: smoke and publication-grade reproducibility guide.
• docs/BENCHMARK_SCHEMA.md: CSV/JSON schema for benchmark result summaries.
• docs/ASSET_PROVENANCE.md: bundled-asset provenance status.
• docs/RELEASE.md: release and archival checklist.
• docs/VISIBILITY_RELEASE_CHECKLIST.md: discoverability, citation-hygiene, release-note, archive, and announcement checklist.
• docs/ACADEMIC_METADATA.md: declared academic metadata status.
• paper/plots/README.md: paper-plot reproduction status, commands, and data policy.
• paper/plots/manifest.csv: figure-to-data/script/output manifest.
• paper/plots/data/: minimal plot-ready summary tables, sidecar metadata, and checksums when paper data are available.
• paper/plots/scripts/: plot reproduction entry points.
• docs/WORKLOG.md: agent-readable maintenance log.
• examples/README.md: tiny runnable examples.
• CITATION.cff: citation metadata for citable releases.
• codemeta.json: CodeMeta software metadata derived from declared repo facts.
• AUTHORS.md: software authorship and contributor-list policy.
• SECURITY.md: minimal security reporting policy for research software.
• ACKNOWLEDGEMENTS.md: funding, institutional, and upstream-software acknowledgements.
• CONTRIBUTING.md: human-facing contribution guide.
• CHANGELOG.md: release-level change log.
• LICENSE: Apache License 2.0; see docs/LICENSING.md for notes on scope and third-party material.

Console script	Implementation
frontier-smoke	tools/frontier_decoder.py
frontier-dem-info	tools/dem_loader.py
frontier-sample-rows	tools/frontier_sample_rows.py
frontier-replay	tools/frontier_sample_replay.py
frontier-bb144-benchmark	tools/frontier_bb144_benchmark.py

Environment Notes

For exact reproducibility constraints, see constraints/README.md. Once a known-good constraints file exists, install with:

python -m pip install -e . -c constraints/<validated-environment>.txt

The committed constraints/py314-macos-validated.txt file is one validated environment, not a default for all users.

CI validates Ubuntu Python 3.11/3.12 and macOS Python 3.12. The Ubuntu Python 3.12 CI environment is validated in GitHub Actions, but this checkout has not captured exact Ubuntu pins yet. See constraints/py312-ubuntu-ci.TODO.md before adding a Linux constraints file.

Paper Plot Reproduction

Paper-specific plot reproduction lives under paper/plots/. The current checkout contains minimal plot-ready summary tables and JSON sidecars for the recorded frontier_decoder2.tex figure inventory, plus committed Matplotlib renderers for every current paper figure. The generated PNGs are ignored by git unless maintainers intentionally add reference images elsewhere.

python paper/plots/scripts/reproduce_plots.py --list
python paper/plots/scripts/reproduce_plots.py --all --strict --out-dir /tmp/frontier-paper-plots

Rows marked reproducible regenerate their listed output from committed summary data and a committed renderer. Rows marked support-data are committed companion inputs consumed by another renderer and are skipped by --all. Publication-scale raw sample corpora are not committed here, so plot reproducibility is separate from simulation reproduction.

Citation And Acknowledgements

The canonical citation is recorded in CITATION.cff. The associated paper is:

Anthony Leverrier and Rüdiger Urbanke, "Approximating optimal decoding of quantum LDPC codes with narrow frontiers," arXiv:2606.20513 [quant-ph], 2026. https://arxiv.org/abs/2606.20513

The repository acknowledgements, including funding, institutional details, and the OpenAI Codex large-language-model acknowledgement, are recorded in ACKNOWLEDGEMENTS.md.

Python API

New examples and user code should prefer the frontier.* public API:

from frontier import FrontierModel, decode_frontier
from frontier.dem import load_dem_family
from frontier.progressive import (
    FactorTransition,
    OutcomeTransition,
    build_frontier_layout,
    columns_from_factor_transitions,
)

family = load_dem_family(
    backend="rotated_surface_d3",
    p_location=0.001,
    scope="memory_X",
    column_order="deadline_reorder",
)
print(f"{family.matrix_rows}x{family.matrix_cols}")

Lower-level grosscode.* builders remain available for matrix construction, and tools.* imports remain supported for console scripts and backward compatibility.

DEM Matrices

Use frontier-dem-info to build a supported detector-side matrix family and print the dimensions used by the decoder:

frontier-dem-info \
  --backend bravyi_depth7 \
  --p-location 0.004 \
  --column-order deadline_reorder

For the accepted BB144/Gross split-sector DEM benchmark, the expected dimensions are D_X = D_Z = 936 x 8784, O_X = O_Z = 12 x 8784, with 12 noisy syndrome-extraction rounds.

This repo bundles the Gross [[144,12,12]] CSS matrices, the BB144/Gross memory X/Z Stim circuits for the exact rates listed below, and a materialized split-sector DEM snapshot for bravyi_depth7, p=0.001. The bundled p=0.001 DEM files live under grosscode/assets/gross144/dem/:

• bravyi_depth7_p0p001_memory_X_detector.npz
• bravyi_depth7_p0p001_memory_X_logical.npz
• bravyi_depth7_p0p001_memory_X_priors.npy
• bravyi_depth7_p0p001_memory_Z_detector.npz
• bravyi_depth7_p0p001_memory_Z_logical.npz
• bravyi_depth7_p0p001_memory_Z_priors.npy

The bundled BB144/Gross Stim circuit rates are exactly 0.0005, 0.001, 0.002, 0.003, 0.004, 0.005, and 0.006, for both memory_X and memory_Z.

For custom Gross assets, set GROSSCODE_ASSET_ROOT to a directory containing:

• gross_code/HX_Gross_144_12_12.mtx
• gross_code/HZ_Gross_144_12_12.mtx
• stim_circuits/BB[[144,12,12]],memory_X,error_rate=...,syndrome_rounds=12.stim
• stim_circuits/BB[[144,12,12]],memory_Z,error_rate=...,syndrome_rounds=12.stim

DEM Replay

Use frontier-sample-rows to generate independent detector-side DEM sample rows from the same matrices and priors used by the decoder:

frontier-sample-rows \
  --out sample_rows.csv \
  --backend bravyi_depth7 \
  --p-location 0.001 \
  --shots 1000 \
  --seed 20260615

Then use frontier-replay on those matched sample rows:

frontier-replay \
  --sample-rows sample_rows.csv \
  --out-dir results/frontier_replay \
  --code bb144 \
  --backend bravyi_depth7 \
  --p-location 0.001 \
  --shot-start 0 \
  --shot-stop 999 \
  --K 512 \
  --Delta 12 \
  --direction-mode fwd_bwd_committee \
  --engine native_binary \
  --column-order deadline_reorder \
  --backward-column-order backward_deadline_reorder \
  --cpus 1 \
  --progress-every-shards 1

For CPU-saturated runs on macOS, launch from Terminal and set FRONTIER_NATIVE_BATCH_THREADS to the number of native worker threads you want the extension to use.

Benchmark

frontier-bb144-benchmark \
  --sample-rows sample_rows.csv \
  --backend bravyi_depth7 \
  --p-location 0.001 \
  --column-order deadline_reorder \
  --K 512 \
  --Delta 12 \
  --payload replay

The benchmark path reports the accepted Gross split-sector DEM dimensions: D_X = D_Z = 936 x 8784, O_X = O_Z = 12 x 8784, with 12 noisy rounds. Use docs/BENCHMARK_SCHEMA.md for the documented CSV/JSON columns expected in human- and agent-readable benchmark summaries.

Reproducing BB144/Gross DEM Results

For the accepted BB144/Gross split-sector DEM benchmark, p is passed as --p-location. Use --backend bravyi_depth7 unless you intentionally want a non-default circuit family. The accepted detector-side matrices are D_X = D_Z = 936 x 8784, O_X = O_Z = 12 x 8784, with 12 noisy syndrome-extraction rounds.

The default Gross benchmark works from the bundled files. Set GROSSCODE_ASSET_ROOT only when intentionally overriding those bundled assets with a custom asset root.

To reproduce a published full-frame row exactly, use the same matched sample_rows.csv that was used for that row and pass the intended probability as --p-location. This repo does not check in large sample corpora. The CSV must contain both memory_X and memory_Z rows for the requested shot ids and must include at least: scope, shot, seed, truth_syndrome, and truth_logical.

To produce a fresh reproducible 10k-shot BB144/Gross DEM sample at p=0.001 and decode it with Delta=12, K=512, and the forward/backward committee:

frontier-sample-rows \
  --out results/bb144_p0p001_sample_rows.csv \
  --backend bravyi_depth7 \
  --p-location 0.001 \
  --shots 10000 \
  --seed 20260615 \
  --progress-every-rows 1000

frontier-replay \
  --sample-rows results/bb144_p0p001_sample_rows.csv \
  --out-dir results/bb144_p0p001_frontier_replay_k512_Delta12 \
  --code bb144 \
  --backend bravyi_depth7 \
  --p-location 0.001 \
  --shot-start 0 \
  --shot-stop 9999 \
  --K 512 \
  --Delta 12 \
  --direction-mode fwd_bwd_committee \
  --engine native_binary \
  --column-order deadline_reorder \
  --backward-column-order backward_deadline_reorder \
  --cpus 10 \
  --shards-per-side 20 \
  --native-batch-size 64 \
  --progress-every-shards 1

Replay writes summary_by_scope.csv, per_shot_rows.csv, combined_per_shot_rows.csv, run_metadata.json, and report.md. The combined row in summary_by_scope.csv is the full logical frame error rate over paired memory_X/memory_Z shots.

How to tell the BB144/Gross reproduction worked

Before decoding, this command should confirm that the bundled detector-side DEM is being used:

frontier-dem-info \
  --backend bravyi_depth7 \
  --p-location 0.001 \
  --column-order deadline_reorder

Expected dimensions:

scope,detector_matrix,logical_matrix,columns,edges,noisy_rounds,total_rounds,column_order
memory_X,936x8784,12x8784,8784,30672,12,13,deadline_reorder
memory_Z,936x8784,12x8784,8784,30672,12,13,deadline_reorder

For the 10k-shot command above:

• frontier-sample-rows writes 20,000 side rows: 10,000 memory_X rows and 10,000 memory_Z rows, paired by shot id.
• frontier-replay runs 40 shard tasks when --shards-per-side 20 is used: 20 shards for memory_X and 20 shards for memory_Z.
• run_metadata.json should contain frontier_native_available: true, engine: "native_binary", K: 512, Delta: 12, direction_mode: "fwd_bwd_committee", and status: "complete".
• report.md should state the matrix as D_X=D_Z=936x8784, O_X=O_Z=12x8784, with 12 noisy rounds.
• summary_by_scope.csv should contain rows for memory_X, memory_Z, and combined. Use the combined row for the full logical frame error rate.
• The useful audit columns are fail_total, logical_fail, syndrome_fail, exception_fail, fer, fer_per_round, transition_evals_total_mean, engine_requested, and engines_seen.

At p=0.001, a 10k-shot sample is mainly a reproducibility and smoke-scale decoder check. It is too small to measure the low FER accurately; if the run has no failures, report that as "below the resolution of this 10k-shot sample", not as evidence that the FER is zero. Use larger samples, higher probabilities, or a fixed published sample-row corpus when the goal is a precise FER estimate.

Wall-clock timing is machine-dependent. If reporting timing, also report the machine, Python version, worker count, whether frontier_native_available was true, and the native_batch_size. For machine-independent comparisons, prefer the transition-evaluation columns in summary_by_scope.csv.

If the replay falls back from the native engine or reports that the native extension is unavailable, rerun:

python setup.py build_ext --inplace

from the activated virtual environment, then rerun the smoke test and replay.

Matrices

The repo bundles the static Gross/BB144 files needed for the default bravyi_depth7, p=0.001 reproduction, and uses builders/generators for the other supported matrix families.

The following is a low-level matrix-builder example; decoder-facing user code should prefer frontier.dem.

• Gross split-sector detector-side DEM: grosscode.dem.builder.build_split_sector_problem(...) returns D_X, D_Z, O_X, O_Z, priors, and metadata. For backend="bravyi_depth7" and p=0.001, this loads the bundled materialized DEM snapshot. For other bundled public rates, it builds the DEM from the bundled Stim circuits.
• Rotated-surface code-capacity checks: grosscode.codes.rotated_surface.load_rotated_surface_code(...) constructs HX/HZ in repo, and rotated-surface DEMs are generated from Stim rotated_memory_x/z circuits for backends such as rotated_surface_d5.
• Standard planar surface-code checks: grosscode.codes.surface.standard_surface_checks(distance) returns the CSS HX/HZ sparse matrices for the standard planar surface code.

Minimal examples:

from grosscode.codes.surface import standard_surface_checks
from grosscode.dem.builder import build_split_sector_problem

hx, hz = standard_surface_checks(5)
print(hx.shape, hz.shape)

problem = build_split_sector_problem(backend="bravyi_depth7", error_rate=0.004)
print(problem.D_X.shape, problem.D_Z.shape)

License

This repository is licensed under the Apache License 2.0. See LICENSE and docs/LICENSING.md. Third-party dependencies and any explicitly marked third-party files/assets remain under their own licenses. Citation, release, funding, and provenance metadata status is tracked in CITATION.cff, ACKNOWLEDGEMENTS.md, and docs/ACADEMIC_METADATA.md.