🔢 mathematics

Learning-Based List Sequential Belief Propagation Decoding of Quantum LDPC Codes

This paper proposes a reinforcement learning-based list sequential belief propagation (RL-LS) decoder for quantum LDPC codes that combines learned variable-node scheduling with a list-based search strategy to overcome challenges like short cycles and degeneracy, thereby achieving superior decoding performance over the depolarizing channel compared to existing methods.

Original authors: Mohsen Moradi, Taejoon Kim, Remi A. Chou

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mohsen Moradi, Taejoon Kim, Remi A. Chou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Fixing Quantum "Static"

Imagine you are trying to listen to a radio station, but the signal is full of static. In the world of quantum computers, this "static" is called noise, and it scrambles the information (qubits) the computer is trying to process. To fix this, scientists use Quantum LDPC codes. Think of these codes as a very smart, redundant way of writing down a message so that even if some letters get smudged or changed, you can still figure out what the original message was.

However, there is a catch. The standard way of fixing these errors (called Belief Propagation or BP) is like a student trying to solve a maze by just guessing and checking. Because the "maze" of quantum codes has many short loops and confusing dead ends (called cycles and degeneracy), the student often gets stuck, goes in circles, or picks the wrong path and gives up.

The Previous Solution: The "Smart Guide"

Before this paper, researchers developed a method called RL-S (Reinforcement Learning-based Sequential).

The Analogy: Imagine the maze has a Smart Guide (an AI trained by Reinforcement Learning). Instead of guessing randomly, the Guide looks at the current situation and tells you exactly which turn to take next to get out of the maze fastest.
The Problem: Even a Smart Guide can make a mistake. Sometimes, the Guide says, "Turn left," because it looks like the best option. But in quantum codes, there's a tricky feature called degeneracy. This means that two different paths might look different locally, but they actually lead to the same correct destination. If the Guide picks the "wrong" looking path (even if it's actually correct), the decoder gets stuck and can't go back to try the other path. It's a "one-way street" approach.

The New Solution: The "Exploratory Hiker" (RL-LS)

This paper proposes a new decoder called RL-LS (Learning-based List Sequential). It takes the Smart Guide and adds a safety net.

1. The "What If" Branch
Instead of just following the Guide's single best advice, the RL-LS decoder does something clever at every step:

Path A (The Main Trail): It follows the Guide's best advice, just like before.
Path B (The "What If" Trail): It asks, "What if the second-best option was actually the right one?" It creates a copy of the current state and softly nudges it toward that second-best option.

2. The Backpack of Options (The List)
Now, instead of walking down one single path, the decoder is walking down multiple paths at once (a "list" of candidates).

Imagine you are hiking with a group of friends. The Guide points to a fork in the road.
Most of the group takes the path the Guide recommends.
A few friends take the second-best path, just in case the Guide was slightly off.
Everyone keeps walking, but they carry a scorecard (called a path metric). This scorecard tracks how much they had to "stray" from the Guide's original advice. If you had to force yourself to take a path that looked very unlikely, your score gets worse.

3. The Pruning (Cutting the Dead Ends)
As the group walks further, the list of paths might get too big. The decoder then acts like a hiking leader:

