CS Paper Radar

Temporal Degeneracy Limits Message Passing Decoding of QLDPC Codes Under Repeated Noisy Syndrome Measurements

Dimitris Chytas, Nithin Raveendran, Bane Vasić

cs.IT quant-ph ·submitted 2026-10-22 20:12 UTC · v1

Abstract

Practical quantum computations can require logical error rates of $10^{-12}$ or lower. Quantum low-density parity-check (QLDPC) codes are promising candidates for reaching such rates with low qubit overhead, provided that their syndromes can be decoded efficiently. Repeated noisy syndrome measurements introduce temporal degeneracy into the space-time decoding graph. We characterize the temporal kernel, whose vectors have zero total data parity, and show that it is generated by elementary temporal codewords of weight $d_v+2$, where $d_v$ is the variable-node degree. For $(d_v,d_c)$-regular parity-check matrices with fixed degrees $d_v,d_c>2$ and girth greater than four, we derive counting bounds and construct degenerate error patterns of weight $(d_v+2)/2$ for even $d_v$ and $d_v+1$ for odd $d_v$, with multiplicity $Θ(nr)$ in the blocklength $n$ and number of measurement rounds $r$. Under the isolation assumption, these patterns cause local failures of deterministic isotropic message-passing decoders under a flooding schedule. These failures depend on the node degrees rather than the minimum distance; for the bivariate bicycle (BB) codes considered, their weight is equal to four. Monte carlo simulations and fixed-weight importance sampling quantify harmful low-weight degenerate error patterns for the min-sum (MS) decoder beyond the isolation assumption. Motivated by the identified symmetries, we propose space-time anisotropic min-sum decoding with syndrome-guided realizations. Its complexity is linear in the number of Tanner graph edges for fixed maximum number of iterations and number of decoders. Numerical results on BB codes show threshold-like behavior acrossthe tested code sizes and improved failure probabilities relative to MS decoding with ordered statistics decoding post-processing.

Closest papers

Nearest neighbours by meaning across the whole index.

Achievability of CSS codes performance limits over Pauli channels under separate ML decoding with bounded graphical complexity

cs.IT quant-ph ·2026-11-02 ·Gulnihal Mercanoglu, Achilleas Anastasopoulos, S. Sandeep Pradhan
similarity 0.70
Abstract · 45 pages, 9 figures

Capacity-approaching quantum error correction faces a fundamental tension: the required parity-check matrices need to become increasingly dense, while practical decoding and syndrome extraction favor sparse, bounded-degree structures. Reconciling these competing requirements remains an important open problem in quantum code design. We construct Calderbank-Shor-Steane (CSS) code ensembles that approach the CSS rate over memoryless Pauli channels under maximum-likelihood decoding while retaining sparse, bounded-degree graphical representations. The construction separates parity-check density from graphical complexity: although capacity-approaching components may require dense parity-check matrices, they are represented by sparse concatenated factor graphs. We first study a construction combining low-density parity-check (LDPC) and low-density generator-matrix (LDGM) component codes and numerically analyze the average weight distributions of the resulting codes. Motivated by these results, we introduce a second construction based on concatenated LDPC and LDGM codes and generalized irregular repeat-accumulate (GIRA) codes. We derive bounds on the average weight distribution of the resulting sum ensemble and use the Miller-Burshtein framework to prove simultaneous reliability of the two CSS decoding components. Consequently, the proposed ensemble achieves rates arbitrarily close to the CSS hashing bound under separate bit- and phase-error correction, while maintaining bounded graphical complexity, thus providing a foundation for future iterative decoders and indirect syndrome-extraction architectures.

0.20

High-Rate Quasi-Dyadic Quantum LDPC Codes

cs.IT ·2026-09-21 ·Alessio Baldelli, Sisi Miao, Laurent Schmalen, Massimo Battaglioni, Marco Baldi
similarity 0.70
Abstract

