PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Fault-Tolerant Decoders for Hypergraph Product and Lifted-Product Codes

Asit Kumar Pradhan, Nithin Raveendran, David Declercq, Bane Vasić

arXiv:2608.31040v1cs.ITquant-ph

TL;DR

The paper tackles high decoding latency in circuit-level QLDPC decoding, where OSD and auxiliary nodes for CNOT-induced correlations increase complexity. It derives message-passing decoders from parent classical LDPC decoders, resolves stabilizer-induced trapping sets, and represents syndrome-type CNOT faults through data and measurement errors. On LP codes, phenomenological-Tanner-graph simulations achieve reduced or comparable logical error rates relative to BP+OSD at substantially lower decoding complexity.

  • Problem

    Circuit-level QLDPC decoding is limited by OSD post-processing and the many auxiliary variable nodes used to represent CNOT-induced correlations and syndrome-extraction faults.

  • Method

    The paper derives QLDPC message-passing decoders from parent classical LDPC decoders to correct stabilizer-induced trapping sets without explicit CNOT-fault nodes.

  • Results

    The proposed decoder achieves 100% success throughout the adversarial-noise table, while phenomenological-graph decoders obtain reduced or comparable logical error rates relative to BP+OSD.

  • Takeaways & Limitations

    Phenomenological Tanner graphs can support effective QLDPC decoding while avoiding the additional complexity of correlated-error nodes and OSD post-processing.

  • Takeaways & Limitations

    The approach depends on parent-code decoders that resolve the corresponding classical trapping sets, and the behavior of inherited trapping-set activation can depend on the syndrome-measurement schedule.

Abstract

from arXiv · show

We design low-complexity, fault-tolerant decoders for quantum low-density parity-check (QLDPC) codes with the goal of reducing decoding latency. We target two major bottlenecks of decoding under the \emph{circuit-level} noise model: (i) post-processing via order-statistics decoding (OSD), and (ii) the large number of auxiliary variable nodes commonly introduced to represent CNOT-induced correlations during syndrome extraction. Our key observation is that propagating CNOT faults (\emph{hook errors}) create \emph{stabilizer-induced} trapping sets (TSs) that are intrinsic to hypergraph-product (HGP) and lifted-product (LP) constructions. Therefore, instead of modeling each such fault with an explicit correlation node and relying on OSD to clean up the resulting failures, we design message-passing decoders that resolve the corresponding \emph{stabilizer-induced} TSs directly. We obtain these decoders by deriving QLDPC decoders from decoders for the parent classical LDPC codes and using them collectively to correct broad families of \emph{stabilizer-induced} TSs. For CNOT faults that manifest primarily as syndrome errors, we show that their effect is equivalent to a data error together with syndrome-bit measurement errors. Consequently, given repeated measurements and a decoding graph that already includes nodes representing syndrome-bit errors, no distinct variable node is needed for each CNOT fault. Using a \emph{phenomenological} Tanner graph with nodes representing only data errors and syndrome-bit errors, simulations on the LP codes show a reduction in, or comparable, logical error rates relative to BP+OSD, at substantially lower decoding complexity.

I. INTRODUCTION

The paper addresses fast, scalable decoding for QLDPC codes by targeting trapping-set failures, OSD complexity, and auxiliary nodes introduced by faulty syndrome extraction. It develops parent-code-based message passing and evaluates phenomenological-graph decoding as a lower-complexity alternative.

  • Motivation: QLDPC codes seek sparse checks, non-vanishing rate, and distance that scales with system size, but efficient scalable decoding remains a major challenge.Fast decoding matters because decoding slower than syndrome extraction can negate quantum-computing advantages.
  • Existing decoding challenges: Classical-style message passing can fail on trapping sets, while OSD post-processing reduces failures at cubic blocklength complexity and exponential complexity in OSD order.For QLDPC codes, dual-containing parent codes make stabilizer-induced trapping sets intrinsic to the construction.
  • Related approaches: Existing alternatives include low-complexity OSD variants, modified message passing, neural decoders, scheduled decoders, and trellis-based decoding, with trade-offs in complexity and performance.The trellis approach has linear blocklength scaling but may have a large constant factor because of its larger state space.
  • Circuit-level noise: Faulty syndrome extraction creates correlated data errors or syndrome-bit errors, and explicit auxiliary nodes for these faults can introduce short cycles and additional trapping sets.For a representative circuit, modeling CNOT faults can require 15 variable nodes per faulty CNOT, producing a 15dc overhead and a factor-90 increase when dc = 6.
  • Approach: The paper connects propagating CNOT faults to stabilizer-induced trapping sets and characterizes broad HGP and LP trapping-set families through trapping sets in parent classical codes.The characterization also quantifies how many CNOT failures suffice to induce these structures and identifies dominant families in the error-floor regime.
  • Approach: The proposed strategy derives QLDPC decoders from parent-code decoders that resolve corresponding classical trapping sets, avoiding explicit CNOT-fault nodes and OSD-style cleanup.CNOT faults appearing as syndrome errors can instead be treated as data errors plus syndrome measurement errors when repeated measurements are available.

