PaperlayerView exact revision on arXiv

Source-linked AI summary

Learned Parallel Bit-Flipping Sequential Belief Propagation Decoding of Quantum LDPC Codes

Mohsen Moradi, Taejoon Kim, Remi A. Chou

arXiv:2610.01068v1quant-phcs.ITmath.IT

TL;DR

QLDPC decoding needs reliable, low-latency methods, while short cycles and degeneracy can hinder BP and a single learned trajectory can be vulnerable to local Pauli decisions. The paper adds scored bit-flip candidates to learned sequential BP and tests them in independent branches; on representative codes, the decoder matches a much deeper RL-S run with substantially smaller decoding depth.

  • Problem

    Short cycles and quantum degeneracy can make standard BP oscillate, stall, or produce logically incorrect estimates, while a single learned sequential trajectory can remain vulnerable to unfavorable local Pauli decisions.

    Source: §I · p. 1

  • Method

    The decoder scores single-qubit quaternary Pauli changes after an initial RL-S stage and tests selected changes through independent RL-S continuation branches.

    Source: §I · p. 2

  • Results

    At decoding depth 200, RL-S-BF matches RL-S with T = 1000 on the [[180, 10, 15 ≤d ≤18]] A5 code and the [[288, 12, 18]] BB code, with more than one order of magnitude improvement over BP and BPGD at p = 0.05 for the BB code.

    Source: §V · p. 5

  • Takeaways & Limitations

    The independent continuation branches provide a parallel, low-latency structure for adding search diversity to learned sequential BP.

    Source: §I · p. 2, §VI · p. 6

Abstract

from arXiv · show

Quantum low-density parity-check (QLDPC) codes are promising candidates for low-overhead fault-tolerant quantum computation, but their practical use requires fast, low-complexity, and reliable decoders. Belief propagation (BP) is attractive because of its local message-passing structure, yet standard flooding BP often suffers from convergence failures on QLDPC codes due to short cycles, degeneracy, and symmetric decoding trajectories. Learned sequential BP improves convergence by using a reinforcement-learning policy to choose variable-node update orders, but a single learned trajectory can still be sensitive to unfavorable local Pauli decisions. We propose a learned parallel bit-flipping sequential BP decoder with a new quaternary score combining syndrome gain, a quantized Pauli log-likelihood penalty, and Q-table lookahead at hypothetical post-flip states. Our decoder first runs learned sequential BP for a fixed number of iterations. If the syndrome is not satisfied, it constructs quaternary bit-flipping candidates, each corresponding to changing the current Pauli decision of one qubit. The selected candidates initialize independent learned sequential BP continuations from the same decoder state. Since these continuations are independent, they can be executed in parallel, so testing several candidates mainly increases parallel hardware resources rather than sequential decoding latency. Simulations on representative QLDPC codes over the depolarizing channel show that the proposed decoder improves the reliability of learned sequential BP while having a parallel low-latency structure.

I. INTRODUCTION

QLDPC decoding benefits from BP’s local message passing, but short cycles and degeneracy can undermine convergence, and a learned sequential trajectory can remain vulnerable to a poor local Pauli decision. The proposed decoder scores single-qubit Pauli changes and tests selected candidates in independent learned sequential BP branches.

I. INTRODUCTION

  • Short cycles weaken BP’s independence assumptions, while quantum degeneracy lets distinct Pauli errors share a syndrome, contributing to oscillation, stalling, or logically incorrect estimates.These are identified as difficulties for applying BP directly to QLDPC codes.Source: §I · p. 1
  • Prior QLDPC BP improvements include post-processing and modified BP dynamics, with controlled asymmetry used through post-processing, decimation, or scheduling.The cited approaches include BP-OSD, stabilizer inactivation, localized statistics decoding, and sequential schedules.Source: §I · p. 1
  • RL-S learns a state-dependent variable-node schedule from a local syndrome-driven representation and guides quaternary BP updates under depolarizing noise.Sequential scheduling reuses fresh messages during an iteration.Source: §I · p. 1
  • The decoder runs RL-S for T0 iterations, then tests selected single-qubit Pauli changes through independent learned sequential BP continuation branches.Branches start from the same decoder state, allowing parallel execution and keeping latency close to testing one candidate.Source: §I · p. 2
  • The quaternary bit-flipping score combines syndrome gain, Pauli-decision reliability, and learned scheduling information.The score also uses Q-table values at hypothetical post-flip states and a soft Pauli likelihood penalty.Source: §I · p. 2
  • On the [[288, 12, 18]] BB code, RL-S-BF at depth 200 matches RL-S at T = 1000 and improves over BP and BPGD by more than one order of magnitude at p = 0.05.The comparison is reported for the depolarizing channel.Source: §I · p. 2

