Evolutionary BP+OSD Decoding for Low-Latency Quantum Error Correction

Heeyoul Kwak, Seong-Joon Park, Hyunwoo Jung, Jeongseok Ha, Jae-Won KimarXiv 2025 · DOI · arXiv

Abstract

Quantum Error Correction (QEC) is essential for fault-tolerant quantum computing but is constrained by the need for low-latency decoding. While Belief Propagation (BP) combined with Ordered Statistics Decoding (OSD) offers high accuracy, the computational overhead of OSD and the sub-optimal performance of BP on degenerate quantum codes remain significant hurdles. We present Evolutionary BP (EBP), a method that utilizes Differential Evolution (DE) to optimize BP weights for end-to-end performance with OSD. Our results demonstrate that EBP achieves state-of-the-art accuracy with up to 63% less computational effort and significantly lower latency, requiring as few as five iterations to outperform standard BP+OSD.

Introduction

Quantum computers are inherently susceptible to noise, necessitating robust Quantum Error Correction (QEC) to protect logical information. A critical challenge in QEC is the "ticking clock" problem: a decoder must identify and correct physical errors faster than the qubits lose their quantum state (the coherence time).

Currently, the Belief Propagation (BP) algorithm is a preferred candidate for decoding due to its linear scaling and speed. However, BP struggles with "degeneracy," a quantum phenomenon where distinct physical errors produce identical syndromes. To mitigate this, researchers typically employ a two-stage approach: BP followed by Ordered Statistics Decoding (OSD). While the BP+OSD combination is highly accurate, the OSD stage is computationally expensive. Previous attempts to optimize this pipeline using deep learning (Neural BP) have been hindered by the fact that OSD is a non-differentiable process, making standard gradient descent optimization impossible. This paper introduces a novel evolutionary approach to overcome this bottleneck.

Methodology

Evolutionary BP (EBP)

The authors propose Evolutionary BP (EBP), which replaces gradient-based training with Differential Evolution (DE)—a metaheuristic search algorithm. By treating the BP+OSD pipeline as a "black box," the researchers can optimize the internal weights of the BP algorithm to maximize the success rate of the subsequent OSD stage.

  1. Trainable Weights: Weights are integrated into the messages passed within the BP algorithm to refine the probability distributions of potential errors.
  2. Differential Evolution: The optimization process involves a population of weight sets that undergo mutation and crossover. Only the "fittest" individuals—those resulting in the lowest Logical Error Rate (LER) when paired with OSD—survive to the next generation.
  3. Edge-Indexed Weight Sharing: To ensure scalability, the authors developed a weight-sharing technique based on the degree and index of connections within the code's parity-check graph. This allows a weight set optimized on a small quantum code to be effectively transferred to much larger codes.

Experimental Evaluation

The EBP decoder was evaluated against two primary classes of quantum codes:

  • Rotated Surface Codes: The current industry standard, tested at distances ranging from $d=3$ to $d=13$.
  • Bivariate Bicycle QLDPC Codes: Modern, high-rate codes ($[[72, 12, 6]]$, $[[90, 8, 10]]$, and $[[144, 12, 12]]$) that are central to current scaling efforts in quantum hardware.

Key Results and Discussion

Ultra-Low Latency and Efficiency

EBP+OSD demonstrates a significant reduction in the number of iterations required for convergence. The decoder achieves superior results in just 5 iterations compared to the 32 iterations typically required by standard BP+OSD. Furthermore, because EBP is more effective at resolving errors in the first stage, the computationally intensive OSD stage is triggered far less frequently. This leads to a reduction in total computational complexity of 35% to 63% across the tested codes.

Performance Gains and Thresholds

For surface codes, the physical error rate threshold—the point below which QEC becomes effective—improved from 15.6% to 16.5%. Dramatic improvements were also observed in the pseudo-thresholds of QLDPC codes, indicating that EBP is particularly well-suited for modern, high-performance code architectures.

Transferability

A significant finding of this research is the transferability of learned weights. Weights optimized for a small surface code ($d=7$) were found to perform optimally when applied to a much larger code ($d=13$). This suggests that the evolutionary process captures fundamental structural features of the code that are independent of its specific size.

Conclusion

Evolutionary BP+OSD represents a major step toward real-time quantum error correction. By optimizing the decoder end-to-end, the researchers have slashed computational overhead and latency while improving error-correction performance. Future work will focus on testing EBP under biased noise models and implementing the algorithm on FPGA or ASIC hardware to meet the microsecond-level latency requirements of production-scale quantum computers.

Summary updated

Abstract

Quantum error correction (QEC) for fault-tolerant quantum computing requires a balanced decoding solution that offers high performance, low complexity, and low latency. However, the de facto standard, belief propagation (BP) combined with ordered statistics decoding (OSD), suffers from excessive iterations in the BP stage and high complexity in the OSD stage. To address these challenges, we propose an evolutionary BP (EBP) decoder optimized via a differential evolution (DE) algorithm. By leveraging the gradient-free nature of DE, we enable end-to-end optimization of the EBP+OSD structure to maximize overall performance. In addition, a multi-objective selection rule is introduced to suppress frequent OSD activation, significantly reducing complexity overhead. Experimental results on surface codes and quantum low-density parity-check (QLDPC) codes demonstrate that EBP plus OSD simultaneously achieves superior decoding performance and substantially lower complexity compared to conventional BP plus OSD, particularly in stringent low-latency regimes.
BibTeX
@misc{kwak2025evolutionary,
  author = {Heeyoul Kwak and Seong-Joon Park and Hyunwoo Jung and Jeongseok Ha and Jae-Won Kim},
  title = {{Evolutionary BP+OSD Decoding for Low-Latency Quantum Error Correction}},
  year = {2025},
  eprint = {2512.18273},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2512.18273},
}
Figure