F. Quantum LDPC Codes

HGP and LP quantum LDPC codes are constructed from two classical LDPC codes, with product graphs organizing variable and check-node types. Their syndrome-measurement framework uses stabilizer detectors built from controlled gates and ancillas.

  • Classical quasi-cyclic LDPC Codes: LP codes use quasi-cyclic classical LDPC codes represented by base matrices over a quotient polynomial ring isomorphic to binary circulant matrices.The Tanner graph can be constructed by expanding the base matrix or through copy-and-permute operations on the base graph.
  • Lifted-product Codes: The LP construction combines two classical-code base matrices into X- and Z-check matrices satisfying the CSS criterion.The construction defines the numbers of X-checks, Z-checks, and variable nodes from the dimensions of the parent matrices.
  • Lifted-product Codes: The LP product graph contains VV- and CC-type variable nodes together with X- and Z-checks formed from node products in the two parent base graphs.The induced subgraphs associated with X- and Z-check collections correspond to the respective product base matrices.
  • Lifted-product Codes: In Tanner-graph depictions, VV nodes use nested circles, CC nodes nested squares, X-checks circle-inside-square symbols, and Z-checks square-inside-circle symbols.These symbols reflect whether the product node combines parent variable or check nodes.
  • Syndrome Measurement Circuit: A detector tests whether a state lies in a stabilizer generator’s +1 eigenspace, and all detectors together form the syndrome-measurement circuit.For multi-qubit stabilizers, ancilla interactions and subsequent ancilla measurement determine the stabilizer outcome.

H. Detector-Error Matrix

The detector-error matrix records which circuit faults flip detector outputs, enabling circuit-level errors to be represented for decoding. Error propagation through controlled gates determines its entries, including correlated hook errors.

  • Detector-Error Matrix: The detector-error matrix maps circuit fault locations and their possible errors to detector-output changes.Rows represent detectors, columns represent circuit errors, and an entry is 1 when the corresponding error makes a detector output −1.
  • Detector-Error Matrix: CNOT and CZ propagation rules determine detector responses by propagating each isolated fault through the controlled-gate circuit.The detector output is evaluated with only the selected error present, while other circuit faults are absent.
  • Detector-Error Matrix: Ancilla errors can propagate to multiple data qubits, producing correlated hook errors during syndrome extraction.An ancilla X error in the illustrated circuit propagates to q3, q4, and q5 as Z errors.
  • Detector-Error Matrix: For R measurement rounds and r stabilizer generators, the error-detector matrix has rR detector rows.Each stabilizer-generator measurement contributes one detector per round.
  • Detector-Error Matrix: The alternative detector representation preserves effective minimum distance while producing a sparser matrix for iterative decoding.Its repeated-round rows are formed by modulo-two sums of corresponding stabilizer measurements across rounds.

I. Noise Models and Decoders

The paper distinguishes capacity-error, phenomenological, and circuit-level noise models for evaluating decoders. Its primary focus is circuit-level noise, where data, gate, and measurement faults occur together.

  • Noise Models: The capacity-error model applies independent Pauli errors to data qubits while assuming perfect gates and syndrome measurements.Each data qubit receives X, Y, or Z with probability p/3.
  • Noise Models: The phenomenological model combines independent data-qubit Pauli errors with independently flipped measurement outcomes.This model abstracts measurement faults without explicitly modeling the syndrome-extraction circuit.
  • Noise Models: The circuit-level model assigns probability p to CNOT failure, distributes failures uniformly over 15 nontrivial two-qubit Pauli errors, and flips measurements with probability p.Data qubits independently undergo X, Y, or Z errors with probability p/3.
  • Decoders: The decoder estimates the data-qubit error up to the stabilizer group from detector outputs, with failure declared when it cannot do so.The detector outputs are also called the syndrome vector.