II. BACKGROUND

The background defines stabilizer and CSS QLDPC codes, represents Pauli errors through binary components, and distinguishes matching a measured syndrome from successful decoding.

A. CSS QLDPC Codes and Syndrome Decoding

  • A stabilizer code is the joint +1 eigenspace of an abelian stabilizer subgroup, and an [[n, k, d]] code encodes k logical qubits in n physical qubits with minimum distance d.The subgroup does not contain −I⊗n.Source: A. CSS QLDPC Codes and Syndrome Decoding · p. 2
  • CSS QLDPC codes use sparse binary parity-check matrices HX and HZ that satisfy a commutativity condition.Their rows represent X-type and Z-type stabilizer checks, and sparsity limits the number of checks involving each qubit.Source: A. CSS QLDPC Codes and Syndrome Decoding · p. 2
  • Each Pauli error is represented by binary X and Z components, and the measured CSS syndrome is computed from those components and the parity-check matrices.HX detects the Z-component and HZ detects the X-component.Source: A. CSS QLDPC Codes and Syndrome Decoding · p. 2
  • A zero residual mismatch means the estimate matches the measured syndrome, but decoding succeeds only if the residual error is logically trivial and belongs to the stabilizer group.Syndrome matching alone does not guarantee decoding success.Source: A. CSS QLDPC Codes and Syndrome Decoding · p. 2

B. Depolarizing Channel and Quaternary BP

The depolarizing-channel background motivates quaternary BP because Pauli errors couple the two binary components, so decisions use beliefs over all four Pauli symbols.

B. Depolarizing Channel and Quaternary BP

  • Under the depolarizing channel, quaternary BP represents beliefs over I, X, Y, and Z rather than decoding the binary components independently.The supplied passages identify the possible Pauli symbols but do not specify their probabilities.Source: B. Depolarizing Channel and Quaternary… · pp. 2–3
  • A Y error contains both X- and Z-components, coupling the binary components statistically.Source: B. Depolarizing Channel and Quaternary… · p. 2
  • The quaternary decision uses the joint four-symbol belief because the most likely Pauli symbol generally depends on that joint belief, not on separate binary decisions.The decoder computes a local log-likelihood score for each Pauli symbol from component soft information and the depolarizing prior.Source: B. Depolarizing Channel and Quaternary… · p. 3

C. Learned Sequential BP Scheduling

Learned sequential BP chooses variable-node updates using a Q-table indexed by local syndrome state and node, then refreshes affected residual checks and states after each update.

C. Learned Sequential BP Scheduling

  • Sequential variable-node scheduling updates nodes one at a time and makes each new message available to later updates in the same sweep, unlike flooding BP’s parallel updates.Breaking flooding BP’s synchrony can reduce oscillations on loopy Tanner graphs.Source: C. Learned Sequential BP Scheduling · p. 3
  • The learned policy uses a Q-table indexed by local state and variable node, with local state determined by currently unsatisfied neighboring checks.The scheduler selects among variable nodes not yet visited in the current sweep.Source: C. Learned Sequential BP Scheduling · p. 3
  • After selecting a variable node, the decoder applies the quaternary BP rule, refreshes its hard decision and affected residual checks and local states, then directs computation toward the current residual syndrome.Source: C. Learned Sequential BP Scheduling · p. 3

A. Motivation

A single learned sequential BP trajectory can be sensitive to local Pauli decisions, even when a locally less-likely choice could lead to successful recovery. The decoder addresses this with a one-shot search over candidate Pauli changes and independent continuation paths.

A. Motivation

  • Learned sequential BP follows one trajectory and can be sensitive to local Pauli decisions.Under depolarizing noise, several Pauli symbols may have comparable likelihoods at a qubit.Source: A. Motivation · p. 3
  • Because QLDPC codes are degenerate, a locally less-likely Pauli symbol may still lead to globally successful recovery after further message passing.Source: A. Motivation · p. 3
  • The decoder responds with a one-shot branching search: top candidates each change one qubit's Pauli decision and seed an independent continuation from the same post-initial state.Each branch refreshes affected residual checks and BP messages before running RL-S for Tbr iterations.Source: A. Motivation · p. 3

B. Quaternary Bit-Flipping Candidates

The decoder scores alternative Pauli labels for individual qubits using local syndrome effects, soft reliability, and learned scheduling information. It selects high-scoring candidates for continuation.