In this work, we propose a novel design of high-rate Calderbank--Shor--Steane (CSS) quantum low-density parity-check (QLDPC) codes based on quasi-dyadic matrices. The Tanner graphs associated with the two component classical codes used to construct the proposed CSS codes are characterized by a girth of at least $6$. We also derive an exact count of length-$4$ cycles in the quaternary representation of the parity-check matrix. Monte Carlo simulations under code-capacity and phenomenological noise models show that the proposed codes have competitive finite-length logical error rate performance compared with state-of-the-art codes in both these settings.

0.05

Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time

cs.IT quant-ph ·2026-09-30 ·William Gay, Fernando Granha Jeronimo, Abhi Shukul
top venue similarity 0.69
Abstract · SODA 2027, to Appear

In classical coding theory, the quest for explicit codes achieving list decoding capacity has been an important driving force. While random codes are easily shown to achieve capacity, an explicit construction was only discovered decades later in the seminal work [Guruswami and Rudra, STOC 2006]. In quantum coding theory, it is highly desirable that a code family be LDPC. While good quantum codes were known for decades, obtaining the additional LDPC property was elusive. In fact, only very recently that good quantum LDPC codes were discovered in a breakthrough work [Panteleev and Kalachev, STOC 2022]. In this context, a natural question is to ask for an explicit family of quantum codes achieving list decoding capacity while also possessing the important LDPC property. In this work, we provide (to the best of our knowledge) the first explicit constructions of quantum LDPC codes achieving list decoding capacity, namely, with a list decoding radius approaching the quantum Singleton bound with constant list sizes. Furthermore, we provide near-linear time (in the block-length) list decoding algorithms approaching capacity. Our explicit code construction are based on expander graphs via the quantum analogue of Alon-Edmonds-Luby (AEL) amplification [Bergamaschi, Golowich and Gunn, STOC 2024], and this enables the important LDPC property. Our efficient list decoding algorithms are obtained by generalizing the classical expander-based weak-regularity list decoding algorithms [Srivastava and Tulsiani, FOCS 2025] [Jeronimo and Singh, 2025] to suitable instantiations of quantum AEL.

0.58

Quantum LDPC and High-Rate CSS Codes from Fair-Density Parity-Check Codes

cs.IT ·2026-09-01 ·Hessam Mahdavifar
similarity 0.69
Abstract

We construct quantum LDPC (qLDPC) and high-rate CSS codes from our recently introduced classical fair-density parity-check (FDPC) codes. To this end, we introduce a structured sparsification of FDPC parity-check matrices, which reduces their check weights while preserving the underlying combinatorial structure and distance guarantees. Combined with the hypergraph-product construction, this yields finite-length qLDPC codes with analytically controlled blocklength, dimension, certified distance, and stabilizer weight. For quantum blocklengths $N<10^5$, the constructions introduced here span guaranteed rates from approximately $0.35\%$ to $25.8\%$ and certified quantum distances from $12$ to $69$, with stabilizer weights between $8$ and $16$. In the large-blocklength regime, allowing the FDPC order and sparsified check weight to scale moderately with blocklength yields a family of high-rate CSS codes, which we refer to as quantum FDPC (qFDPC) codes, with rate $R_Q$ and minimum distance $D$ satisfying \[ R_Q = 1-O\left(\frac{1}{\log\log N}\right), \ \ D=Ω(N^{1/4}), \] and stabilizer weight $O(\log N\log\log N)$. Finally, the analytically available FDPC weight distribution provides explicit information about the logical operators of the resulting hypergraph-product codes. Over the quantum erasure channel, this structure yields rigorous first-order maximum likelihood (ML) expressions and a higher-order weight-distribution approximation to the ML logical block error probability. This enables estimation of finite-length operating points and the onset of the error-floor regime. To the best of our knowledge, beyond surface-code-type constructions, this is the first finite-rate qLDPC framework to provide both finite-length certified minimum-distance information and an analytical characterization of low-weight logical multiplicities.

0.08

Certified decoding of quantum LDPC codes

cs.IT quant-ph ·2026-08-26 ·Ragavi Krishnamoorthy, Florian Gerhardt, Johannes Knaute, Thomas Klir, Stefan Raimund Maschek +6 more
similarity 0.68
Abstract

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.

