Decoding with alternating weighted graph sparsification for quantum low-density parity-check codes

AI summary

Overview

• Research area: Quantum error correction — specifically real-time decoding algorithms for quantum low-density parity-check (qLDPC) codes, combining belief propagation (BP) with detector error model (DEM) sparsification.
• Technical level: Advanced. Familiarity with belief propagation, Tanner graphs, detector error models, and qLDPC code families (bivariate bicycle codes, color codes) is assumed by the paper.
• One-sentence scope: The paper introduces and numerically benchmarks DAWG, an ensemble BP decoder that alternates between a full detector error model and a sparsified copy of it, with an LSD-0 post-processor, on bivariate bicycle and superdense color code circuits.

What This Paper Is About

Belief propagation is central to many qLDPC decoding proposals, but short loops and degeneracy create trapping sets that prevent it from converging, so post-processors or modified message passing are needed. The authors build an ensemble decoder in which BP first runs on the full detector error model, then its posterior log-likelihood ratios are mapped — via many different "transfer matrices" — onto a much smaller, sparsified graph where further BP rounds run. The goal is to reach the accuracy of the best existing BP decoders (RelayBP, Vibe) while invoking the expensive post-processor far less often and on a much smaller graph, which matters for hardware latency.

Key Contributions

1. The DAWG decoder. An ensemble-based BP decoder that combines Tanner graph sparsification with ensembling: BP runs on the full DEM, posteriors are transferred to a sparsified DEM using a different transfer matrix per ensemble member, and a second stage of randomized-schedule serial BP runs on the sparsified graph.
2. Transfer-matrix diversity as a design tool. The paper exploits the fact that the transfer matrix relating the full DEM to its sparsified version is not unique, using a guided exhaustive search that permits higher-order combinations of sparsified DEM columns, then randomly choosing among solutions to build an ensemble of distinct matrices.
3. Schedule randomization borrowed and extended. Serial BP schedules are randomized as in Vibe decoding, and additional diversity comes from the two-stage structure, since distinct schedules are used for the full DEM and the sparsified DEM in each ensemble member.
4. Numerical benchmarking plus a hardware-latency analysis. DAWG+LSD-0 is compared against BP+LSD-0, RelayBP, and Vibe on bivariate bicycle codes and superdense color code circuits, and an FPGA integration sketch with estimated per-round latencies is provided.

Main Findings

• Small code, no advantage: For the [[72,12,6]] BB code, DAWG and DAWG+LSD-0 match BP+LSD-0; the authors attribute this to the code being non-degenerate, so most errors are solved by BP alone.
• Order-of-magnitude gain on larger BB codes: For the [[108,8,10]] code, DAWG performs an order of magnitude better than BP+LSD-0, and LSD-0 does not significantly improve the logical error rate — suggesting DAWG can run standalone there.
• Gross code matches RelayBP: For the [[144,12,12]] Gross code, DAWG alone is an order of magnitude better than BP+LSD-0 without a post-processor, and adding LSD-0 reaches a logical error rate matching RelayBP (whose values are taken from prior work on the uncorrelated DEM), without RelayBP's extensive memory-strength optimization.
• Rare post-processor invocation: For the Gross code, LSD-0 runs once per 10 million decoding rounds at p = 0.1%.
• Better convergence than Vibe on BB codes: With the same ensemble size and 20 total serial BP iterations, DAWG leaves up to an order of magnitude fewer unconverged shots per round than Vibe for physical error rates below p = 0.004, with the gap widening near p = 0.001.
• Color codes match Vibe with a smaller ensemble: For superdense color code circuits at distances d = 3, 5, 7, 9, DAWG+LSD-0 reaches the same performance as Vibe+LSD-0, while Vibe used a size-32 ensemble and DAWG used up to 15.
• Color code unconvergence: For d = 9, DAWG shows a fraction of Vibe's unconvergence probability below p = 0.002, meaning LSD-0 is invoked an order of magnitude less often.
• Heavy sparsification: Sparsified models for BB codes contain only 25% of the full DEM's variable nodes; for superdense color codes, only 10%. Example column counts: [[72,12,6]] 2232 → 252; [[108,8,10]] 5508 → 1728; [[144,12,12]] 8784 → 2736; color code d = 3: 385 → 86; d = 5: 2957 → 402; d = 7: 9543 → 1083; d = 9: 21995 → 2273. The number of rows is unchanged.
• Degree reduction: For BB codes, mean/max check degrees drop from 32.8/35 to 7.8/8 and variable degrees from 3.5/6 to 2.7/3; for color codes, check degrees drop from 189.2/270 to 10.1/14 and variable degrees from 4.65/7 to 2.4/3.
• Estimated latency: Worst-case DAWG+OSD-0 latency per extraction round ranges from 981.33 ns (color d = 3) to 6,996 ns ([[144,12,12]]), versus 3,692 ns to 186,400 ns for BP+OSD-0 on the full DEM. Compared with BP+OSD-0 on the full DEM, DAWG reduces worst-case latency by a factor between 7 and 40.
• Versus the 1 μs constraint: For most reported codes the worst case exceeds the 1 μs superconducting latency constraint by at most a factor of 5.15, and no architectural optimizations were performed.

Methodology in Plain English

The decoder works in stages, each invoked only if the previous one fails to converge.

First, a set of BP decoders (the "ensemble") each run on the full detector error model with randomized message-passing schedules, mirroring Vibe decoding. If any converges, the most likely error among converged members is chosen using the model's priors.

Second, if none converged, the posterior log-likelihood ratios from the full model are transferred onto a sparsified version of the model — in this work, a quasi-phenomenological model in which entangling gates are treated as perfect — using a transfer matrix. Because merging several full-model error nodes into one sparsified node means their errors cancel modulo 2, the probability update uses an XOR-style rule, structurally similar to a check-node update in sum-product BP. Each ensemble member uses a different transfer matrix, so different soft information arrives at the small graph. Another round of randomized-schedule serial BP then runs on the sparsified graphs.

