This paper discusses a critical challenge in quantum computing: protecting quantum information using error-correcting codes due to the inherent imperfections in quantum devices. For quantum computers to effectively implement complex algorithms like Shor’s factoring algorithm, they need to perform over 10 billion logical operations with extremely low error rates (less than 10^-10).
The primary focus is on quantum stabilizer codes, particularly those constructed from sparse graphs, including surface codes, toric codes, color codes, random bicycle codes, and Generalized Hypergraph-Product (GHP) codes. While several decoding methods exist, including Minimum-Weight Perfect Matching (MWPM) and Renormalization Group (RG) decoders, Belief Propagation (BP) has emerged as a promising approach due to its lower computational complexity.
However, BP faces significant challenges when dealing with quantum codes that have high degeneracy (meaning they have many stabilizers of weight lower than their minimum distance). The main issue stems from the Tanner graph of stabilizer codes containing numerous short cycles, which interfere with BP’s message-passing process. While various modifications to BP have been proposed, including neural network pre-training and post-processing techniques, these solutions often become impractical for larger codes.
The authors introduce a new approach called MBP (Memory-effect Belief Propagation), which directly handles quaternary errors and incorporates memory effects. The algorithm is mathematically formulated to include an inhibition functionality, similar to neural networks with negative-weight edges, which helps resist incorrect beliefs passing through the Tanner graph. Importantly, MBP maintains the same computational complexity as conventional BP while significantly improving performance.
The paper also presents an adaptive version called AMBP, which dynamically selects step sizes using an ε-net. This adaptation further enhances the algorithm’s effectiveness without increasing its computational complexity. Another key innovation is the use of fixed initialization, which allows MBP to perform well regardless of the true channel statistics by utilizing a proven energy topology.
Computer simulations demonstrate MBP’s superior performance compared to conventional BP across various quantum codes, including quantum bicycle codes, highly-degenerate GHP codes, and surface/toric codes. Particularly noteworthy are the achieved error thresholds of 16% for surface codes and 17.5% for toric codes when dealing with depolarizing errors.
This work represents a significant advancement in quantum error correction, addressing the long-standing challenge of effectively decoding highly degenerate quantum codes while maintaining computational efficiency. The success of MBP suggests that belief propagation, when properly modified, can be a powerful tool for quantum error correction, contrary to previous skepticism about its effectiveness for topological codes.
npj Quantum Information, Published online: 14 September 2022; doi:10.1038/s41534-022-00623-2
