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:1205.7036 · Quantum Information and Computation

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

Nicolas Delfosse, Gilles Zémor

Published Sep 1, 2013• 37 citations
arXivHTMLPDF

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

DOI
10.26421/qic13.9-10-4

Related papers

Quantum erasure-correcting codes and percolation on regular tilings of the hyperbolic plane

Nicolas Delfosse, Gilles Zémor

We are interested in percolation for a family of self-dual tilings of the hyperbolic plane. We achieve an upper bound on the critical probability for these tilings by taking appropriate finite quotients and associating them with a family of quantum CSS codes. We then relate the probability of percolation to the probability of a decoding error for these codes on the quantum erasure channel.

IEEE Information Theory Workshop (ITW)•Aug 1, 2010•15 citations

Fidelity of Finite Length Quantum Codes in Qubit Erasure Channel

Alexei Ashikhmin

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 error for finite length stabilizer and CSS codes. CSS codes have many advantages for practical applications. Our results show that CSS codes of small lengths, like 100 qubits, visibly lose in performance to generic stabilizer codes.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•2 citations

Stabilizer-Code Channel Transforms Beyond Repetition Codes for Improved Hashing Bounds

Tyler Kann, Matthieu R. Bloch, Shrinivas Kudekar +1 more

The quantum hashing bound guarantees that rates up to $1-H(p_I, p_X, p_Y, p_Z)$ are achievable for memoryless Pauli channels, but it is not generally tight. A known way to improve achievable rates for certain asymmetric Pauli channels is to apply a small inner stabilizer code to a few channel uses, decode, and treat the resulting logical noise as an induced Pauli channel; reapplying the hashing argument to this induced channel can beat the baseline hashing bound. We generalize this induced-channel viewpoint to arbitrary stabilizer codes used purely as channel transforms. Given any $ [\![ n, k ]\!] $ stabilizer generator set, we construct a full symplectic tableau, compute the induced joint distribution of logical Pauli errors and syndromes under the physical Pauli channel, and obtain an achievable rate via a hashing bound with decoder side information. We perform a structured search over small transforms and report instances that improve the baseline hashing bound for a family of Pauli channels with skewed and independent errors studied in prior work.

cs.ITCross-listedarXiv:2601.15505•IEEE International Symposium on Information Theory (ISIT)•Jan 23, 2026•1 citation

Random Quantum LDPC Codes Approaching the Gilbert-Varshamov Bound

Tushant Mittal, Shashank Srivastava, Madhur Tulsiani +1 more

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.

cs.ITCross-listedarXiv:2610.02648•Oct 5, 2026•2 citations

Polylog-LDPC Capacity Achieving Codes for the Noisy Quantum Erasure Channel

Seth Lloyd, Peter W. Shor, Kevin Thompson

We provide polylog sparse quantum codes for correcting the Erasure channel arbitrarily close to the capacity. Specifically, we provide the [[n, k, d]] 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 (S1, S2, ... Sn-k) such that |Si| ≤ log2+ζ(n) for all i and for any ζ > 0 with high probability. In this paper, we show that the result of Delfosse et al. is tight: one can construct capacity approaching codes with weight almost O(1).

arXiv:1703.00382•IEEE Transactions on Information Theory•Jun 26, 2019•3 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
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.
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 error for finite length stabilizer and CSS codes. CSS codes have many advantages for practical applications. Our results show that CSS codes of small lengths, like 100 qubits, visibly lose in performance to generic stabilizer codes.
The quantum hashing bound guarantees that rates up to 1−H(pI,pX,pY,pZ)1-H(p_I, p_X, p_Y, p_Z)1−H(pI​,pX​,pY​,pZ​) are achievable for memoryless Pauli channels, but it is not generally tight. A known way to improve achievable rates for certain asymmetric Pauli channels is to apply a small inner stabilizer code to a few channel uses, decode, and treat the resulting logical noise as an induced Pauli channel; reapplying the hashing argument to this induced channel can beat the baseline hashing bound. We generalize this induced-channel viewpoint to arbitrary stabilizer codes used purely as channel transforms. Given any $ [\![ n, k ]\!] $ stabilizer generator set, we construct a full symplectic tableau, compute the induced joint distribution of logical Pauli errors and syndromes under the physical Pauli channel, and obtain an achievable rate via a hashing bound with decoder side information. We perform a structured search over small transforms and report instances that improve the baseline hashing bound for a family of Pauli channels with skewed and independent errors studied in prior work.
We show that for any R,ε>0R,ε>0R,ε>0 and any prime p≥2p\geq 2p≥2, there exists an infinite family of ppp-ary quantum low-density parity-check (QLDPC) codes, rate RRR, checks of weight Oε(1)O_ε(1)Oε​(1), and normalized distance at least δGV(p,R)−εδ_{\mathrm{GV}}(p,R)-εδGV​(p,R)−ε. Here, δGV(p,R)δ_{\mathrm{GV}}(p,R)δGV​(p,R) denotes the quantum Gilbert-Varshamov (GV) bound for ppp-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.
We provide polylog sparse quantum codes for correcting the Erasure channel arbitrarily close to the capacity. Specifically, we provide the [[n, k, d]] 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 (S1, S2, ... Sn-k) such that |Si| ≤ log2+ζ(n) for all i and for any ζ > 0 with high probability. In this paper, we show that the result of Delfosse et al. is tight: one can construct capacity approaching codes with weight almost O(1).
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.