🔢 mathematics

Multiple-Bases Belief Propagation List Decoding for Quantum LDPC Codes

This paper introduces the Multiple-Bases Belief-Propagation List Decoder (MBBP-LD), a linear-time quantum LDPC decoding algorithm that generates structured diversity through parallel decoding across multiple redundant parity-check representations, achieving significant error rate reductions compared to existing methods like BP-OSD and BPGD without requiring super-linear post-processing.

Original authors: Sheida Rabeti, Hessam Mahdavifar

Published 2026-05-15

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Sheida Rabeti, Hessam Mahdavifar

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

Imagine you are trying to solve a massive, incredibly complex jigsaw puzzle. But there's a catch: the puzzle pieces are quantum bits (qubits), and the picture is a "Quantum Error-Correcting Code." These codes are like safety nets for quantum computers, designed to catch mistakes (errors) before they ruin a calculation.

The paper introduces a new way to solve these puzzles faster and more accurately. Here is the breakdown using everyday analogies:

The Problem: The "Stuck" Solver

To fix errors in quantum computers, scientists use a method called Belief Propagation (BP). Think of BP as a single detective trying to solve a crime by asking neighbors for clues.

The Issue: In quantum puzzles, the clues are often confusing. The detective gets stuck in "traps" (short cycles in the puzzle structure) or gets confused by "degeneracy" (where many different solutions look exactly the same).
The Old Fix: Previous attempts to fix this involved either:
1. Brute Force (BP-OSD): Hiring a super-intelligent detective who checks every single possibility. This works well but takes forever (too slow for real-time use).
2. Guided Guessing (BPGD): A detective who makes a guess, erases part of the puzzle, and tries again. This is powerful but computationally expensive, like burning down a house to find a lost key.

The New Solution: The "Team of Detectives"

The authors propose a new method called Multiple-Bases Belief-Propagation List Decoding (MBBP-LD).

Instead of sending one detective to solve the puzzle, they send a team of detectives working in parallel. But they don't just send them to the same puzzle; they give each detective a slightly different view of the puzzle.

1. The "Tree" Trick (Structured Diversity)

How do they create these different views?

The Old Way (Random): Previous methods would randomly copy and paste parts of the puzzle rules to confuse the detective. It was like randomly gluing extra pieces onto the puzzle board. It helped a little, but it was messy.
The New Way (Tree Decomposition): The authors use a clever geometric trick. They look at the puzzle's structure (the Tanner graph) and chop it up into tree-like branches.
- Imagine the puzzle is a tangled ball of yarn. The authors carefully untangle specific sections into neat, straight trees.
- In a "tree" (a structure with no loops), a detective can solve the puzzle perfectly.
- By creating multiple different "tree" versions of the same puzzle, the team generates structured diversity. Each detective sees a different, clean version of the problem, making it much harder for them to get stuck in the same trap.

2. The "Voting Booth" (Decision Making)

Once all the detectives finish their work, they each submit a list of their best guesses for the solution.

The system then acts as a Voting Booth.
It looks at who guessed the same answer most often (Frequency).
It also checks if the answer is a "simple" error (low weight) rather than a chaotic mess.
The final answer is the one that wins this vote.

Why is this a Big Deal?

The paper claims this method hits the "sweet spot" that other methods miss:

It's Fast: Unlike the "Brute Force" detective (BP-OSD) who takes hours, this team of detectives works in parallel. The time it takes is roughly the same as the original single detective, just with a bit more muscle.
It's Smarter: It beats the "Guided Guessing" detective (BPGD) in accuracy, especially when errors are rare or moderate.
No Burning Houses: It avoids the heavy computational cost of previous advanced methods. It doesn't need to "burn down the house" (super-linear post-processing) to find the answer.

The Results (The Scoreboard)

The authors tested this on three different sizes of quantum puzzles (codes):

Small to Medium Puzzles: The new method reduced errors by 20% to 30% compared to the best existing methods.
Large Puzzles: It performed just as well as the heavy-duty methods but with much less waiting time.

In a nutshell: The paper says, "Don't just send one detective to get stuck in a loop. Send a team of detectives, give them different 'tree' maps of the problem so they don't get confused, and let them vote on the best answer. It's faster, cheaper, and more accurate."

Technical Summary: Multiple-Bases Belief-Propagation List Decoding for Quantum LDPC Codes

Problem Statement
Quantum Low-Density Parity-Check (QLDPC) codes are critical for scalable fault-tolerant quantum computation due to their sparse parity-check matrices, which minimize qubit interactions. However, the performance of standard Belief Propagation (BP) decoding for QLDPC codes is often degraded by code degeneracy, short cycles, and trapping sets within the Tanner graph. While existing high-performance decoders like BP with Ordered Statistics Decoding (BP-OSD) and Belief Propagation with Guided Decimation (BPGD) offer improved error rates, they suffer from significant drawbacks: BP-OSD requires super-linear post-processing complexity ( $O(n^3)$ ), and BPGD involves high iteration counts and complex decimation steps, leading to increased latency and computational cost. There is a need for a decoding strategy that improves error-rate performance over standard BP while maintaining linear-time complexity and avoiding super-linear post-processing.