B. Quaternary Bit-Flipping Candidates

C. Branch Initialization by a Forced Pauli Change

Each candidate branch begins from a saved common decoder configuration, applies its forced Pauli change, and refreshes affected state before continuation.

C. Branch Initialization by a Forced Pauli Change

  • Before branch evaluation, the decoder saves hard decisions, component estimates, posterior soft information, BP messages, residual mismatches, scheduling states, and mismatch weight.Source: C. Branch Initialization by a Forced… · p. 4
  • Each branch restores that configuration, applies its forced Pauli change, and updates affected residual syndrome values and neighboring VNs' scheduling states.Source: C. Branch Initialization by a Forced… · p. 4
  • Incident messages are refreshed with finite magnitude LBF = 25 in the numerical results, biasing the branch toward its selected Pauli decision without numerical infinities.The branch then runs RL-S for Tbr iterations; if none converges, the decoder returns the branch with the smallest final residual mismatch weight.Source: C. Branch Initialization by a Forced… · p. 4

IV. IMPLEMENTATION AND LATENCY

The implementation shares an initial RL-S stage and generates candidates locally, then runs selected continuation branches in parallel. Increasing parallelism trades hardware resources and memory against latency.

IV. IMPLEMENTATION AND LATENCY

  • Candidate generation evaluates up to three alternative Pauli labels per active VN and costs O(n) using local neighborhoods in bounded- or small-degree Tanner graphs.Source: §IV · p. 4
  • With K parallel lanes, independent branches run simultaneously after the common T0-iteration stage, so increasing K mainly adds parallel hardware resources and memory rather than decoding latency.Source: §IV · p. 4
  • Fully parallel execution replicates branch state across lanes, while time-multiplexing branch hardware reduces parallel resources at the cost of higher latency.The architecture trades search diversity, hardware resources, and latency.Source: §IV · p. 4

V. NUMERICAL RESULTS

Across the A5 and two BB benchmarks, RL-S-BF approaches deeper RL-S performance at substantially smaller decoding depths, while outperforming BP-based baselines in the reported comparisons. The numerical results use block error rate, defined to include logical errors and decoder failures.

V. NUMERICAL RESULTS

  • The decoder runs an initial RL-S stage, scores eligible single-qubit Pauli changes, and tests selected candidates in continuation branches; block error rate counts logical errors or decoder failures.Reported settings include K = 25, β = η = 0.3, Gmin = 1, and LBF = 25; T0 and Tbr vary by figure.Source: §V · pp. 4–5
  • At decoding depth 200, RL-S-BF matches RL-S at T = 1000 on the A5 code and improves block error rate by approximately one order of magnitude over BP, BPGD, and BP-OSD-0.The reported comparison is at p = 0.04; BPGD uses T = 10 per decimation step and decimates up to 180 variable nodes (GT = 1800).Source: §V · p. 5, Figure 1 · p. 5
  • At p = 0.05 on the [[288, 12, 18]] BB code, depth 200 matches RL-S at T = 1000 and improves over BP and BPGD by more than one order of magnitude.Fig. 2 plots the block error rate for the proposed decoder at different maximum decoding depths.Source: §V · p. 5, Figure 2 · p. 5
  • On the [[144, 12, 12]] BB code, depth 20 achieves performance comparable to RL-S with T = 100, BP with T = 1000, and BPGD with GT = 1140.Fig. 3 reports block error rate for this benchmark.Source: §V · p. 5, Figure 3 · p. 6
  • Detailed complexity analysis, hardware-implementation study, and systematic optimization of score-function parameters are left for future work.The paper notes that prior work found sequential BP complexity comparable to BP and substantially lower than BP with post-processing such as BP-OSD.Source: §V · p. 6

VI. CONCLUSION

The conclusion presents RL-S-BF as a learned parallel bit-flipping decoder that adds controlled search diversity to sequential BP while retaining a parallel low-latency structure.

VI. CONCLUSION

  • RL-S-BF first runs RL-S and, when the syndrome remains unsatisfied, forms quaternary candidates by changing one qubit’s Pauli decision.Each candidate is scored using local syndrome gain, soft reliability, and learned scheduling information from the Q-table.Source: §VI · p. 6
  • Selected candidates start independent continuation branches from the same saved decoder configuration, with affected residual checks and BP messages refreshed before further RL-S decoding.Source: §VI · p. 6
  • Because branches can run in parallel, testing more candidates mainly increases parallel hardware resources rather than sequential decoding depth.Source: §VI · p. 6
Loading 2610.01068v1…