AI summary · arXiv: 2611.14087v1 · cs.IT

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

Henry D. Pfister, Oscar Sprumont, Gilles Zémor
Original paper Submitted to arXiv on 10 Nov. 2026 License: CC BY 4.0 Also in: fr

How to read this summary? Illustrated guide

The essentials

The paper proves classical tensor-code capacity results and constructs quantum Tanner codes that approach quantum erasure capacity with linear-time decoding and exponentially small failure probability.

Question

Can tensor products and their duals preserve erasure-channel capacity, and can these classical results enable quantum Tanner codes to decode near the quantum erasure capacity? The work also asks whether this can be achieved with bounded check weights, linear distance, and a linear-time decoder.

Method

The authors analyze erasure decoding of tensor products by comparing independent erasures with correlated patterns and use robustness properties to establish capacity for duals of tensor products of independent uniform random binary linear codes. They then construct CSS quantum Tanner codes on fixed-degree Cayley square complexes, using four local component codes and local decoding followed by adversarial decoding; for fixed erasure probability and rate gap, the degree and local codes are independent of blocklength.

Findings

  • Result Under the stated minimum-distance and error-decay conditions, tensor products of capacity-achieving code families also achieve erasure capacity.
    See the passage in the paper
    If the families achieve capacity on the erasure channel and have minimum distance $\omega(\log n)$, where $n$ denotes the blocklength, then the tensor family $\mathcal{F}_{0}\otimes\mathcal{F}_{1}$ also achieves capacity on the erasure channel.
  • Result Duals of tensor products of independent uniform random binary linear codes achieve erasure capacity.
    See the passage in the paper
    Duals of tensor codes of independent uniform random linear codes of the same length and rate $R_{0}$ and $R_{1}$ can be decoded from a proportion $p$ of erasures that converges with the code length to $p=R_{0}R_{1}$.
  • Result For each fixed $\rho\in(0,1/2)$ and rate gap $\varepsilon>0$, the constructed quantum Tanner codes have rate at least $1-2\rho-\varepsilon$ and exponentially small erasure-decoding failure probability.
    See the passage in the paper
    Then there exists positive constants $a,\Delta,N_{0}$ (i.e. depending only on $\rho$ and $\varepsilon$) such that for all $N>N_{0}$, the quantum Tanner code $C_{\rho,\varepsilon,\Delta,N}$ has rate at least $1-2\rho-\varepsilon$ and can decode random quantum erasures of rate $\rho$ with probability
  • Result For fixed erasure probability and rate gap, the quantum Tanner codes have linear minimum distance, bounded stabilizer weights, and a linear-time decoder.
    See the passage in the paper
    For fixed $\rho$ and $\varepsilon$, the degree and the local codes are fixed independently of $N$. The resulting codes have constant stabilizer weights and qubit degrees with minimum distance growing linearly with $N$.
  • Authors’ interpretation The quantum construction combines local erasure decoding with an adversarial decoder to handle the residual errors.
    See the passage in the paper
    A first round of decoding will remove a large proportion of the erasures, after which we can rely on the adversarial error-correcting capabilities of quantum Tanner code to finish removing the remaining erasures.

Limitations

  • The bounded-weight and linear-time guarantees apply after fixing the target erasure probability and rate gap; the construction does not give one fixed degree and set of local codes for all targets.
    See the passage in the paper
    For the bounded-check-weight and linear-time claims, the degree $\Delta$, the local codes, and the distance are chosen after the target rate and gap.
  • The construction is asymptotic and relies on choosing a sufficiently large fixed degree before the blocklength grows.
    See the passage in the paper
    A sufficiently large $\Delta$ is then chosen after which the total length can be taken to grow to infinity.

Why it matters

The authors present a capacity-approaching quantum erasure code within the quantum Tanner framework that, unlike the cited concurrent construction, includes a linear-time decoder. Their tensor-product results also establish classical tools for designing quantum codes with these performance guarantees.

Written by AI from the paper. Passages are checked word for word against the text we analysed; the rest may contain errors.

