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

Concatenated Codes with One Inner Code: Low-Rate Gilbert-Varshamov Asymptotics from Algebraic-Geometric Codes

Yota Maeda, Ruho Kondo

Published Nov 12, 2026• 0 citations
arXivHTMLPDF

Abstract

Constructing codes that attain the Gilbert-Varshamov (GV) bound while admitting efficient encoding and decoding is a fundamental problem in coding theory. We study concatenated codes that reuse a single binary inner code across all outer coordinates. To exploit existing encoding and decoding algorithms, we restrict the outer codes to random subcodes of scaled copies of prescribed algebraic codes and investigate their minimum distance. Our first contribution is a general upper bound on the minimum-distance failure probability that separates two terms controlled by the inner code's bias moments and the dual weight distribution of the prescribed code, together with sufficient conditions for exponential decay. Our second contribution is a concrete construction satisfying these conditions using algebraic-geometric codes from the Garcia-Stichtenoth tower. For every sufficiently small $\varepsilon>0$, we construct a family of random binary codes $C_m$ whose rates approach $\varepsilon^2$ and satisfy \[ \Pr\left[δ(C_m)\geq\frac12-\sqrt{\frac{\ln 2}{2}}\left(\varepsilon+\frac{\varepsilon^3}{2}\right)\right]\geq 1-2^{-c\varepsilon^4N_m}, \] for all sufficiently large $m$, where $N_m$ is the block length and $c>0$ is independent of $\varepsilon$ and $m$. Thus, the distance guarantee matches the leading coefficient of the GV bound at low rates. For each fixed $\varepsilon$, the construction uses a single inner encoding map throughout the family and admits polynomial-time encoding and unique decoding within a guaranteed radius. This answers the question of Doron, Mosheiff, and Wootters for subcodes of scaled algebraic geometry codes at low rates.

DOI
10.48550/arxiv.2611.16179

Related papers

Quantum Generalized Reed-Solomon codes concatenated with random rate one inner stabilizer codes asymptotically attain the Quantum Gilbert-Varshamov bound

Yingkai Ouyang

AbstractA good quantum code corrects for a linear number of errors. It has been shownthat random codes attains the QGVB with a relative distance H −1q 2 ((1−R)/2) wherethe code is q-ary and R is the rate of the code (number of encoded systems / blocklength). However,randomcodeshavelittlestructure. Inthispaper,westudyafamilyofconcatenatedq-arystabilizercodes. Eachoftheinnercodesisarandomrate1q-arystabilizer code of block length n. The outer code is a quantum MDS code with blocklengthq n andalphabetsizeq n ,anarbitraryrateR≤1,anddistanceN(1−R)/2+1thatmeets the Quantum Singleton bound. Fixing the outer code rate and letting n grow,the concatenated stabilizer code has a distance that almost surely attains the QGVB.This partially generalizes Thommesen’s result, where heshowed thatthedistanceof aconcatenated code with a Reed-Solomon outer code and random inner linear codes ofarbitraryrateattainstheGilbert-Varshamovboundalmostsurely. 1 Introduction A family of q-ary quantum codes of increasing block length is defined to be good if the ratioof its distance to its block length approaches a non-zero constant. Designing good quantumcodes is highly nontrivial, just as it is in the classical case. The quantum Gilbert-Varshamovbound (QGVB) is a lower bound on an achievable relative distance of a quantum code ofa fixed rate. Explicit constructions of good quantum codes for q ≤ 7 have been studied[1, 2, 3], but they all fail to satisfy the QGVB. The QGVB bound is attainable for the familyof all random quantum codes [4], the family of random stabilizer codes [5], and the familyof random nondegenerate stabilizer codes [6], and the family of random degenerate stabilizercodes [6]. We show that concatenated quantum codes, with a quantum outer code havinga known structure and being efficiently decodable, and randomly chosen independent innerquantum codes also attains the QGVB. Thus our family of random quantum codes has morestructure than previously studied examples.In this paper, we generalize a special case of Thommesen’s result [7] to the quantumcase. He showed that a code from the family of binary concatenated codes made with a1

•Apr 7, 2010•0 citations

Concatenated Codes

Ron M. Roth

In this chapter, we continue the discussion on concatenated codes, which was initiated in Section 5.4. The main message to be conveyed in this chapter is that by using concatenation, one can obtain codes with favorable asymptotic performance—in a sense to be quantified more precisely—while the complexity of constructing these codes and decoding them grows polynomially with the code length. We first present a decoding algorithm for concatenated codes, due to Forney. This algorithm, referred to as a generalized minimum distance (in short, GMD) decoder, corrects any error pattern whose Hamming weight is less than half the product of the minimum distances of the inner and outer codes (we recall that this product is a lower bound on the minimum distance of the respective concatenated code). A GMD decoder consists of a nearest-codeword decoder for the inner code, and a combined error–erasure decoder for the outer code. It then enumerates over a threshold value, marking the output of the inner decoder as erasure if that decoder returns an inner codeword whose Hamming distance from the respective received sub-word equals or exceeds that threshold. We show that under our assumption on the overall Hamming weight of the error word, there is at least one threshold for which the outer decoder recovers the correct codeword. If the outer code is taken as a GRS code, then a GMD decoder has an implementation with time complexity that is at most quadratic in the length of the concatenated code.

