PaperlayerView exact revision on arXiv

Source-linked AI summary

Random Quantum LDPC Codes Approaching the Gilbert-Varshamov Bound

Tushant Mittal, Shashank Srivastava, Madhur Tulsiani, Mary Wootters

arXiv:2610.02648v1cs.ITmath.ITquant-ph

TL;DR

QLDPC codes are challenging to construct and analyze because sparsity conflicts with stabilizer commutation constraints. The paper combines low-degeneracy QLDPC codes with random concatenation to obtain near-GV distance and random-stabilizer channel rates with bounded-weight checks.

  • Problem

    QLDPC sparsity makes random-code constructions difficult because uniformly random sparse matrices do not satisfy the stabilizer commutation constraint, and the lack of a QLDPC ensemble limits analysis of their capabilities.

    Source: §1 · p. 3

  • Method

    The construction uses low-degeneracy QLDPC codes as outer codes and random concatenation to make fixed-error bounds resemble those for random stabilizer codes.

    Source: §1.1 · p. 9, §3 · p. 12

  • Results

    With exception probability 2^-Ωε(n), the ensemble reaches distance d ≥ (δGV(p, R) − ε)·n; on erasure and memoryless Pauli channels, random codes achieve rate R(Q) − ε.

    Source: §1 · p. 4

  • Takeaways & Limitations

    The ensemble supplies a probabilistic construction of QLDPC codes that matches random-stabilizer performance on distance and the stated channel-rate benchmarks.

    Source: §1 · p. 4

    Entanglement fidelity need not lower-bound worst-case pure-state fidelity, so the channel guarantee does not itself establish that worst-case fidelity.

    Source: §3.1 · p. 16

Abstract

from arXiv · show

