PaperlayerView exact revision on arXiv

Source-linked AI summary

Certified decoding of quantum LDPC codes

Ragavi Krishnamoorthy, Florian Gerhardt, Johannes Knaute, Thomas Klir, Stefan Raimund Maschek, Erik Schulze, Tomislav Maras, Alexander Dotterweich, Loong Kuan Lee, Christian Bauckhage, Nico Piatkowski

arXiv:2608.25545v1quant-phcs.IT

TL;DR

Degenerate qLDPC decoding requires comparing partition functions over equivalent errors, beyond the guarantees of heuristic BP+OSD. This paper reframes decoding as probabilistic inference and develops sampling and region-based decoders with certificates, showing broad validation across code families and noise models.

  • Problem

    Degeneracy makes qLDPC maximum-likelihood decoding a coset partition-function problem, while BP+OSD uses heuristic post-processing without optimality guarantees.

  • Method

    The paper represents each logical class as a partition function of an unconstrained positive Markov random field and applies probabilistic-inference estimators and region-based approximations.

  • Results

    Experiments validate the decoders against exact degenerate ML, BP+OSD, and MWPM across surface, bivariate-bicycle, spacetime, and circuit-level decoding problems.

  • Takeaways & Limitations

    The partition-function formulation makes established probabilistic-inference machinery applicable to degenerate decoding across code families and faulty-measurement settings.

  • Takeaways & Limitations

    At induced width ≈40, MBE(20) upper bounds are too loose to rank classes reliably and perform worse than BP+OSD.

Abstract

from arXiv · show

Quantum low-density parity-check (qLDPC) codes reduce the qubit overhead of fault-tolerant quantum computation by an order of magnitude, but their decoding is harder than its classical counterpart: because many physical errors are equivalent up to stabilizers, the degenerate maximum-likelihood (ML) decoder must compare the probabilities of entire equivalence classes of errors, that is, partition functions, rather than single errors. The workhorse decoder BP+OSD sidesteps degeneracy heuristically and offers no guarantees. We treat degenerate decoding as probabilistic inference in an undirected graphical model: the probability of each logical class is the partition function of an unconstrained, strictly positive Markov random field over the code's check variables, a construction that generalizes the random-bond Ising mapping of the surface code to arbitrary CSS codes and to spacetime decoding with measurement errors and circuit-level noise. On this model we build two decoders. The first estimates all class partition functions by annealed importance sampling with common random numbers and attaches to every decision a certificate of optimality: a paired bootstrap test, or, composed with constant-factor estimators such as WISH, an exact optimality proof. The second is region-based: the Bethe free energy, whose bias cancels between classes, reproduces exact ML decoding on every tested surface-code instance at millisecond cost, and enlarging the regions to elimination clusters makes exact degenerate ML decoding of the [[72,12,6]] bivariate bicycle code feasible. Across surface codes and the bivariate bicycle codes [[72,12,6]] and [[144,12,12]], under code-capacity, phenomenological, and circuit-level noise, the sampling decoder matches or exceeds BP+OSD while certifying the bulk of its decisions, and the certificate flags exactly the syndromes on which any fast decoder should be distrusted.

1 Introduction