AI-generated keywords: quantum Tanner codes erasure-channel capacity tensor-product codes quantum LDPC codes linear-time decoding

Read further

  • Comprehensive Summary
  • Layman's Summary
  • Blog article
  • Original abstract
The paper asks whether quantum Tanner codes can approach the erasure-channel capacity while retaining bounded-weight checks and efficient decoding. For a quantum erasure probability \(\rho<1/2\), the capacity rate is \(1-2\rho\). The authors also study a classical problem that underlies their construction: whether tensor products of good codes, and duals of tensor products of random codes, can correct erasures close to their respective capacities. The classical argument first shows that, in terms of the expected dimension of the subcode supported entirely on erased coordinates, correlated erasures are no easier to decode than independent erasures. The key observation is that this dimension is a supermodular function of the erasure pattern. The authors represent an independent erasure pattern as the union of two patterns, then replace one pattern with a column-correlated pattern. This enables a two-stage decoder: it decodes columns using one component code, then rows using the other. If the component codes have lengths \(n_1,n_2\) and failure probabilities \(\delta_1,\delta_2\) at the relevant erasure rates, the tensor code’s failure probability is bounded by \(n_1n_2(n_2\delta_1+\delta_2)\). Thus, capacity-achieving component families with sufficiently small failure probabilities yield capacity-achieving tensor products. In particular, tensor products of independent uniform random binary linear codes achieve classical erasure capacity. The paper also proves that duals of tensor products of independent random codes achieve classical erasure capacity. This is more difficult because a code’s capacity-achieving property does not automatically extend to its dual. The proof combines product expansion, which decomposes dual-tensor codewords into row and column contributions, with bounds on the dimension and minimum weight of codewords covered by random erasures. The resulting theorem provides a concrete near-capacity guarantee. For component rates \(1-\rho_1\) and \(1-\rho_2\), the dual tensor can correct erasures at rate \(1-\rho-n^{-1/2+3\nu/2}\), where \(\rho=\rho_1+\rho_2-\rho_1\rho_2\) and \(0<\nu<1/3\). For sufficiently large \(n\), its ensemble-average failure probability is at most \(4n^{-\nu/2}\). For the quantum construction, the authors generalize quantum Tanner codes by using four different local component codes, assigned to the four vertex classes of a quadripartite square complex. Asymmetric component rates concentrate most checks on two vertex classes. Local tensor-code decoders first recover most erased errors, after which an existing adversarial-error decoder handles the remainder. Random component codes provide the required distance, robustness, and local erasure performance, while Ramanujan Cayley graphs provide expansion. The main result states that, for every \(\rho\in(0,1/2)\) and every positive rate gap \(\epsilon\), there is a family of binary quantum Tanner codes with rate at least \(1-2\rho-\epsilon\). For fixed \(\rho\) and \(\epsilon\), the local degree remains fixed as the blocklength grows. The codes have bounded-weight stabilizers, minimum distance proportional to the blocklength, and a linear-time decoder that corrects random erasures at rate \(\rho\) with failure probability exponentially small in the blocklength. These conclusions require sufficiently large fixed local degree and the stated expansion and random-code properties. They establish asymptotic existence and performance, not an explicit practical construction or decoder.

Was this synthesis useful?

Score: 0

Why do we need votes?

Votes are used to determine whether we need to re-run our summarizing tools. If the count reaches -10, our tools can be restarted.

Figures and plots

Ask about a figure by number or use its question button to request visual analysis. Up to two figures and four image panels per question. Values read from plots are approximate; check the original data.

AI assistant instructions?

Tools for this paper

Explain it differently 1 free rewrite left today
Save to a collection Group papers in collections to compare them, chat with them and export them. Continue with Google Create a free account Log in

Advanced tools Premium

For researchers who follow a field closely: citation alerts, journal-club slides, version comparison and Zotero export. Discover Premium

Zotero Zotero guide
Citation alerts Citation alerts guide
Who works on it?

Among the 23 papers around this one, the name that comes back most: Anthony Leverrier (5 papers)

6 more people sign several of them. The full map adds their institutions and approaches, from the papers of the last years.

