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:2610.02648

Random Quantum LDPC Codes Approaching the Gilbert-Varshamov Bound

Tushant Mittal, Shashank Srivastava, Madhur Tulsiani, Mary Wootters

cs.ITquant-phSubmitted Oct 2, 2026• Announced Oct 5, 2026• 2 citations
arXivHTMLPDF

Abstract

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.

AI Summary

The paper asks whether quantum LDPC codes can match the rate–distance tradeoff and channel-coding guarantees of random stabilizer codes, despite the commutation constraints and unavoidable low-weight stabilizers that obstruct direct random-coding arguments. For any prime $p$, fixed rate $R\in(0,1)$, and $\varepsilon>0$, it constructs an ensemble of $p$-ary stabilizer codes with constant check weight $O_{\varepsilon,R}(1)$ and relative distance at least $H_{p^2}^{-1}((1-R)/2)-\varepsilon$, with exponentially high probability. Related guarantees approach erasure-channel capacity $1-2\kappa$ and the hashing rate $1-H(\nu)/\log_2p$ for memoryless Pauli noise. The construction starts from existing asymptotically good QLDPC codes and applies quantum Alon–Edmonds–Luby expander-based distance amplification. The key additional analysis controls degeneracy: near-Singleton outer codes can have at most $|L|^\eta$ stabilizers below a specified distance threshold, for arbitrarily small constant $\eta$. Independent random symplectic encodings within constant-size blocks then produce the ensemble. In the simplest model, every fixed Pauli error is a nontrivial undetectable error with probability at most $p^{-N(1-R-\gamma)}$, enabling union-bound proofs of distance and channel guarantees. The construction relies on existing good QLDPC families rather than providing an independent random construction of them. Check weights and alphabet/block sizes depend on the approximation parameters. Efficient decoding is discussed for a constant fraction of adversarial errors, not up to the GV distance or the stated channel limits; the Pauli-channel proof uses a typical-error decoder without an efficiency guarantee.

Little sign of AI-generated textAI use disclosed
ChatGPT Sol 5.6 was used to assist with checking proofs, generating figures, performing literature searches, and drafting parts of this manuscript.

Error found: The abstract states an ε-only check-weight bound, whereas the proved locality guarantee allows dependence on the target rate R as well as ε.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

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

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

Check-weight-constrained quantum codes: Bounds and examples

Lily Wang, Andy Zeyi Liu, Ray Li +2 more

Quantum low-density parity-check (qLDPC) codes can be implemented by measuring only low-weight checks, making them compatible with noisy quantum hardware and central to the quest to build noise-resilient quantum computers. A fundamental open question is how constraints on check weight limit the achievable parameters of qLDPC codes. Here, we study stabilizer and subsystem codes with constrained check weight, combining analytical arguments with numerical optimization to establish strong upper bounds on their parameters. We show that stabilizer codes with checks of weight at most three cannot have nontrivial distance. We also prove tight tradeoffs between rate and distance for broad families of CSS stabilizer and subsystem codes with checks of weight at most four and two, respectively. Notably, our bounds are applicable to general qLDPC codes, as they rely only on check-weight constraints without assuming geometric locality or special graph connectivity. In the finite-size regime, we derive numerical upper bounds using linear programming techniques and identify explicit code constructions that approach these limits, delineating the landscape of practically relevant qLDPC codes with tens or hundreds of physical qubits.

quant-pharXiv:2601.15446•Jan 23, 2026•14 citations

List Decodable Quantum LDPC Codes

Thiago Bergamaschi, Fernando Granha Jeronimo, Tushant Mittal +2 more

We give a construction of Quantum Low-Density Parity Check (QLDPC) codes with near-optimal rate-distance tradeoff and efficient list decoding up to the Johnson bound in polynomial time. Previous constructions of list decodable good distance quantum codes either required access to a classical side channel or were based on algebraic constructions that preclude the LDPC property. Our construction relies on new algorithmic results for codes obtained via the quantum analog of the distance amplification scheme of Alon, Edmonds, and Luby [FOCS 1995]. These results are based on convex relaxations obtained using the Sum-of-Squares hierarchy, which reduce the problem of list decoding the distance amplified codes to unique decoding the starting base codes. Choosing these base codes to be the recent breakthrough constructions of good QLDPC codes with efficient unique decoders, we get efficiently list decodable QLDPC codes.

