Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2611.14087

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

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

Published Nov 10, 2026• 0 citations
arXivHTMLPDF

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.

DOI
10.48550/arxiv.2611.14087

Related papers

Decoding Quantum Tanner Codes

Anthony Leverrier, Gilles Zémor

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.

arXiv:2208.05537•IEEE Transactions on Information Theory•Apr 17, 2023•52 citations

The n-shot classical capacity of the quantum erasure channel

Matteo Rosati

Abstract We compute the n-shot classical capacity of the quantum erasure channel, providing upper bounds and almost-matching lower bounds for it, the latter achievable via large-minimum-distance classical linear codes for any n. The protocols are in full product form, i.e. no entanglement is needed either at the encoder or decoder to attain the capacity, and they explicitly adapt to the transition between different error regimes as the erasure probability increases. Finally, we show that our upper and lower bounds on the capacity are tighter than those obtainable from the general theory of finite-size capacity via generalized divergences.

Journal of Physics Communications•Aug 1, 2024•2 citations

Finite-blocklength classical communication over the quantum erasure channel with and without classical feedback

Mark M. Wilde

We determine the optimal success probability for transmitting a fixed number of classical messages through a finite number of uses of the quantum erasure channel, assisted by noiseless classical feedback and without initial shared entanglement. For an input dimension $d$, an erasure probability $p$, a blocklength $n$, and $M$ equiprobable messages, the optimal success probability is equal to $E[\min\{1,d^K/M\}]$, where $K$ is binomial with parameters $n$ and $1-p$. The converse allows arbitrary adaptive quantum encoders, quantum memories, and receiver instruments. Its main ingredient is an elementary dimension bound for noiseless quantum communication with classical feedback, proved by fixing the classical controls without conditioning the sender's state on the observed transcript. A classical protocol that transmits the base-$d$ digits of an integer representing the message, repeating each digit until the receiver acknowledges its reception or the prescribed blocklength is reached, attains the bound for every integer $M$. We also establish a relative-majorization property of erasure-channel outputs and exactly evaluate a hypothesis-testing converse, recovering the same numerical bound without feedback. That converse need not be achievable without feedback: four uses of the qubit erasure channel and four messages give a strict gap. A product-state code employing tetrahedral qubit states nevertheless outperforms every classical binary erasure code with these parameters. We give an explicit message-size formula and show that the bounded-remainder normal approximation and the average-success strong-converse exponent are unchanged without feedback. We also determine the feedback-assisted error exponent below capacity, prove that it agrees with the no-feedback exponent above a critical rate, and give no-feedback bounds at lower rates.

quant-pharXiv:2610.00440•Oct 1, 2026•2 citations

Upper bounds on the rate of low density stabilizer codes for the quantum erasure channel

Nicolas Delfosse, Gilles Zémor

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 \leq 1-2p$, for stabilizer codes: we also derive an improved upper bound of the form $R \leq 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 with appropriate finite quotients of these tilings. We then relate the probability of percolation to the probability of a decoding error for these codes on the quantum erasure channel. The application of our upper bound on achievable rates of low density stabilizer codes gives rise to an upper bound on the critical probability for these tilings.

arXiv:1205.7036•Quantum Information and Computation•Sep 1, 2013•37 citations

Reed-Muller Codes for Random Erasures and Errors

Emmanuel A. Abbe, Amir Shpilka, Avi Wigderson

This paper studies the parameters for which binary Reed-Muller (RM) codes can be decoded successfully on the BEC and BSC, and in particular when can they achieve capacity for these two classical channels. Necessarily, the paper also studies properties of evaluations of multi-variate GF(2) polynomials on random sets of inputs. For erasures, we prove that RM codes achieve capacity both for very high rate and very low rate regimes. For errors, we prove that RM codes achieve capacity for very low rate regimes, and for very high rates, we show that they can uniquely decode at about square root of the number of errors at capacity.

ACM Symposium on Theory of Computing (STOC)•Jun 3, 2015•18 citations

From Bit to Block: Decoding on Erasure Channels

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