III. WHY DOES OSD WORK BETTER ON DETECTOR-ERROR TANNER GRAPHS?

Detector-error Tanner graphs improve BP+OSD by adding variable nodes for syndrome-measurement faults and the correlations they induce. These nodes can reduce logical error rates but substantially increase decoding complexity.

  • Why Detector-Error Tanner Graphs Help: Additional variable nodes represent syndrome-measurement faults and capture correlations induced by the measurement circuit.Their inclusion facilitates BP+OSD convergence and can substantially reduce the logical error rate.
  • Why Detector-Error Tanner Graphs Help: The same auxiliary nodes that improve BP+OSD performance dramatically increase decoding complexity.The section frames the central question as whether explicit fault nodes are essential for low decoding-failure rates.

A. CNOT faults and stabilizer-induced TSs

Hook errors can propagate into correlated data-error patterns that activate stabilizer-induced trapping sets, making BP unlikely to converge. Explicit fault nodes reduce the OSD order needed to resolve these patterns, but can add short cycles and message-passing difficulties.

  • Hook-error mechanism: A single CNOT fault can propagate an ancilla error to data qubits and activate a stabilizer-induced TS.The resulting data-error pattern lies on the TS associated with the measured stabilizer, and BP is unlikely to converge.
  • Hook-error mechanism: The Figure 8 TS is induced by the X-type stabilizer generator c1v2 and includes its neighboring variable nodes.The CNOT ordering determines how the hook error propagates across the relevant data qubits.
  • OSD implications: Adding hook-error variable nodes can reduce the required OSD order from six or higher to order two.Without these nodes, the OSD search order and its exponential complexity increase substantially.
  • Decoder design: Fault-representing nodes help OSD expose correlated hook-error patterns but can worsen BP convergence by introducing additional short cycles.The paper therefore targets BP modifications that resolve the corresponding stabilizer-induced TSs directly.

B. CNOT Faults and Syndrome-Measurement Errors

CNOT faults that do not propagate to other data qubits can instead corrupt the measured syndrome. The section examines whether repeated measurements and existing syndrome-error nodes can handle these faults without separate fault nodes.

  • Syndrome corruption: Non-propagating CNOT faults can corrupt the measured syndrome and are often represented by additional variable nodes.These faults differ from propagating faults because they do not create correlated data errors.
  • Syndrome corruption: A data error introduced midway through stabilizer measurement can be detected only by checks whose gates occur afterward.Consequently, the measured syndrome may differ from the syndrome of the final data-error pattern.
  • Decoder representation: The section asks whether repeated measurements and syndrome-error representations can replace explicit nodes for individual CNOT failures.This question is deferred to a later section.

IV. STABILIZER-INDUCED TSS WITH MULTIPLE COPIES OF TSS FROM A PARENT CODE

HGP/LP codes inherit classical trapping sets, and stabilizer combinations can produce larger structures containing multiple isomorphic copies. These stabilizer-induced trapping sets can be activated by hook errors, motivating decoders derived from parent-code decoders rather than OSD or measurement-schedule optimization.

  • Inherited trapping sets: HGP/LP codes inherit multiple isomorphic copies of classical trapping sets from their parent LDPC codes.Certain collections of these copies form larger stabilizer-induced trapping sets through linear combinations of stabilizer generators.
  • Definitions: A trapping set is an (a, b) subgraph with a variable nodes and b odd-degree check nodes, and its critical number is the smallest initial error count causing iterative-decoder failure.
  • Graph construction: For a degree-four check node in one parent graph, graph products with a parent-code trapping set produce four identical copies of that trapping set.The copies do not share vertices or edges, and the resulting structure is induced by associated stabilizer generators.
  • Decoder implication: A stabilizer-induced trapping set is active when at least ⌈|N_c1|/2⌉ copies are active; below this threshold, parent-derived decoders can resolve it without modification.At or above the threshold, the derived decoder may fail and additional measures are needed.
  • Hook-error activation: Hook errors during measurement of the inducing stabilizers can corrupt all variable nodes in ℓ isomorphic copies of the parent trapping set.The erroneous variable-node set is the union of the corresponding copies contained in the stabilizer-induced structure.
  • Decoder implication: The proposed parent-code-derived message-passing approach resolves these trapping sets without OSD and without optimizing the measurement schedule.The paper therefore designs decoders to handle inherited trapping sets when they appear in T_stab.