The paper recasts degenerate qLDPC decoding as partition-function inference in a code-derived graphical model, enabling certified sampling and region-based decoders. These methods apply from arbitrary CSS codes through circuit-level noise and are validated against exact ML decoding and established baselines.

  • Motivation: Quantum degeneracy makes optimal decoding a comparison of exponentially large error-equivalence-class probabilities, whereas BP+OSD handles this structure heuristically.Errors differing by stabilizers act identically on the code space, so maximum-likelihood decoding must sum over configurations rather than select a single most probable error.
  • Coset MRF: Each logical class becomes the partition function of an unconstrained, strictly positive MRF over code check variables, generalizing the surface-code Ising mapping [2] to arbitrary CSS codes and spacetime decoding.For bivariate bicycle codes, the construction yields a three-body analogue and extends to faulty measurements.
  • Certified sampling decoder: AIS with common random numbers estimates all class partition functions jointly, while paired bootstrap tests certify decisions and WISH [12] can provide exact optimality proofs.WISH uses QUBO optimization oracles, making the constant-factor estimator compatible with quantum annealers [15].
  • Region-based decoders: Bethe free-energy bias cancels between classes, reproducing exact ML decisions on every tested surface-code instance at millisecond cost; larger elimination regions enable exact decoding of [[72,12,6]].The region-based hierarchy progresses from loopy-belief-propagation Bethe estimates to Kikuchi-size regions implemented by mini-bucket elimination.
  • Validation: The evaluation spans rotated surface codes, bivariate bicycle codes [[72,12,6]] and [[144,12,12]] [8], and phenomenological and circuit-level spacetime noise against exact ML, BP+OSD, and MWPM [17].Reported measures include logical error rates, certified fractions, certificate calibration against ground truth, and runtime.
  • Scope: Unlike surface-code-specific methods [18], the construction requires only sparsity rather than geometric structure, so its guarantees come from the estimator rather than the code family.This supports application to expander-like codes central to current fault-tolerance road maps.

2 Classical LDPC Codes

Classical LDPC codes use sparse parity checks with bounded-degree Tanner graphs, enabling cheap, parallelizable decoding and strong asymptotic performance. The qLDPC program asks whether these benefits can coexist in quantum codes, where the answer is less obvious.

  • Classical LDPC codes: LDPC codes have sparse parity-check matrices, with every row and column containing at most a constant number of ones independent of code length.Equivalently, their Tanner graphs have bit and check nodes with bounded degree.
  • Classical LDPC codes: Gallager introduced LDPC codes in 1962, and their 1990s rediscovery established iterative belief-propagation decoding near the Shannon limit.Sparsity also makes decoding iterations cheap and massively parallelizable, supporting adoption in standards including 5G-NR and IEEE 802.11.
  • Classical LDPC codes: The qLDPC program asks whether sparse checks and good asymptotic parameters can coexist in quantum codes, where their coexistence is substantially less obvious.

3 Undirected Probabilistic Graphical Models

This section formulates decoding as inference in undirected probabilistic graphical models, where distributions factorize over clique potentials and are normalized by a partition function. Quantum degeneracy changes decoding from MAP estimation of individual errors to evaluating constrained partition functions over stabilizer equivalence classes.

  • An MRF factorizes a distribution over variables into nonnegative clique potentials, whose sum over configurations defines the normalizing partition function.Writing clique potentials as ψ_C = exp(θ_C) gives the log-domain representation.
  • The canonical inference tasks are marginal inference, MAP inference, and partition-function evaluation, all computationally hard in general.Computing Z is #P-hard, and even approximate marginal inference is intractable in the worst case.
  • Belief propagation computes marginals exactly on trees but only approximately on loopy factor graphs, where fixed points correspond to stationary points of the Bethe free energy.Replacing summation with maximization yields max-product BP for approximate MAP inference.
  • Classical syndrome decoding is an MRF inference problem on the code’s Tanner graph, with bitwise MAP decoding as marginal inference and blockwise MAP decoding as MAP inference.LDPC sparsity makes each belief-propagation iteration cheap.
  • Quantum degenerate maximum-likelihood decoding maximizes posterior mass over stabilizer cosets, requiring constrained partition-function evaluation rather than selection of the single most probable error.For the surface code, the coset sum is the partition function of a random-bond Ising model.

4 Stabilizer Codes and the CSS Construction

Stabilizer codes protect encoded quantum states by extracting syndromes from commuting Pauli checks, while CSS codes separate X- and Z-error detection into classical problems. qLDPC sparsity supports fault-tolerant syndrome extraction, but degeneracy and stringent commutation constraints make useful constructions difficult.

  • Stabilizer formalism: Stabilizer codes define the code space as the joint +1 eigenspace of an abelian Pauli group, with generator measurements revealing error information without destroying the logical state.An [[n, k, d]] code encodes k logical qubits into n physical qubits.
  • CSS construction: CSS codes combine two classical codes whose parity-check matrices satisfy an orthogonality condition, ensuring that X- and Z-type stabilizers commute.
  • CSS construction: CSS decoding separates phase-flip and bit-flip detection into two classical problems, but degeneracy makes many distinct physical errors equivalent up to stabilizers [32, 33].Classical decoders are not designed to exploit these equivalence classes.
  • Construction challenges: The CSS commutation constraint makes good quantum codes difficult to construct: random sparse matrices rarely satisfy it, while structured constructions often sacrifice rate or distance.

