⚛️ quantum physics

An almost-linear time decoding algorithm for quantum LDPC codes under circuit-level noise

This paper introduces the BP+OTF algorithm, an almost-linear time decoder for quantum LDPC codes under circuit-level noise that combines belief propagation with an ordered Tanner forest post-processing stage and a detector error model sparsification technique to achieve logical error suppression comparable to state-of-the-art decoders while maintaining efficient runtime.

Original authors: Antonio deMarti iOlius, Imanol Etxezarreta Martinez, Joschka Roffe, Josu Etxezarreta Martinez

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Antonio deMarti iOlius, Imanol Etxezarreta Martinez, Joschka Roffe, Josu Etxezarreta Martinez

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 fix a giant, incredibly complex jigsaw puzzle. But there's a catch: the pieces are constantly changing shape, the picture is blurry, and you have to solve it in the blink of an eye. This is the challenge of Quantum Error Correction (QEC). Quantum computers are powerful, but they are fragile; tiny glitches (noise) can ruin their calculations. To fix them, we need a "decoder" that looks at the clues (called syndromes) and figures out exactly which pieces are broken, all in real-time.

This paper introduces a new, super-fast decoder called BP+BP+OTF. Here is how it works, broken down into simple concepts:

1. The Problem: The "Noisy" Puzzle

In a quantum computer, we don't just look at the final picture; we check the puzzle periodically to see if pieces have shifted. However, the tools we use to check are also noisy. This creates a "circuit-level" mess where a single mistake can trigger a chain reaction of false alarms.

Traditional methods to fix this are like trying to solve the puzzle by checking every single possible combination of pieces. It's accurate, but it's slow. If you have a puzzle with thousands of pieces, these slow methods take too long, and the quantum computer crashes before you finish.

2. The First Step: The "Gut Feeling" (Belief Propagation)

The authors start with a method called Belief Propagation (BP). Think of this as a team of detectives passing notes around a room.

Each detective looks at a clue and whispers, "I think this piece is broken."
They pass this information to their neighbors.
If enough neighbors agree, they become confident.

This is fast (like a whisper network), but sometimes the detectives get stuck in a loop. They might keep passing the same wrong idea back and forth, never agreeing on a solution. In math terms, the graph of clues has "loops" that confuse the system.

3. The Second Step: The "Sparsification" (Making the Map Simpler)

The paper introduces a clever trick called Sparsification.

Imagine the map of clues is a dense, tangled forest with thousands of paths. It's hard to find a way out.
The authors use a special "transfer matrix" (like a translator) to redraw the map. They remove the tangled, confusing paths and keep only the most direct, essential routes.
Crucially, they don't just throw away information; they translate the "gut feelings" from the first fast round into this new, simpler map. This ensures the new map still knows where the trouble spots are, just without the confusing detours.

4. The Third Step: The "Tree Cutter" (Ordered Tanner Forest)

If the detectives are still stuck, the authors bring in a special tool called OTF (Ordered Tanner Forest).

Imagine the tangled forest again. The OTF algorithm is like a gardener with a very specific rule: "Cut down any tree branch that creates a loop."
It looks at the clues, ranks them by how likely they are to be the culprit (based on the "gut feelings" from the first step), and starts cutting.
It keeps cutting until the remaining structure is a perfect tree (or a forest of trees). In a tree structure, there are no loops.
Why does this matter? In a loop-free tree, the "whisper network" (Belief Propagation) is guaranteed to work perfectly. It can find the solution immediately because there are no confusing circles to get stuck in.

5. The Result: Fast and Accurate

The paper tested this BP+BP+OTF method on two types of quantum puzzles:

Bivariate Bicycle Codes: A complex, modern type of quantum code.
Surface Codes: The standard type used by many labs today.

The Findings:

Speed: The new decoder is almost linear in speed. This means if you double the size of the puzzle, it takes roughly double the time (instead of the time growing exponentially like a snowball). It was found to be 10 times faster than the current best standard methods for certain codes.
Accuracy: Despite being so much faster, it is just as good at fixing errors as the slow, heavy-duty methods. It successfully suppressed errors to the same level as the "gold standard" decoders.

The Big Picture Analogy

Think of the old way of decoding as a slow, meticulous detective who checks every single file in a massive library to find a clue. It's accurate, but it takes hours.

The new BP+BP+OTF method is like a smart, fast detective who:

Quickly scans the library to get a hunch (BP).
Asks a librarian to throw away all the irrelevant, confusing books and give them a streamlined list (Sparsification).
If they are still stuck, they use a laser cutter to slice away any confusing connections until only a straight, clear path remains (OTF).
They then walk down that straight path to find the answer instantly.

The paper claims this method allows quantum computers to fix their own mistakes in real-time, which is a critical step toward building useful, fault-tolerant quantum machines.

Technical Summary: An Almost-Linear Time Decoding Algorithm for Quantum LDPC Codes under Circuit-Level Noise

