⚛️ quantum physics

Finite-Degree Quantum LDPC Codes Reaching the Gilbert-Varshamov Bound

This paper constructs finite-degree quantum LDPC codes with non-vanishing rates that achieve relative linear distance and, in specific settings, reach the Gilbert-Varshamov bound through a rigorous computer-assisted proof.

Original authors: Kenta Kasai

Published 2026-03-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kenta Kasai

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a secret message across a stormy ocean. The waves (noise) are so violent that they might flip your letters upside down or erase them entirely. To survive, you don't just send the message once; you send it with a massive amount of redundancy—extra bits of information that act like a safety net. If the waves knock out a few letters, the receiver can use the safety net to figure out what the original message was.

In the world of quantum computing, this "safety net" is called a Quantum Error-Correcting Code. But there's a catch: quantum data is incredibly fragile. If the safety net itself is too complex (too many connections between the bits), it becomes hard to manage and prone to its own errors. We need a code that is sparse (simple connections) but powerful (can fix many errors).

This paper by Kenta Kasai is like a master architect presenting a new blueprint for building these safety nets. Here is the story of what they found, explained simply.

1. The Problem: The "Zero-Rate" Trap

For a long time, scientists tried to build these quantum codes by taking two classical codes that were "mirror images" of each other (mathematically, they are "duals").

The Analogy: Imagine you have a lock (Code A) and a key (Code B) that fits it perfectly.
The Trap: If you try to use the lock and the key together to protect a message, they cancel each other out. The amount of actual information you can send (the "rate") drops to zero. It's like building a fortress so thick with walls that no one can get inside to live there. You have a perfect structure, but it's useless for communication.

2. The Solution: The "Nested" House

The author's breakthrough was to stop using the lock and key as direct opposites. Instead, he built a nested structure.

The Analogy: Imagine a house inside a house.
- The Outer House (the MacKay-Neal code) is a sturdy, spacious building.
- The Inner House (the Hsu–Anastasopoulos code) is a smaller, perfectly fitted room inside the outer one.
- Because the inner room is inside the outer house, they don't cancel each other out. They work together.
The Result: This "Nested" design allows the code to have a positive rate. You can actually send information, and the code is still sparse (simple to build).

3. The "Goldilocks" Balance

To make this work, the author had to find a very specific set of numbers for how the "rooms" connect.

The Analogy: Think of it like baking a cake. If you add too much flour (too many connections), the cake is dense and hard to eat. Too little flour, and it falls apart.
The author found a "Goldilocks" zone where the connections are just right. He proved that for specific, small sets of numbers (which he calls "balanced triples"), this cake doesn't just taste good; it's perfect.

4. The Big Discovery: Hitting the "Theoretical Limit"

In coding theory, there is a famous theoretical ceiling called the Gilbert–Varshamov (GV) Bound.

The Analogy: Imagine a mountain peak. For decades, scientists were climbing up the mountain, getting closer and closer to the top, but they could never quite prove they had reached the very summit. They knew the peak existed, but they couldn't point to a specific spot and say, "We are here."
The Paper's Achievement: Kenta Kasai didn't just climb higher; he proved that for several specific, small designs, his codes actually reach the summit.
- He used a "computer-assisted proof" (like a super-precise GPS) to verify that these specific small designs hit the theoretical maximum efficiency.
- This means these codes are as good as mathematically possible for their size. They are the "perfect" safety nets.

5. Why This Matters

Simplicity: Unlike previous "perfect" codes that required massive, complex structures (like giant skyscrapers), these new codes work with small, finite degrees. They are like efficient, modular homes rather than sprawling mega-cities.
Reliability: The paper proves that these codes have a "linear distance."
- The Analogy: If you have a code with linear distance, it means that to break the code, an attacker (or a wave) has to smash a number of bits proportional to the total size of the message. It's not enough to just poke a few holes; you have to destroy the whole thing to break it.
The Future: While the paper doesn't yet solve how to decode (read) these messages quickly in real-time, it provides the blueprint for the perfect structure. It's like finding the perfect engine design; now engineers just need to figure out how to build the transmission to make it run smoothly.

Summary

Kenta Kasai took two existing types of mathematical codes, stopped trying to make them mirror images, and instead nested one inside the other. He proved that for specific, small configurations, this new "Nested" code is perfectly efficient, reaching the absolute theoretical limit of how much error protection you can get for a given amount of data. It's a major step toward building the reliable, fault-tolerant quantum computers of the future.

1. Problem Statement

The paper addresses the construction of Quantum Low-Density Parity-Check (QLDPC) codes, specifically within the Calderbank–Shor–Steane (CSS) framework. The primary challenges in this field are:

Asymptotic Goodness: Achieving a non-vanishing coding rate ( $R > 0$ ) and a linear minimum distance ( $d = \Theta(n)$ ) simultaneously.
Finite-Degree Constraints: Most recent breakthroughs (e.g., Panteleev–Kalachev, Dinur et al., Leverrier–Zémor) achieve asymptotic goodness but often rely on complex constructions or high degrees. There is a need for codes with bounded (fixed) degrees that are explicitly good.
The Gilbert–Varshamov (GV) Bound: While asymptotic existence of good CSS codes is known, proving that specific, finite-degree ensembles achieve the GV bound (the theoretical limit for random linear codes) has been difficult.
Dual Pairing Issue: A naive CSS construction using a code $C$ and its dual $C^\perp$ results in a quantum rate of zero ( $R_Q = R + (1-R) - 1 = 0$ ). Constructing a CSS pair with a positive quantum rate requires a nested structure ( $C_Z^\perp \subseteq C_X$ ) rather than a direct dual pair, which complicates the distance analysis.