arXiv:2411.04306•Nov 6, 2024•5 citations

Quantum Low-Density Parity-Check Codes

Bane V. Vasic, Valentin Savin, Michele Pacenti +2 more

Quantum error correction (QEC) is a cornerstone of quantum computing, enabling reliable information processing in the presence of noise. Sparse stabilizer codes -- referred to generally as quantum low-density parity-check (QLDPC) codes -- have risen to the forefront of QEC research in recent years. This can be attributed to several key factors. First, classical LDPC codes admit low-complexity belief propagation iterative decoding and near-capacity performance, which contributed to the early interest in QLDPC codes. Then, the result promising constant overhead fault tolerance using QLDPC codes led to the search for code families that go beyond the long-holding $\sqrt{n}$ scaling barrier of minimum distance for codelength $n$. This resulted in recent breakthroughs in the construction of QLDPC codes, which, combined with efficient decoding algorithms and the development of fault-tolerant protocols operating on QLDPC-encoded quantum information, provide a promising pathway to low-overhead, fault-tolerant quantum computation. However, despite their potential, challenges remain, particularly in constructing and decoding finite-length codes that account for, or efficiently leverage, specific characteristics of quantum hardware, such as connectivity, topology, native gate sets, and noise models. This article provides an in-depth examination of QLDPC codes and their iterative decoders, catering to an information theory audience with no or limited background in quantum mechanics. We discuss the theoretical underpinnings, explore unique characteristics of quantum channels, and delineate key code constructions and decoding algorithms, ultimately highlighting the impact and future prospects of QLDPC codes in quantum information science.

arXiv:2510.14090•IEEE BITS the Information Theory Magazine•Dec 1, 2025•17 citations

Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time

William Gay, Fernando Granha Jeronimo, Abhi Shukul

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 achieving list decoding capacity while also possessing the important LDPC property. In this work, we provide (to the best of our knowledge) the first explicit constructions of quantum LDPC codes achieving list decoding capacity, namely, with a list decoding radius approaching the quantum Singleton bound with constant list sizes. Furthermore, we provide near-linear time (in the block-length) list decoding algorithms approaching capacity. Our explicit code construction are based on expander graphs via the quantum analogue of Alon-Edmonds-Luby (AEL) amplification [Bergamaschi, Golowich and Gunn, STOC 2024], and this enables the important LDPC property. Our efficient list decoding algorithms are obtained by generalizing the classical expander-based weak-regularity list decoding algorithms [Srivastava and Tulsiani, FOCS 2025] [Jeronimo and Singh, 2025] to suitable instantiations of quantum AEL.

