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:1703.00382 · IEEE Transactions on Information Theory

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

Seth Lloyd, Peter W. Shor, Kevin Thompson

Published Jun 26, 2019• 3 citations
arXivHTMLPDF

Abstract

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

DOI
10.1109/tit.2019.2925100

Related papers

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

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

Capacity Achieving Codes for an Erasure Queue-channel

Jaswanthi Mandalapu, Avhishek Chatterjee, Krishna Jagannathan +1 more

We consider a queue-channel model that captures the waiting time-dependent degradation of information bits as they wait to be transmitted. Such a scenario arises naturally in quantum communications, where quantum bits tend to decohere rapidly. Trailing the capacity results obtained recently for certain queue-channels, this paper aims to construct practical channel codes for the erasure queue-channel (EQC)—a channel characterized by highly correlated erasures, governed by the underlying queuing dynamics. Our main contributions in this paper are twofold: (i) We propose a generic ‘wrapper’ based on interleaving across renewal blocks of the queue to convert any capacity-achieving block code for a memoryless erasure channel to a capacity-achieving code for the EQC. Next, due to the complexity involved in implementing interleaved systems, (ii) we study the performance of LDPC and Polar codes without any interleaving. We show that standard Arıkan’s Polar transform polarizes the EQC for certain restricted class of erasure probability functions. We also highlight some possible approaches and the corresponding challenges involved in proving the polarization of a general EQC.

arXiv:2305.04155•IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2023•2 citations

Capacity Achieving Channel Codes for an Erasure Queue-Channel

Jaswanthi Mandalapu, Krishna Jagannathan, Andrew Thangaraj

We consider a queue-channel model that captures the waiting time-dependent degradation of information bits as they wait to be transmitted. Such a scenario arises naturally in quantum communications, where information bits become useless after a certain time. Trailing the capacity results obtained recently for certain queue-channels, this paper aims to construct practical channel codes for the erasure queue-channel (EQC)—a channel characterized by highly correlated erasures, governed by the underlying queuing dynamics. Our main contributions in this paper are twofold: (i) We propose a generic ‘wrapper’ based on interleaving across renewal blocks of the queue to convert any capacity-achieving code for a memoryless erasure channel to a capacity-achieving code for the EQC. Next, due to the complexity involved in implementing interleaved systems, (ii) we study the performance of LDPC and Polar codes without any interleaving. Motivated by the empirical performance, we show that standard Arıkan’s Polar transform polarizes the M/M/1 EQC.

IEEE Transactions on Communications•Jun 24, 2024•0 citations

A class of quantum LDPC codes: construction and performances under iterative decoding

Thomas Camara, Harold Ollivier, Jean–Pierre Tillich

A generic method for constructing quantum LDPC codes is presented. We first explain how to overcome the difficulty of finding a set of low weight generators for the stabilizer group of the code. Our approach is based on a graph representation of the generators of the stabilizer group and on a simple local rule to ensure commutativity. We provide several specific examples of quantum LDPC codes obtained by our method, together with numerical simulations over the depolarizing channel and the erasure channel.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2007•51 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
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).
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.
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 a queue-channel model that captures the waiting time-dependent degradation of information bits as they wait to be transmitted. Such a scenario arises naturally in quantum communications, where quantum bits tend to decohere rapidly. Trailing the capacity results obtained recently for certain queue-channels, this paper aims to construct practical channel codes for the erasure queue-channel (EQC)—a channel characterized by highly correlated erasures, governed by the underlying queuing dynamics. Our main contributions in this paper are twofold: (i) We propose a generic ‘wrapper’ based on interleaving across renewal blocks of the queue to convert any capacity-achieving block code for a memoryless erasure channel to a capacity-achieving code for the EQC. Next, due to the complexity involved in implementing interleaved systems, (ii) we study the performance of LDPC and Polar codes without any interleaving. We show that standard Arıkan’s Polar transform polarizes the EQC for certain restricted class of erasure probability functions. We also highlight some possible approaches and the corresponding challenges involved in proving the polarization of a general EQC.
We consider a queue-channel model that captures the waiting time-dependent degradation of information bits as they wait to be transmitted. Such a scenario arises naturally in quantum communications, where information bits become useless after a certain time. Trailing the capacity results obtained recently for certain queue-channels, this paper aims to construct practical channel codes for the erasure queue-channel (EQC)—a channel characterized by highly correlated erasures, governed by the underlying queuing dynamics. Our main contributions in this paper are twofold: (i) We propose a generic ‘wrapper’ based on interleaving across renewal blocks of the queue to convert any capacity-achieving code for a memoryless erasure channel to a capacity-achieving code for the EQC. Next, due to the complexity involved in implementing interleaved systems, (ii) we study the performance of LDPC and Polar codes without any interleaving. Motivated by the empirical performance, we show that standard Arıkan’s Polar transform polarizes the M/M/1 EQC.
A generic method for constructing quantum LDPC codes is presented. We first explain how to overcome the difficulty of finding a set of low weight generators for the stabilizer group of the code. Our approach is based on a graph representation of the generators of the stabilizer group and on a simple local rule to ensure commutativity. We provide several specific examples of quantum LDPC codes obtained by our method, together with numerical simulations over the depolarizing channel and the erasure channel.
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.