5 From the Surface Code to Quantum LDPC Codes

The surface code offers local connectivity, a near-1% circuit-level threshold, and efficient decoding, but its vanishing rate makes large computations qubit-intensive. Quantum LDPC constructions trade geometric locality for sparse expansion, culminating in bivariate bicycle codes that reduce practical qubit overhead while retaining promising thresholds.

  • The surface code is a geometrically local CSS qLDPC code with weight-four stabilizers, a near-1% circuit-level threshold, and efficient minimum-weight perfect matching decoding [2] [3].Its locality makes it attractive for planar superconducting chips.
  • A distance-d surface-code patch uses n = Θ(d2) physical qubits for k = 1 logical qubit, requiring roughly 103 physical qubits per logical qubit at d ≈ 25–35 before magic-state distillation.
  • Two-dimensional locality imposes this poor scaling: any 2D-local stabilizer code obeys the Bravyi–Poulin–Terhal bound, making the surface code essentially optimal within its locality class.Improved parameters therefore require long-range connectivity.
  • Lifted products and quantum Tanner codes achieve asymptotically good qLDPC families by replacing geometric locality with sparse, highly connected expansion [6] [7].Earlier hypergraph-product codes achieved constant rate with d = Θ(√n), while the newer constructions reach k = Θ(n) and d = Θ(n).
  • The [[144, 12, 12]] bivariate bicycle code encodes 12 logical qubits at distance 12, and at physical error rate 10−3 can match performance requiring roughly ten times as many surface-code qubits [8].Circuit-level simulations report a pseudo-threshold near 0.7%; the code uses 144 data qubits plus 144 syndrome-extraction ancillas.

6 The Decoding Bottleneck

Deploying qLDPC codes has three obstacles, but this section focuses on decoding. Decoding is harder than for classical LDPC codes or the surface code because quantum Tanner graphs contain unavoidable short cycles and error degeneracy.

  • The Decoding Bottleneck: Decoding is identified as the third obstacle to deploying qLDPC codes and is the subject of the paper’s subsequent analysis.The other obstacles are engineering the long-range connectivity required by (6) and developing fault-tolerant logical gates for densely packed code blocks.
  • The Decoding Bottleneck: Plain BP fails on quantum Tanner graphs because CSS constructions contain unavoidable four-cycles and error degeneracy.These effects distinguish qLDPC decoding from decoding classical LDPC codes or the surface code.
  • The Decoding Bottleneck: Error degeneracy splits posterior probability mass across many equivalent errors, preventing BP from converging to any single one.The syndrome-conditioned posterior therefore has many symmetric modes, so its sum-product marginals do not resolve one error representative.

7 Degenerate ML Decoding as Partition-Function Estimation

The section reformulates degenerate quantum ML decoding as comparing partition functions of positive, unconstrained coset MRFs. It then develops certified sampling estimators and region-based free-energy methods, including exact decoding through enlarged elimination clusters.

  • Coset partition functions: Degenerate ML decoding compares the probabilities of 2^k logical cosets, and any representative from the highest-probability class is an optimal correction.Each class is a syndrome-solution coset e_λ ⊕ rowspace(H_X); redundant-check multiplicities cancel across class comparisons.
  • Coset partition functions: Each coset probability is exactly the partition function of a strictly positive, unconstrained MRF whose variables are X-checks and whose factors are qubits.The factor graph is the transpose of the H_X Tanner graph, with clique size equal to qubit check-degree; surface codes recover the random-bond Ising model of [2].
  • Certified sampling: The sampling decoder uses shared randomness across classes and bootstrap comparisons to attach per-decision certificates, while WISH supplies factor-16 relative guarantees for exact optimality proofs.The bootstrap certifies the large majority of decisions on the gross code at identical sampling cost, whereas the t-test certifies almost nothing.
  • Region-based decoding: Bethe free-energy biases largely cancel between coset MRFs because classes share graph structure and couplings, making class ratios on surface codes track exact ratios to ≈0.1 nats.At strong coupling, BP can reach a class-independent paramagnetic fixed point; polarized initialization selects the ordered branch, while convergence depends on noise rate.
  • Region-based decoding: Enlarging regions through the Kikuchi/cluster-variation hierarchy makes exact ML decoding of the [[72, 12, 6]] code feasible, reducing it to seconds per syndrome and enabling optimization over all 2^12 classes.The construction also extends beyond code-capacity CSS decoding to phenomenological and circuit-level detector error models; spacetime instances require an annealing base near q_0 ≈ 0.02.