Problem Statement
The practical realization of fault-tolerant quantum computing requires real-time decoding of quantum error correction (QEC) syndromes, often within microsecond timescales. While Belief Propagation (BP) offers a fast, linear-time ( $O(n)$ ) decoding approach suitable for Low-Density Parity-Check (LDPC) codes, it frequently fails to converge on Quantum LDPC (QLDPC) codes due to degenerate errors and trapping sets. Existing high-performance decoders, such as Ordered Statistics Decoding (BP+OSD) or matching-based decoders, often rely on matrix inversion techniques that increase worst-case runtime complexity to $O(n^3)$ , creating a bottleneck for real-time hardware implementation. Furthermore, decoding under circuit-level noise (as opposed to phenomenological noise) introduces complex error propagation mechanisms that are difficult to handle with standard BP, particularly when the detector error model (DEM) contains high-weight columns and short loops that hinder post-processing strategies.

Methodology
The authors propose a hybrid decoding framework, BP+BP+OTF, designed to achieve almost-linear time complexity while maintaining high error suppression under circuit-level noise. The methodology consists of three primary stages:

Detector Graph Sparsification:
The authors introduce a technique to map the full detector error model ( $H_{dem}$ ), which relates circuit fault mechanisms to syndrome measurements, to a sparsified detector graph ( $H_{sdem}$ ). This sparsified graph has a maximum column weight comparable to the code's parity-check matrices (typically $\leq 2$ for surface codes or low constants for QLDPC).
- A transfer matrix ( $A_{tr}$ ) is constructed to map the full DEM to the sparsified DEM. This matrix ensures that the logical action of errors is preserved and allows for the translation of soft information (error probabilities) from the full graph to the sparsified graph.
- The sparsification reduces the number of columns (error mechanisms) and eliminates short loops, making the graph more amenable to tree-based post-processing.
Two-Stage Belief Propagation (BP+BP):
- Stage 1: Standard BP is applied to the full detector graph to extract initial soft information regarding error probabilities.
- Stage 2: The soft information from Stage 1 is mapped to the sparsified detector graph using the transfer matrix. A second round of BP is executed on this sparsified graph. This stage benefits from a non-uniform error channel derived from the first round, which accelerates convergence.
Ordered Tanner Forest (OTF) Post-Processing:
If the BP stages fail to satisfy the syndrome, the OTF algorithm is invoked on the sparsified graph.
- Mechanism: The OTF algorithm uses a modified Kruskal's algorithm to construct an ordered spanning forest. It sorts qubits (columns of the parity check matrix) based on their posterior error probabilities (from the BP output) and iteratively adds them to the graph, discarding any column that would introduce a loop.
- Convergence: The resulting graph is a forest (a collection of trees). Since BP is guaranteed to converge on tree-like structures, a final round of BP on this ordered forest is guaranteed to find a solution if the syndrome lies within the image of the reduced matrix.
- Complexity: The sorting and forest construction steps have a complexity of $O(n \log n)$ , and the final BP step is $O(n)$ , resulting in an overall almost-linear time complexity.

Key Contributions

OTF Post-Processor: The introduction of the Ordered Tanner Forest algorithm as a post-processor that avoids matrix inversion, offering an alternative to $O(n^3)$ inversion-based methods like BP+OSD.
Sparsification with Transfer Matrices: A novel procedure to map circuit-level detector error models to sparser graphs while preserving critical error propagation information via a transfer matrix. This allows the decoder to leverage the structure of the full circuit noise model without being hindered by its complexity.
BP+BP+OTF Architecture: A unified decoder that combines standard BP, sparsified BP, and OTF post-processing, specifically optimized for circuit-level noise.
Hardware Viability: The algorithm relies on standard BP and Kruskal's algorithm, both of which are well-suited for implementation on off-the-shelf Application-Specific Integrated Circuits (ASICs) or Field-Programmable Gate Arrays (FPGAs).

Results
The authors benchmarked the BP+BP+OTF decoder using Monte Carlo simulations on bivariate bicycle codes and rotated surface codes under depolarizing circuit-level noise.

Performance: The decoder achieves logical error suppression comparable to state-of-the-art decoders. For bivariate bicycle codes, it matches the performance of BP+OSD-0. For surface codes, it achieves suppression comparable to Minimum-Weight Perfect Matching (MWPM) and significantly outperforms BP+OSD-0.
Speed: The implementation demonstrates a speedup of more than 10x compared to a standard BP+OSD implementation (specifically referencing the implementation in [27]) when decoding bivariate bicycle codes.
Efficiency: For surface codes, the decoder achieves reliable decoding with a very small number of iterations (e.g., 107 total BP iterations for a distance-17 code).
Sparsification Efficacy: Experiments showed that while applying BP directly to the sparsified model without the initial full-graph round degrades performance, the hybrid BP+BP approach recovers the performance of the full-model decoder while reducing average decoding time by a factor of three.

Significance
The paper claims that BP+BP+OTF represents a significant step toward the real-time decoding requirements of fault-tolerant quantum computers. By achieving almost-linear time complexity ( $O(n \log n)$ ) without sacrificing the error thresholds of slower, inversion-based methods, the algorithm addresses the critical bottleneck of decoding latency. The authors emphasize that the decoder's reliance on standard, well-understood algorithms (BP and Kruskal's) makes it a highly attractive candidate for hardware acceleration, potentially enabling the construction of fault-tolerant systems with lower development costs and higher scalability compared to complex, specialized decoders. The work also suggests that the sparsification technique could benefit other decoder families beyond the specific BP+BP+OTF architecture proposed.