Fusion Blossom: Fast MWPM Decoders for QEC
Authors:
- 17 September 2023
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 01, 928-938
Abstract
The Minimum-Weight Perfect Matching (MWPM) decoder is widely used in Quantum Error Correction (QEC) decoding. Despite its high accuracy, existing implementations of the MWPM decoder cannot catch up with quantum hardware, e.g., 1 million measurements per second for superconducting qubits. They suffer from a backlog of measurements that grows exponentially and as a result, cannot realize the power of quantum computation. We design and implement a fast MWPM decoder, called Parity Blossom, which reaches a time complexity almost proportional to the number of defect measurements. We further design and implement a parallel version of Parity Blossom called Fusion Blossom. Given a practical circuit-level noise of 0.1%, Fusion Blossom can decode a million measurement rounds per second up to a code distance of 33. Fusion Blossom also supports stream decoding mode that reaches a 0.7 ms decoding latency at code distance 21 regardless of the measurement rounds.Keywords
All Related Versions
Funding Information
- Yale University
This publication has 24 references indexed in Scilit:
- Fault-tolerant weighted union-find decoding on the toric codePhysical Review A, 2020
- Linear-time maximum likelihood decoding of surface codes over the quantum erasure channelPhysical Review Research, 2020
- NISQ+: Boosting quantum computing power by approximating quantum error correction2020
- Quantum error correction for quantum memoriesReviews of Modern Physics, 2015
- Topological Code AutotunePhysical Review X, 2012
- Towards practical classical processing for the surface code: Timing analysisPhysical Review A, 2012
- LEMON – an Open Source C++ Graph Template LibraryElectronic Notes in Theoretical Computer Science, 2011
- Blossom V: a new implementation of a minimum cost perfect matching algorithmMathematical Programming Computation, 2009
- Computing Minimum-Weight Perfect MatchingsINFORMS Journal on Computing, 1999
- Matching, Euler tours and the Chinese postmanMathematical Programming, 1973