Continue with Google Create a free account: your first map is free
Weekly letter Presented in "Computing beyond AI this week" of 16 November 2026. Computing beyond AI this week: The costs hidden in our maps, networks and algorithms · Receive one by email for free

Papers around this one

See them on a map

Ranked by how close their title and abstract are to this paper’s. Select some to read them together.

Closest papers

  1. Very close Another approach to the problem Cited by this paper
    Efficient Decoding up to a Constant Fraction of the Code Length for Asymptotically Good Quantum Codes
    Anthony Leverrier, Gilles Z'emor · 2022 · Electron. Colloquium Comput. Complex. · cited 51 times · Not summarized yet

    The paper develops a linear-time decoder for adversarial errors in quantum Tanner codes, while the target uses local and adversarial decoding for erasures.

    Abstract

    We introduce and analyse an efficient decoder for quantum Tanner codes that can correct adversarial errors of linear weight. Previous decoders for quantum low-density parity-check codes could only handle adversarial errors of weight \(O(\sqrt{n\log n})\) . We also work on the link between quantum Tanner codes and the lifted product codes of Panteleev and Kalachev and show that our decoder can be adapted to the latter. The decoding algorithm alternates between sequential and parallel procedures and converges in linear time.

  2. Very close Another approach to the problem Cited by this paper Used in depth by this paper
    Decoding Quantum Tanner Codes
    Anthony Leverrier, Gilles Zémor · 2022 · IEEE Transactions on Information Theory · cited 49 times · Not summarized yet

    The paper introduces sequential and parallel decoders for adversarial errors in quantum Tanner codes; the target studies linear-time erasure decoding for these codes.

    Abstract

    We introduce sequential and parallel decoders for quantum Tanner codes. When the Tanner code construction is applied to a sufficiently expanding square complex with robust local codes, we obtain a family of asymptotically good quantum low-density parity-check codes. In this case, our decoders provably correct arbitrary errors of weight linear in the code length, respectively in linear or logarithmic time. The same decoders are easily adapted to the expander lifted product codes of Panteleev and Kalachev. Along the way, we exploit recently established bounds on the robustness of random tensor codes to give a tighter bound on the minimum distance of quantum Tanner codes.

  3. Very close Same question Cited by this paper
    Polylog-LDPC Capacity Achieving Codes for the Noisy Quantum Erasure Channel
    S. Lloyd, P. Shor, Kevin Thompson · 2017 · IEEE Transactions on Information Theory · cited 4 times · Not summarized yet

    The paper constructs sparse quantum codes that approach erasure-channel capacity, while the target achieves near-capacity erasure rates with bounded check weights.

    Abstract

    We provide polylog sparse quantum codes for correcting the Erasure channel arbitrarily close to the capacity. Specifically, we provide the <inline-formula> <tex-math notation="LaTeX">$[[n, k, d]]$ </tex-math></inline-formula> quantum stabilizer codes that correct for the erasure channel arbitrarily close to the capacity if the erasure probability is at least 0.33 and with a generating set <inline-formula> <tex-math notation="LaTeX">$\langle S_{1}, S_{2}, \cdots {} S_{n-k} \rangle $ </tex-math></inline-formula> such that <inline-formula> <tex-math notation="LaTeX">$|S_{i}|\leq {\mathrm{ log}} ^{2+\zeta }(n)$ </tex-math></inline-formula> for all <inline-formula> <tex-math notation="LaTeX">$i$ …

  4. Close Broader context
    Optimal Interleavers for Classical and Quantum Tensor Product Codes
    P. Nadkarni, S. Garani · 2021 · IEEE Communications Letters · cited 1 time · Not summarized yet

    The paper optimizes interleavers for burst correction in classical and quantum tensor product codes, rather than studying erasure capacity.

    Abstract

    By exploiting the subblock structure of a tensor product code, we provide an upper bound on the maximum correctable burst length of tensor product codes used with interleavers designed based on only the minimum distance and the maximum correctable burst length of its component codes, without taking the specific code geometry and soft decoding into consideration. We provide necessary and sufficient conditions for an interleaver to achieve this upper bound. Further, for two cases of the tensor product codes, we design optimal intracodeword interleavers that satisfy the proposed conditions.

  5. Close Groundwork for this paper Cited by this paper
    Capacities of Quantum Erasure Channels
    Charles H. Bennett, D. Divincenzo, J. Smolin · 1997 · Physical Review Letters · cited 362 times · Not summarized yet

    The paper derives the quantum erasure channel’s capacity, providing the benchmark for the target’s capacity-achieving quantum codes.

    Abstract

    The quantum analog of the classical erasure channel provides a simple example of a channel whose asymptotic capacity for faithful transmission of intact quantum states, with and without the assistance of a two-way classical side channel, can be computed exactly. We derive the quantum and classical capacities for the quantum erasure channel and related channels, and compare them to the depolarizing channel, for which only upper and lower bounds on the capacities are known.

  6. Close Same question Cited by this paper
    Upper bounds on the rate of low density stabilizer codes for the quantum erasure channel
    Nicolas Delfosse, G. Zémor · 2012 · Quantum information & computation · cited 41 times · Not summarized yet

    The paper bounds achievable rates for low-density stabilizer codes on the quantum erasure channel, addressing rate limits related to the target’s construction.

    Abstract

    Using combinatorial arguments, we determine an upper bound on achievable rates of stabilizer codes used over the quantum erasure channel. This allows us to recover the no-cloning bound on the capacity of the quantum erasure channel, R is below 1-2p, for stabilizer codes: we also derive an improved upper bound of the form : R is below 1-2p-D(p) with a function D(p) that stays positive for 0 < p < 1/2 and for any family of stabilizer codes whose generators have weights bounded from above by a constant - low density stabilizer codes. We obtain an application to percolation theory for a family of self-dual tilings of the hyperbolic plane. We associate a family of low density stabilizer codes wit…

  7. Close* Broader context
    Degenerate quantum codes and the quantum channel capacity problem
    Graeme Smith, J. Smolin · 2008 · 2008 IEEE Information Theory Workshop · Not summarized yet

    The paper addresses degenerate quantum codes and channel capacity, a broader capacity topic than the target’s erasure-code construction.

  8. Close Same question
    Fidelity of Finite Length Quantum Codes in Qubit Erasure Channel
    A. Ashikhmin · 2020 · International Symposium on Information Theory · cited 5 times · Not summarized yet

    The paper analyzes decoding error for finite-length quantum codes on the qubit erasure channel, while the target establishes asymptotic erasure-decoding performance.

    Abstract

    We consider the probability of decoding error, equivalently the fidelity, of finite length quantum codes assuming quantum information transmission via qubit erasure channel. First, we obtain an analytical expression on this probability via combinatorial invariants of quantum codes. Next, we derive a generalization of the MacWilliams identities for those invariants and use them to formulate a linear programming optimization problem, which allows us to obtain lower bounds on the number of unrecoverable sets of i erasures and the probability of decoding error. Our example shows that the obtain bounds can be very tight. Next, we derive upper (achievability) bounds on the probability of decoding …