Third, if still unconverged, an order-0 localized statistics decoder (LSD-0) post-processes on the sparsified graph, fed the normalized sum of the ensemble's LLR vectors. The authors note that OSD-0 performs equivalently and has deterministic worst-case latency, so they use OSD-0 for latency estimates.

Transfer matrices are found by a guided exhaustive search over restricted column sets sharing non-trivial positions, extended relative to prior work to allow higher-order combinations of sparsified columns, with one solution randomly selected per matrix. Simulations use minimum-sum BP with serial schedules; BB codes are decoded over uncorrelated DEMs of a memory experiment, superdense color codes over correlated DEMs, under standard depolarizing circuit-level noise. BB codes used ensembles of 10, 15, and 20 members (for [[72,12,6]], [[108,8,10]], [[144,12,12]]), each with 20 total iterations split 10 on the full DEM and 10 on the sparsified one. Color codes used ensembles of 5 (d = 3, 5), 10 (d = 7), and 15 (d = 9), also with 20 total iterations split 10/10.

Why This Matters

Decoder latency and hardware footprint are widely cited as bottlenecks for scaling fault-tolerant quantum computers. DAWG shows that BP ensemble accuracy can be retained while pushing the expensive post-processor onto a graph an order of magnitude smaller in variable nodes, and while invoking it far less often. That directly shrinks both the average latency tail and the worst-case latency of decoding.

• Superconducting quantum processors: The paper frames latency against the 1 μs constraint imposed by superconducting technology, and reports worst cases exceeding it by at most a factor of 5.15 before architectural optimization.
• Trapped-ion and neutral-atom systems: Faster, more compact classical decoding widens the set of hardware platforms for which real-time qLDPC decoding is plausible, though the paper's latency analysis is explicitly framed around superconducting constraints.
• Fault-tolerant logical operations: The authors argue DAWG's lack of heavy parameter tuning should transfer to decoding logical operations, whose decoding graphs are typically denser and loopier than memory experiments.
• FPGA/ASIC control electronics: The two-stage design reuses one serial BP architecture, with transfer matrices implemented as multiplexers at check-node unit inputs, rather than requiring two separate decoder cores.

Industry relevance: The paper includes a concrete hardware sketch — reusing the serial BP architecture from prior work, 6 cores on a VCU19P FPGA, estimating 12 cores at 300 MHz, one FPGA for [[72,12,6]] and [[108,8,10]] (the latter with minor optimizations) and two for [[144,12,12]], with OSD-0 post-processing at 250 MHz. This is aimed squarely at the decoder engineering that quantum hardware companies must solve.

Future Directions

• Efficient transfer-matrix search. The restricted exhaustive search will scale poorly if DEMs must be generated in real time; the authors flag architectures that precompute DEMs for certain operations (e.g., LEGO) versus real-time DEM generation, and suggest adapting ideas from surface-code matching decoders.
• Choosing better sparsified models. The quasi-phenomenological choice was motivated by convenience; any matrix sharing the column space of the full DEM is admissible, and other choices might improve accuracy or simplify transfer-matrix computation.
• Decoding logical operations and denser DEMs. Testing on generalized lattice surgery over qLDPC codes and on codes with large dense DEMs such as directional tile codes compiled in 2D lattices.
• Alternative post-processors on the sparsified graph. Filtered OSD-0 for lower latency at some accuracy cost, LSD-0 variants with better average latency, and other post-processors informed by full-DEM BP runs.
• Maximum supported code distance. Since post-processor resources grow quadratically, distance 12 appeared to be the limit for current FPGAs on the full DEM; larger distances are expected to fit with the sparsified graph, an open question.

Target Audience

Researchers and engineers working on quantum error correction and real-time decoding — particularly those designing BP-based decoders for qLDPC codes, benchmarking against RelayBP or Vibe, or mapping decoders onto FPGA/ASIC hardware. It is also relevant to graduate students and postdocs studying bivariate bicycle and color code circuit-level performance, and to hardware architects estimating latency budgets for fault-tolerant control stacks. Readers without background in belief propagation, Tanner graphs, and detector error models will find the algorithmic sections demanding.

Authors’ abstract

Real-time decoding is a fundamental necessity for building fault-tolerant quantum computers. In this work, we introduce decoding with alternating weighted graph sparsification (DAWG), an ensemble based approach that combines Tanner graph sparsification with ensembling belief-propagation (BP) decoders. The DAWG decoder runs BP decoders over the full detector error model Tanner graph for certain iterations to then transfer the posteriors to a sparsified graph in which additional rounds of BP are run. Each of the decoders in the ensemble uses a different transfer matrix to map the posterior information to the sparsified graph. We use the serial schedule for the minimum-sum BP decoders and, thus, employ Vibe decoding ideas by randomizing the schedules of each of them. The performance of the DAWG decoder is then numerically studied for bivariate bicycle codes and superdense color code circuits to be compared with other state-of-the-art decoding approaches. Importantly, the DAWG decoder shows a similar performance to Relay belief-propagation and Vibe decoding when combined with an order-$0$ Localized Statistics Decoding (LSD-$0$) post-processor. Crucially, the post-processor is called an order of magnitude less times than for Vibe with the same ensemble size, indicating that the introduced latency tail will be minimal. Furthermore, LSD-$0$ operates on a sparsified decoding graph of a fraction of the size of the full detector error model, which simplifies the resources required by specialized hardware to support it. Overall, the DAWG+LSD-$0$ decoder represents a viable low-cost BP-based decoding algorithm for quantum error correction codes.