CS Paper Radar

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

Henry D. Pfister, Oscar Sprumont, Gilles Zémor

cs.IT ·submitted 2026-11-10 13:50 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Random Quantum LDPC Codes Approaching the Gilbert-Varshamov Bound

cs.IT quant-ph ·2026-10-02 ·Tushant Mittal, Shashank Srivastava, Madhur Tulsiani, Mary Wootters
highly cited similarity 0.72
Abstract

We show that for any $R,ε>0$ and any prime $p\geq 2$, there exists an infinite family of $p$-ary quantum low-density parity-check (QLDPC) codes, rate $R$, checks of weight $O_ε(1)$, and normalized distance at least $δ_{\mathrm{GV}}(p,R)-ε$. Here, $δ_{\mathrm{GV}}(p,R)$ denotes the quantum Gilbert-Varshamov (GV) bound for $p$-ary stabilizer codes. In fact, we construct an ensemble of such QLDPC codes, such that a random code from this ensemble is close to the GV bound with high probability. Moreover, this ensemble matches the performance of random stabilizer codes on several quantum channels. Specifically, it approaches the quantum capacity of the erasure channel and the hashing bound for memoryless Pauli channels, including the depolarizing channel. A significant challenge in working with QLDPC codes is that they are necessarily \emph{degenerate}, i.e., contain many low-weight stabilizers. A key contribution of our work is a construction of QLDPC codes with quantitative control on their degeneracy. These codes are obtained by combining known constructions of asymptotically good QLDPC codes with the expander-based distance amplification procedure of Alon, Edmonds, and Luby [FOCS'95]. Our random ensemble is constructed by starting with these low-degeneracy QLDPC codes near the quantum Singleton bound and concatenating each coordinate with a random inner code. This can be viewed as a quantum analogue of Thommesen's construction, and as an LDPC version of a result of Ouyang, with an appropriately designed outer code.

0.44

Bounds for Pure Disjoint $(r,δ)$-Quantum Locally Recoverable Codes

cs.IT quant-ph ·2026-08-11 ·Evagoras Stylianou, Holger Boche
publishedtheory similarity 0.71
Abstract · Accepted for presentation at the 2026 IEEE International Symposium on Information Theory (ISIT 2026)

We study pure disjoint $(r,δ)$-quantum locally recoverable codes (qLRCs) without assuming a stabilizer structure. We formulate local Knill--Laflamme conditions for recovery from up to $δ-1$ erasures within a recovery block, and introduce blockwise Shor--Laflamme and unitary weight enumerators that capture how error weight is distributed across recovery sets. We establish several properties of these enumerators and use them to derive a Singleton-like bound that strengthens the known bound for disjoint $(r,δ)$-qLRCs under a purity assumption, as well as a linear-programming upper bound on the code dimension. These results provide a non-stabilizer, weight-enumerator-based approach to the study of pure disjoint $(r,δ)$-qLRCs.

0.52

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.70
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 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.70
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

Linear-time erasure recovery for quantum expander codes

cs.IT quant-ph ·2026-11-04 ·Anirudh Krishna, Christopher A. Pattison
similarity 0.70
Abstract

Erasures are used to model faults at a subset of known locations in various platforms used to construct fault-tolerant quantum computers. Beyond the utility in erasure recovery, efficient decoders for erasures are useful to both understand error decoders and as a subroutine for error decoding. Classical expander codes, which belong to the family of low-density parity-check (LDPC) codes, can be equipped with the Peeling decoder which works in linear time. Our main result is the algorithm Small-Set-Peeling, a quantum generalization of the classical Peeling decoder for erasures, that applies to quantum expander codes (Tillich, Zémor, IEEE T-IT 2013; Leverrier, Tillich, Zémor, FOCS 2015). This decoder can correct up to $D-1$ erasures, where $D$ is the (design) distance of the code and, importantly, is the first decoder that is guaranteed to do so in linear time. Combining with the erasure-conversion algorithm Small-Set-Find (Krishna, Livni-Navon, Wootters, SODA 2024), our result also implies the existence of a novel graph-local linear-time decoder for Pauli errors.

0.22

Entanglement-assisted quantum locally recoverable codes: bounds and constructions with availability

cs.IT quant-ph ·2026-08-10 ·Rutuja Kshirsagar, Gretchen L. Matthews, Julia Shapiro
similarity 0.69
Abstract

In this work, we define entanglement-assisted quantum locally recoverable codes with availability, in which any set of up to $δ-1$ erased qudits can be recovered from any one of $t$ local recovery sets, each of size at most $r+δ-1$, with the recovery sets intersecting exactly in the erased coordinates, where $r$ is a (small) positive integer. We show that shared entanglement permits $t>1$, meaning that multiple local recovery sets can be available for the same set of up to $δ-1$ erasures. We establish a Singleton-like bound for this family of codes and present random constructions based on classical linear codes with Vandermonde parity-check matrices. We also provide explicit constructions of entanglement-assisted quantum locally recoverable codes with availability from several classical code families and their folded versions, including Tamo-Barg codes, fiber-product codes, and algebraic-geometry codes such as one-point Hermitian and Suzuki codes.

0.42

An Upper Bound to the Undetected Error Exponent with Erasure Decoding at Positive Rates

cs.IT ·2026-10-11 ·Seyed AmirPouya Moeini, Marco Dalai, Albert Guillén i Fàbregas
theory similarity 0.68
Abstract

We study the undetected-error exponent of discrete memoryless channels with erasure decoding. Assuming that the undetected-error and erasure probabilities vanish, we derive an upper bound on the undetected-error exponent at positive rates. The bound uses Somekh-Baruch's genie-aided argument where an auxiliary output provides the decoder with a list of codewords. It recovers Telatar's tight rate-zero converse and is at least as tight as the straight-line bound. A numerical example shows that the improvement over the straight-line bound can be strict.

0.16

A Spectrum-Based Converse for Quantum State Discrimination and Its Applications to Classical-Quantum Channel Coding

cs.IT quant-ph ·2026-10-05 ·Tam{á}s Havas, Hsuan-Yin Lin, Eirik Rosnes
theory similarity 0.68
Abstract

We investigate converse bounds on the average decoding error probability in finite-blocklength classical-quantum channel coding. We first present a lower bound for multiple quantum hypothesis testing in terms of pairwise trace distances and derive a corresponding fidelity bound. We then obtain a spectrum-based converse that depends only on the a priori probabilities and spectra of the states. We show that the converse bound remains tight for the quantum depolarizing channel under suitable conditions. For codes with product-state outputs, this converse takes an explicit form involving products of output-state eigenvalues. We apply it to binary codes over the quantum amplitude damping channel using the input states $\vert+\rangle$ and $\vert-\rangle$. For this setting, we also discuss a normal approximation to the spectrum-based converse in the large blocklength regime. In all numerical examples considered, the spectrum-based converse is tighter than the other converse bounds at low noise levels.

0.09