quant-pharXiv:2609.40313•Oct 1, 2026•1 citation
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.
The paper asks whether quantum LDPC codes can match the rate–distance tradeoff and channel-coding guarantees of random stabilizer codes, despite the commutation constraints and unavoidable low-weight stabilizers that obstruct direct random-coding arguments.
For any prime ppp, fixed rate R∈(0,1)R\in(0,1)R∈(0,1), and ε>0\varepsilon>0ε>0, it constructs an ensemble of ppp-ary stabilizer codes with constant check weight Oε,R(1)O_{\varepsilon,R}(1)Oε,R​(1) and relative distance at least Hp2−1((1−R)/2)−εH_{p^2}^{-1}((1-R)/2)-\varepsilonHp2−1​((1−R)/2)−ε, with exponentially high probability. Related guarantees approach erasure-channel capacity 1−2κ1-2\kappa1−2κ and the hashing rate 1−H(ν)/log⁡2p1-H(\nu)/\log_2p1−H(ν)/log2​p for memoryless Pauli noise.
The construction starts from existing asymptotically good QLDPC codes and applies quantum Alon–Edmonds–Luby expander-based distance amplification. The key additional analysis controls degeneracy: near-Singleton outer codes can have at most ∣L∣η|L|^\eta∣L∣η stabilizers below a specified distance threshold, for arbitrarily small constant η\etaη. Independent random symplectic encodings within constant-size blocks then produce the ensemble. In the simplest model, every fixed Pauli error is a nontrivial undetectable error with probability at most p−N(1−R−γ)p^{-N(1-R-\gamma)}p−N(1−R−γ), enabling union-bound proofs of distance and channel guarantees.
The construction relies on existing good QLDPC families rather than providing an independent random construction of them. Check weights and alphabet/block sizes depend on the approximation parameters. Efficient decoding is discussed for a constant fraction of adversarial errors, not up to the GV distance or the stated channel limits; the Pauli-channel proof uses a typical-error decoder without an efficiency guarantee.
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.
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
Quantum low-density parity-check (qLDPC) codes can be implemented by measuring only low-weight checks, making them compatible with noisy quantum hardware and central to the quest to build noise-resilient quantum computers. A fundamental open question is how constraints on check weight limit the achievable parameters of qLDPC codes. Here, we study stabilizer and subsystem codes with constrained check weight, combining analytical arguments with numerical optimization to establish strong upper bounds on their parameters. We show that stabilizer codes with checks of weight at most three cannot have nontrivial distance. We also prove tight tradeoffs between rate and distance for broad families of CSS stabilizer and subsystem codes with checks of weight at most four and two, respectively. Notably, our bounds are applicable to general qLDPC codes, as they rely only on check-weight constraints without assuming geometric locality or special graph connectivity. In the finite-size regime, we derive numerical upper bounds using linear programming techniques and identify explicit code constructions that approach these limits, delineating the landscape of practically relevant qLDPC codes with tens or hundreds of physical qubits.
We give a construction of Quantum Low-Density Parity Check (QLDPC) codes with near-optimal rate-distance tradeoff and efficient list decoding up to the Johnson bound in polynomial time. Previous constructions of list decodable good distance quantum codes either required access to a classical side channel or were based on algebraic constructions that preclude the LDPC property. Our construction relies on new algorithmic results for codes obtained via the quantum analog of the distance amplification scheme of Alon, Edmonds, and Luby [FOCS 1995]. These results are based on convex relaxations obtained using the Sum-of-Squares hierarchy, which reduce the problem of list decoding the distance amplified codes to unique decoding the starting base codes. Choosing these base codes to be the recent breakthrough constructions of good QLDPC codes with efficient unique decoders, we get efficiently list decodable QLDPC codes.
Quantum error correction (QEC) is a cornerstone of quantum computing, enabling reliable information processing in the presence of noise. Sparse stabilizer codes -- referred to generally as quantum low-density parity-check (QLDPC) codes -- have risen to the forefront of QEC research in recent years. This can be attributed to several key factors. First, classical LDPC codes admit low-complexity belief propagation iterative decoding and near-capacity performance, which contributed to the early interest in QLDPC codes. Then, the result promising constant overhead fault tolerance using QLDPC codes led to the search for code families that go beyond the long-holding n\sqrt{n}n​ scaling barrier of minimum distance for codelength nnn. This resulted in recent breakthroughs in the construction of QLDPC codes, which, combined with efficient decoding algorithms and the development of fault-tolerant protocols operating on QLDPC-encoded quantum information, provide a promising pathway to low-overhead, fault-tolerant quantum computation. However, despite their potential, challenges remain, particularly in constructing and decoding finite-length codes that account for, or efficiently leverage, specific characteristics of quantum hardware, such as connectivity, topology, native gate sets, and noise models. This article provides an in-depth examination of QLDPC codes and their iterative decoders, catering to an information theory audience with no or limited background in quantum mechanics. We discuss the theoretical underpinnings, explore unique characteristics of quantum channels, and delineate key code constructions and decoding algorithms, ultimately highlighting the impact and future prospects of QLDPC codes in quantum information science.
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 achieving list decoding capacity while also possessing the important LDPC property. In this work, we provide (to the best of our knowledge) the first explicit constructions of quantum LDPC codes achieving list decoding capacity, namely, with a list decoding radius approaching the quantum Singleton bound with constant list sizes. Furthermore, we provide near-linear time (in the block-length) list decoding algorithms approaching capacity. Our explicit code construction are based on expander graphs via the quantum analogue of Alon-Edmonds-Luby (AEL) amplification [Bergamaschi, Golowich and Gunn, STOC 2024], and this enables the important LDPC property. Our efficient list decoding algorithms are obtained by generalizing the classical expander-based weak-regularity list decoding algorithms [Srivastava and Tulsiani, FOCS 2025] [Jeronimo and Singh, 2025] to suitable instantiations of quantum AEL.