It looks at everyone's scorecards.
It keeps the paths with the best scores (those that stayed close to the Guide's advice but still explored alternatives).
It cuts off (prunes) the paths that are going nowhere or have terrible scores.
If one of the hikers finds the exit (the error is fixed), the whole group stops and celebrates.

Why This Matters

The paper tested this new "Exploratory Hiker" method on several types of quantum codes. Here is what they found:

Better Success Rate: The new method fixed errors much better than the old "Smart Guide" alone. It was able to escape the "dead ends" that trapped the old method.
Faster than Expected: You might think checking multiple paths would be slow. However, because the new method finds the solution faster (in fewer steps), it actually uses less time overall than older, brute-force methods.
The Sweet Spot: It combines the speed of the AI Guide with the safety of checking multiple possibilities. It's like having a GPS that knows the best route but also has a backup plan ready just in case the GPS is wrong.

Summary

In short, this paper introduces a decoder that doesn't just trust the AI's first guess. Instead, it keeps a small list of "Plan B" options at every step, checks which one is working best, and discards the bad ones. This allows quantum computers to fix their own errors more reliably, even when the noise is confusing and the paths are tricky.

Technical Summary: Learning-Based List Sequential Belief Propagation Decoding of Quantum LDPC Codes

Problem Statement
Quantum Low-Density Parity-Check (QLDPC) codes are promising candidates for fault-tolerant quantum computation due to their sparse stabilizer structure and high encoding rates. However, decoding these codes efficiently remains a significant challenge. Standard Belief Propagation (BP) decoders often fail to converge or converge to logically incorrect solutions when applied to QLDPC codes. This failure stems from two primary factors:

Structural Issues: The commutativity constraints of stabilizer codes induce many short cycles in the Tanner graph, violating the independence assumptions required for standard BP.
Quantum Degeneracy: Distinct Pauli error patterns can yield the same syndrome and represent equivalent recovery operations. Consequently, a decoder need not identify the exact physical error but rather an error in the correct logical coset. This degeneracy creates symmetric pseudo-codewords and trapping sets, causing BP to oscillate or stall.

While reinforcement-learning-based sequential scheduling (RL-S) has shown promise by learning an optimal variable-node update order to improve convergence, it remains a single-trajectory approach. A sequential decoder lacks a mechanism to revisit "near-miss" decisions; if the locally most likely Pauli symbol is chosen early but proves globally suboptimal due to degeneracy, the decoder cannot recover.

Methodology
The authors propose a Learning-Based List Sequential (RL-LS) BP decoder to address the limitations of single-trajectory RL-S. The method extends the existing RL-S framework by maintaining a list of candidate decoding trajectories rather than a single path.

The core mechanism operates as follows:

Sequential Selection: At each decoding step, a learned policy (a frozen Q-table trained offline) selects the next variable node to update based on a local syndrome-driven state representation, identical to the RL-S approach.
List Expansion: Instead of committing to a single update, the decoder generates two candidate continuations for the selected node:
- Ordinary Child: Follows the standard RL-S update, selecting the most likely Pauli symbol based on the local posterior.
- Alternative Child: Softly biases the post-update Log-Likelihood Ratio (LLR) pair toward the second-most likely Pauli symbol. The decoder recomputes the incident local BP messages and sets the variable node to this second-best symbol.
Path Metric and Pruning: Each trajectory is assigned a cumulative path metric $M$ $M$ . The metric penalizes deviations from the locally dominant decision. Specifically, the penalty for taking the second-best branch is the local log-likelihood gap ( $\Delta$ $Δ$ ) between the best and second-best symbols.
- The decoder retains the top $L$ candidates based on a lexicographic ordering of the path metric $M$ and the residual mismatch weight $w$ .
- This pruning strategy ensures that the decoder explores local ambiguities (degeneracy) while prioritizing paths that remain close to the locally dominant evidence.
Termination: The process continues until a path achieves zero residual mismatch (syndrome consistency) or the maximum iteration limit is reached. If no path converges, the decoder returns the surviving path with the best $(M, w)$ pair.

Key Contributions

Novel Decoder Architecture: The paper introduces the RL-LS decoder, which integrates list-based search into the learned sequential scheduling framework. Unlike previous list-based approaches that append heavy post-processing or run parallel bit-flipping after a fixed prefix, RL-LS performs list expansion within the sequential update process itself.
Soft Perturbation Strategy: The authors propose a specific method for generating alternative trajectories by softly biasing LLRs toward the second-best Pauli symbol, rather than hard flipping. This allows the decoder to explore competing hypotheses without discarding the primary learned trajectory.
Cumulative Path Metric: A new metric is defined to rank candidate paths, balancing the likelihood of local decisions against the global requirement for syndrome consistency.
Strict Extension: The proposed decoder is a strict extension of the underlying RL-S decoder; the ordinary RL-S trajectory is always preserved as one candidate in the list, ensuring that the performance of the base decoder is never degraded.

Numerical Results
The authors evaluated the RL-LS decoder on representative QLDPC benchmark codes, including Bivariate Bicycle (BB) codes and A5 codes, over the depolarizing channel.

Performance Gains: Numerical results demonstrate that RL-LS significantly outperforms the underlying RL-S decoder and conventional BP-based methods (such as QBP, QBPGD, and BP-OSD-0) in terms of Block Error Rate (BLER).
Efficiency: The proposed method achieves superior error-correction performance with fewer iterations. For instance, on the [[288, 12, 18]] BB code, RL-LS with a list size $L=8$ and $T=100$ iterations achieved performance comparable to RL-S with $T=1000$ iterations, offering a substantial latency advantage.
Convergence Speed: The learning-based decoders, particularly RL-LS, required significantly fewer average iterations to converge compared to conventional BP-based decoders across various depolarizing probabilities.

Significance and Claims
The paper claims that the RL-LS decoder effectively mitigates the risks of early mistakes in sequential decoding caused by quantum degeneracy and short cycles. By combining the improved convergence of learned sequential scheduling with lightweight list exploration, the method navigates local ambiguities more robustly than single-trajectory approaches.

The authors position this work as a promising direction for improving the reliability of BP-based QLDPC decoding. They emphasize that the approach remains fully within the BP message-passing framework, avoiding the complexity of heavy post-processing stages while offering a favorable trade-off between decoding latency and error-correction performance. The results suggest that integrating list-based search into learned sequential scheduling is a viable strategy for enhancing fault-tolerant quantum architectures.