2. Methodology

The author proposes a construction based on nested regular sparse LDPC matrices derived from two classical code families:

Hsu–Anastasopoulos (HA) Codes: Used for the $Z$ -side code ( $C_Z$ ).
MacKay–Neal (MN) Codes: Used for the $X$ -side code ( $C_X$ ).

Key Construction Steps:

Nested Structure: Instead of using a direct dual pair, the author defines $C_X$ using a stacked matrix $A_X = \begin{bmatrix} A_Z \\ A_\Delta \end{bmatrix}$ , where $A_Z$ is the parity-check matrix for the HA code and $A_\Delta$ is an independent regular LDPC matrix. This ensures $Row(A_Z) \subseteq Row(A_X)$ , satisfying the CSS condition $C_Z^\perp \subseteq C_X$ .
Socket-Based Configuration Model: The matrices are sampled from a socket-based random graph ensemble (configuration model). This allows for exact enumerator analysis and density evolution, differing from the Gallager ensembles used in prior HA analyses.
Hidden Variable Representation: The construction introduces "hidden variables" to define extended parity-check matrices ( $H'_Z, H'_X$ ). The actual codes are obtained by puncturing these hidden variables. This representation simplifies the proof of the CSS condition and the dimension formulas.
Balanced Condition: The paper focuses on "balanced triples" $(j_Z, j_X, k)$ where the classical design rates of the constituent codes match ( $R_{des}^Z = R_{des}^X$ ), ensuring a positive quantum design rate $R_{des}^Q = 1 - 2\alpha_Z > 0$ .

Analytical Approach:

Weight Enumerator Analysis: The author performs a rigorous first-moment analysis (union bound) on the weight distributions of the codes.
HA Side: Adapts the analysis from [9] but replaces the outer code ensemble with the socket-based model.
MN Side: Develops a novel stacked refined enumerator because $A_X$ $A_{X}$ is a stacked object, not a standard regular ensemble. This involves:
- Blockwise complement symmetry (for even degrees).
- Trial-point bounds for the linear-weight regime.
- Pairing bounds for the low-weight regime.
Computer-Assisted Proof: For specific finite-degree triples, the author uses rigorous interval arithmetic and adaptive subdivision to verify that the exponent of the weight enumerator is strictly negative, proving the GV bound is met at finite degrees.

3. Key Contributions

New CSS Construction: A balanced nested CSS family constructed entirely from regular LDPC matrices ( $A_Z, A_\Delta, B$ ) that maintains bounded graphical complexity and a positive quantum rate.
Fixed-Degree Linear Distance: Proof that for fixed even balanced triples satisfying $4 \le j_Z < k/2$ , both constituent classical codes have linear minimum distance with high probability.
Finite-Degree GV Attainment: The paper provides the first rigorous proof that specific finite-degree triples achieve the classical Gilbert–Varshamov bound.
- Seven specific triples (e.g., $(4, 6, 10), (4, 8, 12), \dots$ ) are identified where the distance meets the GV bound.
- Consequently, the nested CSS pair achieves the CSS Gilbert–Varshamov distance at finite degrees.
Rate Convergence: Proof that the actual coding rates of the finite-length codes converge in probability to the design rates as $n \to \infty$ .
Decoding Insight: While the compressed parity-check matrices are dense, the paper shows that syndrome decoding can be represented as sparse affine systems using the extended matrices, suggesting a path toward belief-propagation (BP) implementation, though a direct efficient decoder is not yet proposed.

4. Main Results

Theorem 3.1 & 4.1: For fixed even balanced triples, the nested CSS pair has relative linear distance with high probability.
Theorem 3.2 & 4.2: For seven specific balanced triples in the search window ( $k \le 30, j_Z \le 10$ ), the classical constituent codes attain the GV distance at finite degrees.
Corollary 5.2: These same triples attain the CSS Gilbert–Varshamov distance.
Numerical Evidence: Figure 5 in the paper shows that for $j_Z \ge 4$ , the numerical proxies for the minimum distance lie on or very near the GV curve, leading to Conjecture 6.1: All balanced triples with $j_Z \ge 4$ attain the finite-degree GV bound.

5. Significance

Bridging Theory and Practice: The work moves beyond asymptotic existence proofs to provide explicit, finite-degree parameters that are provably optimal (GV-achieving). This is crucial for practical quantum error correction where block lengths and degrees are constrained.
Simplicity of Construction: Unlike previous asymptotically good QLDPC constructions that rely on complex hypergraph products or Cayley complexes, this construction uses standard regular LDPC matrices with a simple nested structure.
Girth Potential: Because the blocks $A_Z, A_\Delta, B$ are chosen independently, the construction retains the flexibility to enforce large girth (cycle-free properties) in the Tanner graphs, which is known to improve decoding performance but is often sacrificed in other QLDPC constructions.
Foundation for Decoding: By establishing that the underlying structure admits sparse affine representations, the paper lays the groundwork for developing efficient BP decoders for these codes, potentially via spatial coupling (a direction suggested in the conclusion).

In summary, Kasai demonstrates that by carefully nesting regular LDPC codes, one can construct quantum codes that are not only asymptotically good but also achieve the fundamental GV bound at finite, low degrees, offering a promising path toward practical, high-performance quantum error correction.