Prior work it builds on

  1. Close Groundwork for this paper
    Good Quantum LDPC Codes with Linear Time Decoders
    Irit Dinur, Min-Hsiu Hsieh, Ting Lin et al. · 2022 · Symposium on the Theory of Computing · cited 231 times · Not summarized yet

    The paper constructs good quantum LDPC codes with linear-time decoders using random-code tensor-product robustness, a construction ingredient used by the target.

    Abstract

    We construct a new explicit family of good quantum low-density parity-check codes which additionally have linear time decoders. Our codes are based on a three-term chain (2m× m)V →δ0 (2m)E →δ1 2F where V (X-checks) are the vertices, E (qubits) are the edges, and F (Z-checks) are the squares of a left-right Cayley complex, and where the maps are defined based on a pair of constant-size random codes CA,CB:2m→2Δ where Δ is the regularity of the underlying Cayley graphs. One of the main ingredients in the analysis is a proof of an essentially-optimal robustness property for the tensor product of two random codes.

  2. Close Broader context
    Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time
    Adar Avsian, F. G. Jeronimo, Abhi Shukul · 2026 · arXiv.org · preprint, not peer reviewed · cited 1 time · Not summarized yet

    The paper constructs explicit quantum LDPC codes for list decoding near capacity, whereas the target focuses on erasure decoding capacity.

    Abstract

    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 achiev…

  3. Close Groundwork for this paper
    Two-sided Robustly Testable Codes
    G. Kalachev, P. Panteleev · 2022 · arXiv.org · preprint, not peer reviewed · cited 17 times · Not summarized yet

    The paper proves robustness for tensor products of random linear codes, a property relevant to the target’s tensor-code and quantum Tanner-code analysis.

    Abstract

    We show that the tensor product of two random linear codes is robustly testable with high probability. This implies that one can obtain pairs of linear codes such that their product and the product of their dual codes are simultaneously robustly testable. Such two-sided robustly testable codes (with a much weaker form of robustness) were the key ingredient in the recent constructions of asymptotically good quantum LDPC codes, which ensured their linear minimum distance. We hope that the existence of such codes with a stronger form of robustness, shown here, can be used to simplify the proofs and provide better distance bounds in these constructions. We also give new very simple examples of n…

  4. Close Another approach to the problem
    Stabilizer-Assisted Inactivation Decoding of Quantum Error-Correcting Codes with Erasures
    Giulio Pech, Mert Gökduman, Hanwen Yao et al. · 2026 · International Symposium on Information Theory · cited 5 times · Not summarized yet

    The paper gives a maximum-likelihood erasure decoder for quantum LDPC codes using inactivation and dual peeling, unlike the target’s local decoding approach.

    Abstract

    We present a maximum-likelihood (ML) decoder with reduced complexity for quantum low-density parity-check (QLDPC) codes on the quantum erasure channel. Our decoder combines classical inactivation decoding, which integrates peeling with symbolic guessing, with a new dual peeling procedure. In the dual peeling stage, we perform row operations on the stabilizer matrix to efficiently reveal stabilizer generators and their linear combinations whose support lies entirely on the erased set. Each such stabilizer identified allows us to freely fix a bit in its support without affecting the logical state of the decoded result. This removes a degree of freedom that would otherwise require a symbolic gu…

  5. Close Broader context
    Maximally Extendable Product Codes are Good Coboundary Expanders
    G. Kalachev, P. Panteleev · 2025 · IEEE Annual Symposium on Foundations of Computer Science · cited 16 times · Not summarized yet

    The paper studies expansion of tensor products of random codes, a property connected to quantum LDPC constructions but not specifically to erasure capacity.

    Abstract

    We investigate the coboundary expansion property of tensor product codes, known as product expansion, which plays an important role in recent constructions of good quantum LDPC codes and classical locally testable codes. Prior research has shown that this property is equivalent to agreement testability and robust testability for products of two codes with linear distance. However, for products of more than two codes, product expansion is a strictly stronger property. In this paper, we prove that a collection of an arbitrary number of random codes over a sufficiently large field has good product expansion. We believe that, in the case of four codes, the same ideas can be used to construct goo…

How are these papers found?

We compare the title and abstract of this paper with those of every paper summarized on this site, and with the papers Semantic Scholar recommends, those it cites and those citing it (for a much-cited paper, its most recent citations and, from OpenAlex, the most cited ones). Among the prior work and the follow-ups, the papers that use each other in depth, a method it uses and the much-cited follow-ups come a little higher. The levels (very close, close, related) come from the similarity of the texts, not from a judgment of quality; * marks a paper without an abstract, compared by its title. The sentence under a paper is written by an AI from the two abstracts: check it in the papers. A paper marked not relevant by three readers leaves the list.

Updated on 16 November 2026.

The illustrated guide to the papers around a paper

Disclaimer: The AI-based summarization tool and virtual assistant provided on this website may not always provide accurate and complete summaries or responses. We encourage you to carefully review and evaluate the generated content to ensure its quality and relevance to your needs.