We show that for any $R,\epsilon >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_\epsilon(1)$, and normalized distance at least $\delta_{\mathrm{GV}}(p,R)-\epsilon$. Here, $\delta_{\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.

1 Introduction

The paper constructs random QLDPC ensembles approaching the quantum GV bound and matching random stabilizer performance on erasure and memoryless Pauli channels through AEL distance amplification and random local concatenation. It analyzes these concatenations using low-degeneracy bounds for the AEL code and collision-probability control from the randomness.

1 Introduction

  • Except with probability 2^-Ωε(n), the ensemble gives p-ary QLDPC codes with checks of weight Oε,R(1) and distance at least (δ_GV(p,R) − ε)n.This holds for each sufficiently large n, prime p ≥ 2, and rate R ∈ (0, 1).Source: §1 · p. 4
  • The ensemble starts from an AEL-amplified QLDPC outer code and concatenates each coordinate with an independent random inner code, combining LDPC structure with random-stabilizer-like behavior.The construction is described as a quantum analogue of Thommesen’s construction; the paper presents it as the first QLDPC ensemble whose random codes achieve the GV bound.Source: §1 · p. 4
  • For erasure and memoryless Pauli channels, random codes from the QLDPC ensemble achieve rate R(Q) − ε, matching the random-stabilizer rate bounds up to ε.The channel results cover the erasure channel and any memoryless Pauli channel.Source: §1 · p. 4

1.1 Techniques

  • AEL uses an expander-based shuffle and fold to amplify distance while preserving LDPC structure and producing a constant-sized alphabet outer code approaching the quantum Singleton bound.Starting from existing good QLDPC codes, the resulting outer code is then used in the random concatenation; no new proof of asymptotically good QLDPC existence is needed.Source: §1.1 · pp. 6, 8
  • Quantum LDPC distance alone cannot support the usual concatenation union bound: distinct codewords may differ by low-weight stabilizers, so the analysis must control degeneracy.Unlike pure quantum Reed-Solomon codes, QLDPC stabilizer spaces contain low-weight vectors, potentially inflating the count by a factor of |L|.Source: §1.1 · p. 7
  • AEL provides η-degenerate QLDPC codes approaching the quantum Singleton bound, controlling the low-weight stabilizers that complicate distance-based counting.The construction gives rate R and distance at least (1 − R − ε)n/2; η-degeneracy limits the counting overhead from stabilizers to |L|^η.Source: §1.1 · pp. 7–8
  • The AEL code is η-degenerate for sufficiently small γ > 0.Source: §1.1 · p. 9
  • Low degeneracy and random concatenation together yield essentially the same fixed-error bound as for a random stabilizer code.The bound is the key input for the paper’s main results.Source: §1.1 · p. 9

2 Preliminaries

Section 2 establishes the linear-algebraic model for stabilizer codes and defines concatenation and the random model built from it.

2.1 Linear-Algebraic Formulation

  • Pauli operators commute exactly when their labels have zero trace-symplectic product, which becomes the standard symplectic form over F_p under the stated identification.The paper suppresses scalar phases because they affect neither commutation nor code parameters.Source: §2.1 · pp. 9–10
  • Stabilizer codes correspond to isotropic subspaces up to phase choice; the subspace dimension determines code parameters, and bounded-weight basis checks define QLDPC codes.A basis weight bounded independently of n is required for the QLDPC condition.Source: §2.1 · p. 10

2.2 Concatenation

  • Concatenation encodes each large-alphabet outer coordinate with a p-ary inner code, forming L_con = L_inn ⊕ Φ(L_out).The inner stabilizers define the product of inner codes, while Φ maps outer stabilizers to act on the inner codespaces.Source: §2.2 · p. 11
  • The concatenated subspace is isotropic and defines an [[n n_inn, m k, d]]_p stabilizer code.The proposition also gives a distance characterization, but its formula is not included in the supplied passage.Source: §2.2 · p. 11
  • Both random models use a “nice” outer stabilizer code and randomly chosen Φ and L_inn, as a quantum version of Thommesen’s construction.The outer code is over q = p^m, with vectors represented in coordinate blocks.Source: §2.2 · p. 11

3 Random Model 1: Trivial Inner Codes

This section analyzes randomly concatenated codes with trivial inner codes, using quantitative control of outer-code degeneracy to bound low-weight logical codewords. It shows the ensemble approaches the quantum GV bound and performs well on erasure and Pauli channels, and extends the Pauli-channel decoding bound to general memoryless channels using random channel-and-syndrome pairs and recovery maps.

3 Random Model 1: Trivial Inner Codes

  • d ≥ (δGV − ε(γ))·N with probability at least 1 − exp(−Ωγ(N)); the ensemble has rate R and checks of weight Oγ(1).Theorem 3.1 gives blocklength N for sufficiently large N, and the GV guarantee follows as a corollary.Source: §3 · p. 12
  • η-degeneracy controls low-weight stabilizers, enabling bounds on outer-code weight distributions that yield the random ensemble’s distance guarantee.The proof bounds the probability that a fixed vector is a non-trivial codeword using the outer code’s weight distribution; the needed outer codes are constructed in Section 5.Source: §3 · pp. 12–14
  • The ensemble is γ-close to random stabilizer codes under a pointwise bound and retains QLDPC checks whose weights depend only on γ.The authors use this pointwise comparison to motivate performance guarantees on standard quantum channels.Source: §3 · p. 14

3.1 Performance on Quantum Channels

  • 1 − 2κ − ε is an achievable rate for Oε(1)-QLDPC codes correcting erasures with probability κ < 1/2, with decoding error exp(−Ωε(n)).The stated corollary guarantees existence of such a code for every sufficiently large N.Source: §3.1 · p. 14
  • R ≤ 1 − H2(ν)/log2(p) − ε permits decoding over the memoryless Pauli channel with distribution ν, with error exp(−Ω(N)) for a random ensemble code with probability 1 − exp(−Ω(N)).The argument decodes using representatives from a typical error set and bounds atypical errors by concentration.Source: §3.1 · p. 15
  • For general memoryless channels, the section reduces entanglement-fidelity analysis to the channel’s Pauli part using shifted codes and recovery maps, following Hamada.The stated fidelity guarantee concerns average entanglement fidelity, not worst-case pure-state fidelity.Source: §3.1 · pp. 16–17
  • For R < 1 − H_p(P_N), random (Φ,s) pairs have recovery maps satisfying the corollary’s guarantee with probability 1−exp(−Ω(n)).The proof applies the Pauli-channel bound, whose expected decoding error over Φ is exp(−Ω(N)); Markov’s inequality then gives, for each Φ with small Pauli decoding error, a syndrome s with entanglement fidelity close to 1.Source: §3.1 · p. 18

4 Random Model 2: General Inner Codes

The section analyzes random inner-code concatenation, showing that suitable low-degeneracy outer codes yield codes approaching the GV bound. It also describes distance-based decoding guarantees and applications to purity testing.

4 Random Model 2: General Inner Codes

  • The general model chooses each inner code as a uniformly random isotropic subspace and its encoding map uniformly among symplectic isomorphisms.The distance analysis bounds the probability that an outer logical vector maps into a low-weight coset, then takes a union bound.Source: §4 · pp. 18–19
  • With probability 1 − exp(−Ωε(n)), random inner-code concatenation reaches rate rR and relative distance at least δGV(rR) − ε under the theorem’s outer-code conditions.The outer code must satisfy the stated rate and degeneracy assumptions in Theorem 4.5.Source: §4 · p. 20

4.1 Decoding

  • A product of outer- and inner-code distances gives a worst-case distance lower bound for every concatenated code, certifiable from the component distances.Unlike the GV-distance guarantee, this product bound holds for every code in the ensemble.Source: §4.1 · p. 22
  • The codes’ certifiable distance lower bound supports correction of a constant fraction of errors, unlike usual random stabilizer codes.The decoder runtime is bounded by the outer decoder’s runtime plus O(n n_inn).Source: §4.1 · p. 22
  • Larger-distance inner codes allow larger decoding radii, and the concatenated decoder combines inner coset selection with the outer-code decoder.The general inner-code model supports this larger-radius design compared with trivial inner codes.Source: §4.1 · p. 23

4.1.1 Purity Testing and Authentication

  • The construction also yields Oγ(1)-QLDPC purity-testing codes, each with a polynomial-time decoding algorithm.The cited earlier constructions are not LDPC, and efficient decoding was not known for them.Source: §4.1.1 · p. 23

5 Low-Degeneracy QLDPC Outer Codes from AEL

The section constructs low-degeneracy QLDPC outer codes using AEL distance amplification, then selects parameters and concatenates with random inner codes. This yields a random QLDPC ensemble approaching the stabilizer GV bound while keeping locality independent of blocklength.

5 Low-Degeneracy QLDPC Outer Codes from AEL

  • Asymptotically good η-degenerate codes must have check weight Ω(1/η), so check weights cannot remain independent of the degeneracy parameter.The construction instead uses check weights polynomially large in 1/η, with η fixed as a constant for its purposes.Source: §5 · p. 24
  • For fixed prime p, rate R, and η, ε, the construction gives η-degenerate stabilizer codes with check weight at most 1/(η · ε)^O(1) and distance at least 1 − R − ε.The existence statement holds for all sufficiently large blocklengths.Source: §5 · p. 24

5.1 The AEL Code

  • The AEL construction concatenates a base code with local codes, then folds the result according to a bipartite expander; its distance depends on both codes and the expander quality.The graph amplification technique is due to Alon, Edmonds, and Luby.Source: §5.1 · p. 24, §5 · p. 24

5.2 Parameter Selection and Locality

  • The parameter selection uses a pure quantum Reed–Solomon CSS code as the local code, and the resulting AEL code remains QLDPC when its defining parameters are constant.The local code’s purity supports the low-weight stabilizer bound used to establish degeneracy control.Source: §5.2 · pp. 26–27
  • The constructed p-ary QLDPC ensemble has rate ρ and blocklength-independent locality, and a random member approaches the stabilizer GV bound with high probability.The theorem gives probability 1 − exp(−Ω(n)); its displayed distance threshold is incomplete in the supplied passage.Source: §5.2 · p. 27
  • The outer codes can be efficiently decoded using the base code’s decoder, and the construction then uses them to obtain efficiently decodable random QLDPC codes approaching the GV bound.The cited decoder result is attributed to [LZ23] and.Source: §5.2 · p. 28

Statement of AI use

The authors report using ChatGPT Sol 5.6 for several manuscript-support tasks. They state that all mathematical ideas are theirs and that they wrote and verified the claims and proofs.

Statement of AI use

  • ChatGPT Sol 5.6 assisted with proof checking, figure generation, literature searches, and drafting parts of the manuscript.Source: Statement of AI use · p. 28
  • The application to entanglement fidelity for general memoryless channels and its connection to Hamada’s paper were pointed out by ChatGPT.Source: Statement of AI use · p. 28
  • The authors state that they supplied all mathematical ideas and wrote and verified the manuscript’s claims and proofs.Source: Statement of AI use · p. 28
Loading 2610.02648v1…