Fusion Blossom: Parallel MWPM Algorithm for QEC

Minimum-Weight Perfect Matching (MWPM) decoders are widely used for quantum error correction (QEC) decoder due to their high accuracy and polynomial time complexity. Existing MWPM decoders, however, have insufficient throughput for superconducting qubits, which require almost one million measurement rounds per second. We report an MWPM algorithm of almost linear complexity given the rare and randomly distributed local quantum errors. We also report a parallel implementation of this algorithm, called Fusion Blossom [1], which leverages parallel computing resources to further improve the throughput. We report the decoding speed on a d=21 CSS surface code with phenomenological noise model p=0.5% and 1e5 measurement rounds. On a 64-core machine, Fusion Blossom improves the throughput by 41x and achieves an average decoding time of 0.7 us per measurement round or 58 ns per non-trivial measurement. Importantly, Fusion Blossom can support even larger code distances by using more parallel computing resources available from a cluster of computers. Fusion blossom is open-source and implemented in the Rust programming language, with a Python package “fusion-blossom” [2]. It supports arbitrary user-defined decoding graphs and embeds a 3D visualization tool.

[1] https://github.com/yuewuo/fusion-blossom

[2] https://pypi.org/project/fusion-blossom/