Methodology
The paper proposes the Multiple-Bases Belief-Propagation List Decoder (MBBP-LD). This framework extends the classical Multiple-Bases Belief-Propagation (MBBP) concept to the quantum setting by generating structured decoding diversity without relying on random row selection or complex post-processing.

Structured Redundant Representations: Instead of randomly duplicating parity-check rows (as in Augmented Parity-Check decoding), the proposed method constructs multiple redundant parity-check representations using cycle-free subtree decompositions of the Tanner graph.
- The algorithm partitions the check nodes into a collection of maximal subtrees ( $\mathcal{T}$ ) based on a specific permutation of the check nodes.
- A subtree is defined as maximal if adding any adjacent check node would create a cycle.
- For each subtree $t \in \mathcal{T}$ , an augmented parity-check matrix $H^{(t)}$ is formed by appending the submatrix corresponding to the subtree ( $H_t$ ) to the original matrix $H$ .
- Lemma 1 establishes that for check-regular graphs, the number of additional rows introduced is bounded, ensuring the augmentation does not drastically increase complexity.
Parallel Decoding and List Aggregation:
- Multiple BP decoders run in parallel, each operating on a distinct augmented matrix $H^{(t)}$ .
- Decoders that converge within a fixed iteration limit contribute their error estimates to a candidate list $\mathcal{L}$ .
Decision Rule (Frequency-Weighted Scoring):
- A decision function $f_{DM}$ selects the final error estimate from the candidate list.
- The proposed Frequency-Weighted Scoring (FWS) rule assigns a score to each candidate based on its frequency of occurrence in the list and its Hamming weight:
  $\text{Score}(e) = \frac{|\{e' \in \mathcal{L} : e' = e\}|}{w_H(e) + 1}$
- This rule favors candidates that appear repeatedly (indicating robustness across different graph structures) while penalizing high-weight errors. If no decoder converges, the system declares a failure and returns the all-zero vector.

Key Contributions

Structured Diversity: The paper introduces a deterministic, subtree-based method for constructing redundant parity-check representations, contrasting with previous random augmentation approaches. This structure is designed to induce diverse decoding trajectories that mitigate trapping-set effects.
Complexity Preservation: The framework maintains the linear-time complexity and hardware efficiency of standard BP. Under parallel implementation, the decoding latency remains comparable to standard BP, as the number of additional rows is bounded by a constant factor relative to the block length.
Avoidance of Super-Linear Post-Processing: Unlike BP-OSD and BPGD, MBBP-LD avoids $O(n^3)$ or high-overhead decimation stages, offering a more efficient alternative for practical implementation.

Numerical Results
Simulations were conducted on bivariate bicycle codes ( $[[144, 12, 12]]$ and $[[288, 12, 18]]$ ) and the B1 code ( $[[882, 24, 18 \le d \le 24]]$ ) over a binary symmetric channel with independent X-type errors.

Performance Gains: MBBP-LD consistently outperforms BP-OSD and BPGD across various noise regimes.
- For the $[[144, 12, 12]]$ code, it achieves a 3–24% reduction in Logical Error Rate (LER) compared to BP-OSD and 7–17% compared to BPGD.
- For the $[[288, 12, 18]]$ code, reductions reach up to 49% compared to BP-OSD and 36% compared to BPGD.
- For the larger B1 code, MBBP-LD achieves over 91% reduction in LER compared to BP-OSD at $p=0.04$ and up to 66% reduction compared to parallel BPGD.
Efficiency: While BPGD-Serial sometimes shows slightly better LER in low-noise regimes, it incurs significantly higher computational costs (e.g., at $p=0.04$ , BPGD-Serial averages 2.5 iterations per stage but requires repeated decoding, whereas MBBP-LD averages 14.4 total iterations). MBBP-LD maintains an iteration count comparable to standard BP, preserving BP-like latency.
Subtree vs. Random: Comparisons on the $[[288, 12, 18]]$ code show that subtree-based partitions consistently yield lower LER than matched random partitions, with improvements ranging from 2.5% to 9.4%, particularly in low-noise regimes.

Significance and Claims
The paper claims that MBBP-LD successfully bridges the gap between the high performance of complex post-processing decoders and the efficiency of standard BP. By leveraging the tree-like properties of local graph structures to create structured redundancy, the decoder improves convergence and error correction capabilities without sacrificing the linear-time complexity essential for scalable quantum computing. The authors position this as a practical solution that avoids the super-linear overhead of existing high-performance methods while delivering substantial error-rate improvements. Future work is noted to focus on code-specific constructions of redundant checks and refined decision rules.