We provide a general framework for bounding the block error threshold of a linear code$C \subseteq \mathbb{F}_{2}^{N}$over the erasure channel in terms of its bit error threshold. Our approach relies on understanding the minimum support weight of any$r$-dimensional subcode of$C$, for all small values of$r$. As a proof of concept, we use our machinery to obtain a new proof of the celebrated result that Reed-Muller codes achieve capacity on the erasure channel with respect to block error probability.

arXiv:2501.05748•IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•5 citations
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 ρ∈(0,1/2)ρ\in(0,1/2)ρ∈(0,1/2) and every rate gap ε>0\varepsilon>0ε>0, we obtain a family of binary quantum Tanner codes of rate at least 1−2ρ−ε1-2ρ-\varepsilon1−2ρ−ε. 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.
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.
Abstract We compute the n-shot classical capacity of the quantum erasure channel, providing upper bounds and almost-matching lower bounds for it, the latter achievable via large-minimum-distance classical linear codes for any n. The protocols are in full product form, i.e. no entanglement is needed either at the encoder or decoder to attain the capacity, and they explicitly adapt to the transition between different error regimes as the erasure probability increases. Finally, we show that our upper and lower bounds on the capacity are tighter than those obtainable from the general theory of finite-size capacity via generalized divergences.
We determine the optimal success probability for transmitting a fixed number of classical messages through a finite number of uses of the quantum erasure channel, assisted by noiseless classical feedback and without initial shared entanglement. For an input dimension ddd, an erasure probability ppp, a blocklength nnn, and MMM equiprobable messages, the optimal success probability is equal to E[min⁡{1,dK/M}]E[\min\{1,d^K/M\}]E[min{1,dK/M}], where KKK is binomial with parameters nnn and 1−p1-p1−p. The converse allows arbitrary adaptive quantum encoders, quantum memories, and receiver instruments. Its main ingredient is an elementary dimension bound for noiseless quantum communication with classical feedback, proved by fixing the classical controls without conditioning the sender's state on the observed transcript. A classical protocol that transmits the base-ddd digits of an integer representing the message, repeating each digit until the receiver acknowledges its reception or the prescribed blocklength is reached, attains the bound for every integer MMM. We also establish a relative-majorization property of erasure-channel outputs and exactly evaluate a hypothesis-testing converse, recovering the same numerical bound without feedback. That converse need not be achievable without feedback: four uses of the qubit erasure channel and four messages give a strict gap. A product-state code employing tetrahedral qubit states nevertheless outperforms every classical binary erasure code with these parameters. We give an explicit message-size formula and show that the bounded-remainder normal approximation and the average-success strong-converse exponent are unchanged without feedback. We also determine the feedback-assisted error exponent below capacity, prove that it agrees with the no-feedback exponent above a critical rate, and give no-feedback bounds at lower rates.
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≤1−2pR \leq 1-2pR≤1−2p, for stabilizer codes: we also derive an improved upper bound of the form R≤1−2p−D(p)R \leq 1-2p-D(p)R≤1−2p−D(p) with a function D(p)D(p)D(p) that stays positive for 0<p<1/20<p<1/20<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 with appropriate finite quotients of these tilings. We then relate the probability of percolation to the probability of a decoding error for these codes on the quantum erasure channel. The application of our upper bound on achievable rates of low density stabilizer codes gives rise to an upper bound on the critical probability for these tilings.
This paper studies the parameters for which binary Reed-Muller (RM) codes can be decoded successfully on the BEC and BSC, and in particular when can they achieve capacity for these two classical channels. Necessarily, the paper also studies properties of evaluations of multi-variate GF(2) polynomials on random sets of inputs. For erasures, we prove that RM codes achieve capacity both for very high rate and very low rate regimes. For errors, we prove that RM codes achieve capacity for very low rate regimes, and for very high rates, we show that they can uniquely decode at about square root of the number of errors at capacity.
We provide a general framework for bounding the block error threshold of a linear codeC⊆F2NC \subseteq \mathbb{F}_{2}^{N}C⊆F2N​over the erasure channel in terms of its bit error threshold. Our approach relies on understanding the minimum support weight of anyrrr-dimensional subcode ofCCC, for all small values ofrrr. As a proof of concept, we use our machinery to obtain a new proof of the celebrated result that Reed-Muller codes achieve capacity on the erasure channel with respect to block error probability.