Cambridge University Press eBooks•Feb 23, 2006•0 citations

Concatenated Quantum Codes Can Attain the Quantum Gilbert–Varshamov Bound

Yingkai Ouyang

A family of quantum codes of increasing block length with positive rate is asymptotically good if the ratio of its distance to its block length approaches a positive constant. The asymptotic quantum Gilbert-Varshamov (GV) bound states that there exist q -ary quantum codes of sufficiently long block length N having fixed rate R with distance at least NH-1((1-R)/2), where Hq2is the q2-ary entropy function. For q<;7 , only random quantum codes are known to asymptotically attain the quantum GV bound. However, random codes have little structure. In this paper, we generalize the classical result of Thommesen to the quantum case, thereby demonstrating the existence of concatenated quantum codes that can asymptotically attain the quantum GV bound. The outer codes are quantum generalized Reed-Solomon codes, and the inner codes are random independently chosen stabilizer codes, where the rates of the inner and outer codes lie in a specified feasible region.

arXiv:1004.1127•IEEE Transactions on Information Theory•Mar 28, 2014•19 citations

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

Decoding concatenated codes using soft information

Venkatesan Guruswami, Madhu Sudan

We present a decoding algorithm for concatenated codes when the outer code is a Reed-Solomon code and the inner code is arbitrary. "Soft" information on the reliability of various symbols is passed by the inner decodings and exploited in the Reed-Solomon decoding. This is the first analysis of such a soft algorithm that works for arbitrary inner codes; prior analyses could only, handle some special inner codes. Crucial to our analysis is a combinatorial result on the coset weight distribution of codes given only its minimum distance. Our result enables us to decode essentially up to the "Johnson radius" of a concatenated code when the outer distance is large (the Johnson radius is the "a priori list decoding radius" of a code as a function of its distance). As a consequence, we are able to present simple and efficient constructions of q-ary linear codes that are list decodable up to a fraction (1 - 1/q - /spl epsiv/) of errors and have rate /spl Omega/(/spl epsiv//sup 6/). Codes that can correct such a large fraction of errors have found numerous complexity-theoretic applications. The previous constructions of linear codes with a similar rate used algebraic-geometric codes and thus suffered from a complicated construction and slow decoding.

IEEE Conference on Computational Complexity (CCC)•Jun 25, 2003•19 citations

List decoding of concatenated codes: improved performance estimates

Alexander Barg, Andrew McGregor

An improved bound is proved on the list-decoding radius of a concatenated code relying upon a combination of (soft-decision) algebraic list decoding and generalized minimum distance (GMD) decoding in the outer level. This bound is further improved if the inner code is a random linear code.

IEEE International Symposium on Information Theory (ISIT)•Dec 23, 2004•0 citations
Constructing codes that attain the Gilbert-Varshamov (GV) bound while admitting efficient encoding and decoding is a fundamental problem in coding theory. We study concatenated codes that reuse a single binary inner code across all outer coordinates. To exploit existing encoding and decoding algorithms, we restrict the outer codes to random subcodes of scaled copies of prescribed algebraic codes and investigate their minimum distance. Our first contribution is a general upper bound on the minimum-distance failure probability that separates two terms controlled by the inner code's bias moments and the dual weight distribution of the prescribed code, together with sufficient conditions for exponential decay. Our second contribution is a concrete construction satisfying these conditions using algebraic-geometric codes from the Garcia-Stichtenoth tower. For every sufficiently small ε>0\varepsilon>0ε>0, we construct a family of random binary codes CmC_mCm​ whose rates approach ε2\varepsilon^2ε2 and satisfy [ \Pr\left[δ(C_m)\geq\frac12-\sqrt{\frac{\ln 2}{2}}\left(\varepsilon+\frac{\varepsilon^3}{2}\right)\right]\geq 1-2^{-c\varepsilon^4N_m}, ] for all sufficiently large mmm, where NmN_mNm​ is the block length and c>0c>0c>0 is independent of ε\varepsilonε and mmm. Thus, the distance guarantee matches the leading coefficient of the GV bound at low rates. For each fixed ε\varepsilonε, the construction uses a single inner encoding map throughout the family and admits polynomial-time encoding and unique decoding within a guaranteed radius. This answers the question of Doron, Mosheiff, and Wootters for subcodes of scaled algebraic geometry codes at low rates.
AbstractA good quantum code corrects for a linear number of errors. It has been shownthat random codes attains the QGVB with a relative distance H −1q 2 ((1−R)/2) wherethe code is q-ary and R is the rate of the code (number of encoded systems / blocklength). However,randomcodeshavelittlestructure. Inthispaper,westudyafamilyofconcatenatedq-arystabilizercodes. Eachoftheinnercodesisarandomrate1q-arystabilizer code of block length n. The outer code is a quantum MDS code with blocklengthq n andalphabetsizeq n ,anarbitraryrateR≤1,anddistanceN(1−R)/2+1thatmeets the Quantum Singleton bound. Fixing the outer code rate and letting n grow,the concatenated stabilizer code has a distance that almost surely attains the QGVB.This partially generalizes Thommesen’s result, where heshowed thatthedistanceof aconcatenated code with a Reed-Solomon outer code and random inner linear codes ofarbitraryrateattainstheGilbert-Varshamovboundalmostsurely. 1 Introduction A family of q-ary quantum codes of increasing block length is defined to be good if the ratioof its distance to its block length approaches a non-zero constant. Designing good quantumcodes is highly nontrivial, just as it is in the classical case. The quantum Gilbert-Varshamovbound (QGVB) is a lower bound on an achievable relative distance of a quantum code ofa fixed rate. Explicit constructions of good quantum codes for q ≤ 7 have been studied[1, 2, 3], but they all fail to satisfy the QGVB. The QGVB bound is attainable for the familyof all random quantum codes [4], the family of random stabilizer codes [5], and the familyof random nondegenerate stabilizer codes [6], and the family of random degenerate stabilizercodes [6]. We show that concatenated quantum codes, with a quantum outer code havinga known structure and being efficiently decodable, and randomly chosen independent innerquantum codes also attains the QGVB. Thus our family of random quantum codes has morestructure than previously studied examples.In this paper, we generalize a special case of Thommesen’s result [7] to the quantumcase. He showed that a code from the family of binary concatenated codes made with a1
In this chapter, we continue the discussion on concatenated codes, which was initiated in Section 5.4. The main message to be conveyed in this chapter is that by using concatenation, one can obtain codes with favorable asymptotic performance—in a sense to be quantified more precisely—while the complexity of constructing these codes and decoding them grows polynomially with the code length. We first present a decoding algorithm for concatenated codes, due to Forney. This algorithm, referred to as a generalized minimum distance (in short, GMD) decoder, corrects any error pattern whose Hamming weight is less than half the product of the minimum distances of the inner and outer codes (we recall that this product is a lower bound on the minimum distance of the respective concatenated code). A GMD decoder consists of a nearest-codeword decoder for the inner code, and a combined error–erasure decoder for the outer code. It then enumerates over a threshold value, marking the output of the inner decoder as erasure if that decoder returns an inner codeword whose Hamming distance from the respective received sub-word equals or exceeds that threshold. We show that under our assumption on the overall Hamming weight of the error word, there is at least one threshold for which the outer decoder recovers the correct codeword. If the outer code is taken as a GRS code, then a GMD decoder has an implementation with time complexity that is at most quadratic in the length of the concatenated code.
A family of quantum codes of increasing block length with positive rate is asymptotically good if the ratio of its distance to its block length approaches a positive constant. The asymptotic quantum Gilbert-Varshamov (GV) bound states that there exist q -ary quantum codes of sufficiently long block length N having fixed rate R with distance at least NH-1((1-R)/2), where Hq2is the q2-ary entropy function. For q<;7 , only random quantum codes are known to asymptotically attain the quantum GV bound. However, random codes have little structure. In this paper, we generalize the classical result of Thommesen to the quantum case, thereby demonstrating the existence of concatenated quantum codes that can asymptotically attain the quantum GV bound. The outer codes are quantum generalized Reed-Solomon codes, and the inner codes are random independently chosen stabilizer codes, where the rates of the inner and outer codes lie in a specified feasible region.
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 present a decoding algorithm for concatenated codes when the outer code is a Reed-Solomon code and the inner code is arbitrary. "Soft" information on the reliability of various symbols is passed by the inner decodings and exploited in the Reed-Solomon decoding. This is the first analysis of such a soft algorithm that works for arbitrary inner codes; prior analyses could only, handle some special inner codes. Crucial to our analysis is a combinatorial result on the coset weight distribution of codes given only its minimum distance. Our result enables us to decode essentially up to the "Johnson radius" of a concatenated code when the outer distance is large (the Johnson radius is the "a priori list decoding radius" of a code as a function of its distance). As a consequence, we are able to present simple and efficient constructions of q-ary linear codes that are list decodable up to a fraction (1 - 1/q - /spl epsiv/) of errors and have rate /spl Omega/(/spl epsiv//sup 6/). Codes that can correct such a large fraction of errors have found numerous complexity-theoretic applications. The previous constructions of linear codes with a similar rate used algebraic-geometric codes and thus suffered from a complicated construction and slow decoding.