A. Deriving QLDPC Decoders from Parent Code Decoders

The decoder derives QLDPC message-passing components from parent classical decoders and alternates them across VV- and CC-type subgraphs. Preprocessing makes selected stabilizer-induced trapping sets syndrome-compatible with errors on one variable-node type, enabling correction without starting from an entirely new decoder.

  • Decoder construction: Parent-code decoders act independently on disjoint embedded Tanner-graph copies covering the VV-type variables, defining the decoder Dvv.An analogous construction from the other parent code defines Dcc on CC-type variables.
  • Decoder construction: The full QLDPC decoder alternates Dvv and Dcc until the estimated syndrome matches the measured syndrome.Each component takes a syndrome vector as input and outputs an error estimate on its corresponding variable-node type.
  • Trapping-set correction: Preprocessing enforces separation between erroneous VV- and CC-type supports, allowing a syndrome-compatible representative supported only on VV-type variables in the targeted trapping set.The amended preprocessing steps toggle CC-type variables when needed to remove unsatisfied checks from selected subgraphs.
  • Trapping-set correction: Under the stated degree and tree hypotheses, the derived decoders correct stabilizer-induced trapping sets containing multiple copies of a parent classical trapping set.The guarantee assumes that the parent decoder already resolves the underlying classical trapping set.
  • Circuit-level relevance: Large stabilizer-induced trapping sets can be activated by a small number of CNOT failures despite involving many variable nodes.This motivates correcting their structure directly rather than relying solely on generic post-processing.

V. TSS IN HGP AND LP CODES FROM TSS OF TWO PARENT LDPC CODES

Composite trapping sets combine structures inherited from both parent LDPC codes, and shared checks can make their syndromes nonseparable. The paper characterizes these structures and bounds the circuit faults needed to induce them, supporting targeted decoder design.

  • Composite trapping sets: Composite trapping sets can combine trapping-set structures from both parent codes and defeat decoders that succeed on each component separately.Shared checks jointly determine syndrome bits, so the composite syndrome may not decompose into the two parent syndromes.
  • Fault counting: Under the construction’s separation assumptions, no variable in the composite trapping set lies in the support of more than one relevant CV-type check.Consequently, a measurement error on those checks does not propagate to more than one composite-trapping-set variable.
  • Composite trapping sets: When parent trapping sets share a check node, their unsatisfied-check patterns can change or cancel after combination.This altered syndrome prevents a guarantee that independently inherited parent decoders will decode the composite structure.
  • Structural characterization: The composite structure is characterized as a subgraph induced by an explicit set of CV-type checks, equivalently X-type stabilizer generators.This induced-subgraph description supports schedule-dependent counting of the CNOT faults needed to create it.
  • Decoder design procedure: The proposed design procedure enumerates low-critical-number parent trapping sets, identifies families inducible with few faults, designs targeted decoders, and verifies them by adversarial injection.Configurations requiring substantially more faults or negligible error weights are excluded from treatment in the operating regime.

VI. HANDLING CNOT-FAILURE-INDUCED SYNDROME ERRORS WITHOUT ADDITIONAL NODES

CNOT faults that corrupt syndrome measurements can be represented as data errors plus syndrome-bit errors in a phenomenological Tanner graph. This avoids distinct CNOT-fault nodes while retaining the relevant measurement-error structure across repeated rounds.

  • Equivalent error model: A CNOT failure that manifests as a syndrome error can often be reinterpreted as a data error plus one or more syndrome-bit errors.For the example, a Z error introduced on d7 during measurement matches a pre-existing Z error on d7 together with a syndrome-bit error on a2.
  • Graph representation: The phenomenological Tanner graph uses repeated timeslice copies and nodes for data-qubit errors, stabilizer generators, and syndrome errors.This representation captures the measurement history without assigning a separate variable node to each CNOT fault.
  • Trade-offs: Avoiding explicit CNOT-fault nodes may require more measurement rounds or increased spatial redundancy.Keeping such nodes can introduce additional short cycles, including 4-cycles, that may degrade iterative decoding and increase complexity when post-processing is used.
  • Decoding procedure: Multiple error patterns can produce the same measured syndrome in the phenomenological graph, potentially preventing direct message-passing convergence.The decoder mitigates this by iterating on one timeslice for a fixed number of iterations, then switching timeslices while carrying over its state.