8 Experiments

Across simulated noise models, AIS decoding matches or outperforms BP+OSD while certifying most decisions, and region methods enable exact degenerate ML on tractable qLDPC instances. Hardware pilots show the certified pipeline runs end-to-end, but model mismatch—not decoding—limits suppression.

  • Surface codes: On surface codes, AIS is statistically indistinguishable from exact degenerate ML, differing on at most 0.3% of decisions at higher p, while certificates reach 100% in the reported regime.AIS log-partition error falls from 0.82 to 0.068 nats as T increases from 4 to 64, and common random numbers reduce ratio-error variance by 1.2–2.2×.
  • Bivariate bicycle codes: For qLDPC code-capacity noise, AIS is never worse than BP+OSD-0, repairs eight versus three decisions on [[72, 12, 6]], and reaches BP+OSD-CS-7 at p ∈{0.02, 0.05}.With exact references, BP+OSD is provably suboptimal on 2 of 120 [[72, 12, 6]] syndromes at p = 0.03, where its rate is 0.0500 versus 0.0417 for exact ML.
  • Failure modes: Under-resolved partition-function estimates can damage baseline decisions, whereas loose MBE bounds break 49 of 60 gross-code decisions without certificates.At T = K = 128, the sweep ablation eliminates the imbalance but costs 13–30 s per decode; the gross-code MBE(20) run costs 272 s.
  • Circuit-level noise: At circuit level, AIS matches or beats both baselines at every rate, certifies 99%–100% of decisions, and improves over BP+OSD-0 at p = 0.004 (0.0133 versus 0.0183).On 720 spacetime syndromes, AIS never disagrees with BP+OSD-0 and certifies 100% of decisions, at 52 s per decode.
  • Region-based decoding: MBE(16) and MBE(20) reproduce exact decisions on 40/40 syndromes, while exact mini-bucket decoding costs 5–26 s per syndrome.The full optimum over 212 classes lies within the two-logical candidate set on all tested syndromes.
  • Hardware experiments: On IBM hardware, detector rates exceed model predictions threefold (0.229 versus 0.076), so decoding barely improves raw logical flips (0.253 to 0.246); AIS nevertheless certifies 96% of decisions.The [[72, 12, 6]] experiment establishes end-to-end certified decoding on real qLDPC syndrome data, with hardware connectivity remaining the binding constraint.

9 Discussion and Outlook

The discussion frames degenerate maximum-likelihood decoding as exact partition-function estimation over strictly positive Markov random fields, with certificate strength arising from the test statistic rather than a shorter annealing path. Although the sampling decoder is too slow for real-time hardware, it can provide certified reference decisions and support second-stage triage.

  • Proposition 1 exactly reduces each logical class of a CSS code to the partition function of an unconstrained, strictly positive Markov random field over check variables.
  • The anneal through infinite temperature is the appropriate bridge, while certificate strength comes from the test statistic rather than a shorter path.
  • Sampling takes seconds per decode versus the microsecond real-time loop of superconducting hardware, limiting its direct deployment speed.
  • Certified ML decisions can serve as a reference decoder for benchmarking fast qLDPC heuristics and as a second-stage triage decoder.The reference-decoder role has so far been playable only on the surface code, and the Bethe and BP+OSD comparisons already use it this way.
Loading 2608.25545v1…