0.29

Quantum Message Passing Convergence and Vanishing Block-Error Probability for Random LDPC Codes

cs.IT quant-ph ·2026-09-05 ·Avijit Mandal, Christophe Piveteau, Joseph M. Renes, Henry D. Pfister
highly cited similarity 0.67
Abstract

Belief propagation with quantum messages (BPQM) is a quantum algorithm that decodes classical codes transmitted over classical--quantum channels. It realizes optimal decoding on tree factor graphs over pure-state classical-quantum channels. However, this tree-based analysis does not ensure vanishing block-error probability for LDPC Tanner graphs with cycles. In this work, we construct a two-stage BPQM decoder for random $q$-ary LDPC codes over symmetric $q$-ary pure-state channels, where $q$ is prime, and prove that its ensemble-average block-error probability vanishes as the blocklength $N$ tends to infinity. For regular ensembles with $d_v\geq3$, fidelity bounds yield double-exponential decay of the average symbol-error probability throughout the BPQM success region. We apply depth-$\ell$ BPQM to coordinates with tree neighbourhoods and treat the remaining coordinates as erasures. With a suitable $\ell=Θ(\log\log N)$, a noncommutative union bound controls the BPQM decoding errors, while the minimum-distance property guarantees erasure recovery. We also extend the analysis to finite-support irregular ensembles. These results are relevant to quantum algorithms based on Regev's reduction, where coherent decoding uncomputes a codeword register. Decoded quantum interferometry (DQI) uses a closely related Fourier-based framework that reduces sparse max-LINSAT optimization problems to LDPC decoding problems on pure-state channels. Our results justify the use of BPQM in the decoding step of DQI and of coding-theoretic algorithms based on Regev's reduction whenever the code is drawn from one of the random LDPC ensembles analyzed here and the induced memoryless symmetric pure-state channel lies in the BPQM success region. Curiously, our numerical results indicate that DQI+BPQM achieves a satisfaction ratio that closely matches that of simulated annealing.

0.41

Non-Binary Quasi-Cyclic LDPC Codes with Entanglement Assistance

cs.IT ·2026-08-17 ·Pavan Kumar, Shayan Srinivasa Garani
similarity 0.67
Abstract · 6 pages

We construct two families of non-binary entanglement assisted (EA) quasi-cyclic (QC) quantum low-density parity-check (QLDPC) codes over arbitrary finite fields, each possessing a precisely determined code rate. The first family is derived from a pair of non-binary classical QC-LDPC codes, designed such that the unassisted portion of the overall Tanner graph of the resulting EA-QC-QLDPC code is free of 4-cycles. The second family, on the other hand, is constructed from a single non-binary classical QC-LDPC code whose Tanner graph itself is 4-cycle-free. In developing the codes belonging to the first family, we employ a \emph{single Bell pair} to establish entanglement between the transmitter and the receiver, thereby minimizing the required entanglement resources. Furthermore, these constructions demonstrate that careful graph-based design can effectively balance error-correction performance with entanglement consumption, providing a practical approach for realizing efficient non-binary EA-QC-QLDPC codes.

0.11

Classical Tensor Codes and Quantum Tanner Codes Achieve Capacity on Erasure Channels

cs.IT ·2026-11-10 ·Henry D. Pfister, Oscar Sprumont, Gilles Zémor
similarity 0.67
Abstract

We show that on the classical erasure channel, the tensor product of two capacity-achieving code families is itself capacity-achieving under mild conditions. We also prove that duals of tensor products of independent uniform random binary linear codes achieve erasure capacity. Using these local codes, for every erasure probability $ρ\in(0,1/2)$ and every rate gap $\varepsilon>0$, we obtain a family of binary quantum Tanner codes of rate at least $1-2ρ-\varepsilon$. For fixed $ρ$ and $\varepsilon$, these codes have bounded check weights, minimum distance growing linearly with the blocklength, and a linear-time erasure decoder whose decoding error decays exponentially with the blocklength.

0.21