VII. SIMULATION RESULTS

The simulations validate the proposed decoder principles on two lifted-product codes, including adversarial trapping-set tests and stochastic-noise comparisons.

  • Adversarial and stochastic simulations evaluate two LP codes, including [[1054, 140, d ≤20]] and [[775, 43, d ≤20]].
  • Both classical codes are taken to be identical in the simulation notation, so superscripts distinguishing their Tanner-graph nodes are omitted.

A. Adversarial noise model

Under adversarial trapping-set patterns, the proposed alternating and structured decoders resolve failures that remain for BP+OSD, while avoiding explicit fault nodes and post-processing.

  • Min-sum + OSD-CS (10) leaves approximately two fifths of single-generator patterns and roughly one quarter of three-generator patterns uncorrected on the [[1054, 140, d ≤20]] code.
  • The alternating VV/CC min-sum schedule corrects all tested patterns on both codes, typically within two iterations and without post-processing.
  • Explicit hook-error nodes correct every tested pattern but increase variable-node counts, check degrees, and the complexity of message passing and OSD.
  • The experiments compare the proposed decoder and beam search against detector-error-graph and code-level baselines, with the proposed method requiring neither detector-error decoding nor post-processing.
  • 100% success is achieved throughout Table I by the proposed decoder on the tested stabilizer-induced trapping-set families.
  • For combined trapping sets, the derived decoders can remain effective when parent-code decoders tolerate a single erroneous syndrome bit; min-sum is empirically robust for the transpose-code families tested.
  • With one quarter of associated syndrome bits flipped, the decoder still converges to the correct estimate in the tested adversarial settings.

B. Stochastic noise model

Under circuit-level depolarizing noise, layered decoders on the phenomenological Tanner graph achieve comparable logical error rates with substantially lower per-iteration complexity, while remaining subject to design trade-offs.

  • The stochastic simulations use three syndrome-measurement rounds, a perfect final round, and detector-error sampling under circuit-level depolarizing noise.
  • The layered min-sum schedule updates syndrome-bit, CC-type, and VV-type variables across odd and even embedded copies, alternating updates to mitigate trapping-set failures.
  • Schedule 1 applies a VV-side FAID stage after min-sum, whereas Schedule 2 performs deeper layered min-sum sub-iterations without specialized parent-code FAIDs.
  • The FAID library lacks a single FAID correcting all patterns on a (7, 3) trapping set, and TS-focused FAIDs can fail or diverge when neighboring errors are present.
  • The FAID-assisted layered decoder achieves a comparable logical error rate to BP+OSD and beam search with substantially lower per-iteration decoding complexity.
  • Which decoder best suits a hardware platform remains unresolved, including whether beam search meets latency constraints and retains comparable performance with finite precision.

VIII. CONCLUSION

The work presents decoder-design guidelines for phenomenological Tanner graphs that avoid correlated-error nodes, while identifying further opportunities to improve logical error rates and extend the setting.

  • Phenomenological Tanner graphs avoid the additional decoding complexity introduced by nodes representing correlated errors.
  • The layered proposed decoders have better logical error rates than BP+OSD, with further improvement possible by optimizing parent-code decoders for larger trapping sets.
  • The design approaches remain to be extended from quantum memory to quantum computing.

APPENDIX A STABILIZER-INDUCED TS IN G T

The appendix characterizes stabilizer-induced trapping-set structure in HGP-related Tanner graphs and describes decoder components used to address such failures.

  • Tstab contains |Nv2| pairwise isomorphic copies of T(C1s), one for each c2j.
  • These copies are pairwise disjoint, and their nodes correspond to specific CC-type variables and VC-type checks.
  • The resulting stabilizer support contains all CC-type variable nodes and selected VV-type variable nodes, linking the trapping-set structure to stabilizer combinations.
  • A suitable measurement schedule allows one CNOT failure per stabilizer generator to corrupt all variable nodes in selected isomorphic copies.
  • The decoder framework uses FAID and min-sum message rules, with message updates determined by check-node syndromes, extrinsic variable-node messages, quantization thresholds, and variable-node type.
Loading 2608.31040v1…