Hyper Blossom

Hyper Blossom (HyperBlossom in the paper) generalizes the blossom approach behind MWPM decoding from graphs to hypergraphs, making it applicable to general quantum low-density parity-check (qLDPC) codes and correlated error mechanisms.

A new graph problem for QEC

We formulate most-likely-error decoding as a minimum-weight parity factor (MWPF) problem: choose a minimum-weight set of hyperedges whose incident parities reproduce the measured syndrome. Unlike an ordinary decoding graph, a hypergraph can represent an error that triggers more than two detectors without splitting it into independent graph edges.

Mathematical guarantees, with explicit conditions

HyperBlossom uses a primal-dual linear-programming framework inspired by the blossom algorithm. The paper supplies mathematical proofs of optimality under stated conditions, as well as certifiable bounds on proximity to the optimum.

A feasible parity factor whose weight meets the dual lower bound is certified optimal; a remaining primal-dual gap bounds its suboptimality. General hypergraph MWPF is NP-hard, so these guarantees should not be confused with an unconditional claim of efficient exact decoding for every hypergraph.

Open-source implementation

Our implementation, Hyperion, is available in the MWPF repository, with a Rust core and Python bindings distributed as mwpf. Clustering targets almost-linear average runtime at low physical error rates.

Explore the interactive decoding demo or read the paper for the framework, proofs, and benchmarks.