⚛️ quantum physics

High-Girth Regular Quantum LDPC Codes from Affine-Coset Structures

This paper presents a construction of high-girth regular quantum LDPC codes using affine-coset structures and circulant permutation lifts, resulting in a $[[16384, 4142, \leq 40]]$ code that achieves a frame error rate of approximately $10^{-8}$ at a depolarizing error rate of 0.085.

Original authors: Koki Okada, Kenta Kasai

Published 2026-04-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Koki Okada, 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 very noisy, stormy ocean. To protect your message, you wrap it in a giant, intricate safety net. This net is made of strings (checks) that hold the message (data) together. If a wave (an error) hits the net, the strings tug in specific ways, telling you exactly where the wave hit so you can fix it.

This paper is about building a super-strong, high-tech safety net for quantum computers. Here is the story of how the authors built it, explained without the heavy math.

1. The Problem: The "Perfect" Net is Hard to Find

In the world of error correction, we want a net that is:

Sparse: Not too many strings, so it's light and fast to check.
Regular: Every knot holds the same number of strings (no weak spots).
Loop-Free (High Girth): The net shouldn't have small, tight loops. Small loops are like "echo chambers" where confusion spreads quickly, making it hard to figure out what went wrong.
Quantum-Safe: In quantum land, there's a weird rule: the "X" strings and "Z" strings (two different types of safety checks) must be perfectly orthogonal (like the X and Y axes on a graph). They can't interfere with each other, or the whole net collapses.

The authors wanted to build a net that is perfectly regular, has no small loops, and follows the quantum rules, all while being a specific, manageable size (512 units).

2. The Blueprint: The "Affine Coset" City

To build this, the authors didn't just draw lines randomly. They used a mathematical city plan called Affine Cosets.

The City: Imagine a 9-dimensional city where every house is a "qubit" (a quantum bit). There are 512 houses in this city.
The Neighborhoods: They divided the city into three big districts (A, B, and C).
The Checks:
- The X-checks are like "neighborhood patrols" that look at every house in District A, then every house in District B, then every house in District C.
- The Z-checks are a different set of patrols that look at the city from a different angle (Districts D1, D2, D3), which are cleverly mixed versions of the first three.

The Magic Trick: Because of how they built these districts, any two patrols from the X-team and any two from the Z-team only ever cross paths at exactly two houses (or zero). They never cross at just one house or three. This specific "two-house meeting" rule is the secret sauce that guarantees the quantum orthogonality rule is followed automatically.

3. The Expansion: The "Circulant" Multiplier

The blueprint above is for a small city of 512 houses. But the authors wanted a bigger net for a real experiment.

They used a technique called a CPM Lift (Circulant Permutation Matrix). Think of this like taking a small, perfect tile pattern and tiling a massive floor with it.

They took their small 512-house blueprint.
They decided to "lift" it by a factor of 32.
The Result: Instead of 512 houses, they now have 16,384 houses (512 × 32).
The Cool Part: Because they used a specific "shifting" rule (like sliding a pattern over and over), the new giant net kept all the good properties of the small one: it's still regular, it still has no small loops, and it still obeys the quantum rules.

4. The Test: The Stormy Ocean

They put this giant net to the test in a simulation of a "Code-Capacity Depolarizing Model."

The Scenario: Imagine throwing random waves (errors) at the net.
The Decoder: This is the "rescue team." They use a method called Belief Propagation (a smart guessing game) to figure out where the errors are.
The Post-Processing: Sometimes the guessing game gets stuck. So, the rescue team has a "Plan B." They look at the most confused parts of the net and try to fix them manually, checking if their fix actually solves the problem without breaking the quantum rules.

5. The Results: A Victory Lap

The Performance: At a noise level of 8.5% (which is quite stormy), their net managed to keep the message safe with an error rate of about 1 in 100 million ( $10^{-8}$ ). That is incredibly reliable.
The Distance: In coding terms, "distance" is how many waves the net can survive before the message is lost. They found a specific error pattern that broke the net with 40 waves. This means the net is at least strong enough to handle 39 waves, but maybe not 40. So, they report the strength as $\le 40$ .
The Comparison: They compared their custom-built net to a "random" net. Surprisingly, their carefully designed, structured net performed almost as well as a completely random one, proving that their specific "city plan" is excellent.

The Big Picture

This paper is a "proof of concept" for a specific type of quantum net.

They designed a perfect small blueprint using geometry.
They scaled it up using a clever tiling trick.
They tested it and showed it works incredibly well against noise.

It's like showing that a specific type of bridge design, when built to a certain size, can withstand a hurricane. While they haven't built the bridge for the whole world yet, they've proven the design works, and now engineers know exactly how to build bigger, better bridges in the future.

1. Problem Statement

The paper addresses the challenge of constructing finite-length, high-girth, regular Quantum Low-Density Parity-Check (QLDPC) codes that satisfy the strict Calderbank–Shor–Steane (CSS) orthogonality condition.

The Trade-off: Classical LDPC codes benefit from sparse, regular parity-check matrices with large girth (to avoid short cycles that degrade iterative decoding). However, constructing quantum CSS codes requires two binary check matrices ( $H_X$ and $H_Z$ ) that are not only sparse and high-girth but also mutually orthogonal ( $H_X H_Z^T = 0$ ).
The Gap: While asymptotic constructions (like hypergraph products) exist, explicit finite-length constructions that maintain high girth (specifically girth 8) and regularity without sacrificing the CSS orthogonality constraint are difficult to design. Existing methods often rely on random ensembles or complex product constructions that do not easily yield specific, reproducible finite-length parameters.
Goal: The authors aim to provide a completely explicit, fixed-length (512 qubits) base construction with girth 8 and $(3, 8)$ -regularity, and then lift it to a larger code to verify its decoding performance and distance properties.

2. Methodology

The methodology consists of three main stages: Base Construction, Lifting, and Decoding/Verification.

A. Base Matrix Construction (Affine-Coset Structure)

The authors construct a base pair of matrices $(H_X^{base}, H_Z^{base})$ of size $192 \times 512$ using linear algebra over the finite field $\mathbb{F}_2$ .

Vector Space: Let $V = \mathbb{F}_2^9$ . The block length is $n = |V| = 2^9 = 512$ .
Subspace Decomposition: $V$ is decomposed into a direct sum of three 3-dimensional subspaces: $V = A \oplus B \oplus C$ .
Dual Decomposition: Three new subspaces $D_1, D_2, D_3$ are defined by mixing basis vectors from $A, B, C$ (e.g., $D_1 = \langle a_1, b_1, c_1 \rangle$ ).
Matrix Definition:
- $H_X^{base}$ : Rows correspond to all affine cosets of subspaces $A, B,$ and $C$ .
- $H_Z^{base}$ : Rows correspond to all affine cosets of subspaces $D_1, D_2,$ and $D_3$ .
Properties:
- Regularity: Every row has weight $2^3 = 8$ (since cosets of 3D subspaces have 8 points). Every column has weight 3 (each point belongs to exactly one coset in each family).
- Orthogonality: The intersection of any coset from the $X$ -family and any coset from the $Z$ -family is either empty or a 1-dimensional affine subspace (size 2). Since $2 \equiv 0 \pmod 2$ , the inner product of any row pair is zero, satisfying the CSS condition.
- Girth: The authors prove that the Tanner graphs contain no 4-cycles or 6-cycles. The girth is exactly 8.

B. Circulant Permutation Matrix (CPM) Lift

To increase the code length while preserving the structural properties, the authors apply a CPM lift with a lift factor $P$ .

Mechanism: Each non-zero entry '1' in the base matrices is replaced by a $P \times P$ Circulant Permutation Matrix (CPM) $I_P(t)$ , where $t$ is a shift label.
Orthogonality Constraint: To maintain $H_X H_Z^T = 0$ in the lifted code, the shift labels must satisfy a local congruence condition. Since the base intersection of any $X$ -row and $Z$ -row contains exactly two points ( $v_1, v_2$ ), the shifts $x_{r, v}$ and $z_{s, v}$ must satisfy:
$x_{r, v_1} - z_{s, v_1} \equiv x_{r, v_2} - z_{s, v_2} \pmod P$
Resulting Code: For $P=32$ , the code length becomes $n = 512 \times 32 = 16,384$ .

C. Decoding Algorithm

The authors employ a Belief Propagation (BP) decoder enhanced with post-processing:

Standard BP: Iterative decoding is run first.
Post-Processing (OSD-based): If BP fails (residual syndrome remains), the decoder attempts to repair the error using Ordered Statistics Decoding (OSD) principles adapted for quantum codes.
- It identifies low-reliability qubits based on BP messages.
- It solves linear systems over small candidate sets ( $K_m$ ) to find corrections that satisfy the residual syndrome.
- It includes specific steps for "Local OSD" and "Restricted-candidate fallback" to handle localized errors without exploding computational complexity.
- Crucial Check: The decoder verifies if the difference between the estimated error and the true error is a stabilizer (logical equivalence).

3. Key Contributions

Explicit Finite-Length Construction: The paper provides a fully explicit, reproducible construction of a $(3, 8)$ -regular CSS base matrix pair with girth 8 and length 512. This is a significant departure from asymptotic or random ensemble approaches.
Affine-Coset Framework: The use of affine cosets of subspaces in $\mathbb{F}_2^9$ provides a rigorous geometric proof of orthogonality and girth properties, avoiding the need for heuristic searches.
High-Girth Preservation: The construction guarantees a girth of 8 in the base, which is preserved in the lifted code, ensuring the absence of short cycles that typically cause error floors in LDPC decoding.
Decoder-Derived Distance Bound: The authors report a specific upper bound on the code distance derived from a decoding failure event, rather than relying solely on theoretical bounds.

4. Results

Code Parameters:
- Base Code: $[[512, 174, 8]]$ (Rate $\approx 0.34$ ).
- Lifted Code ( $P=32$ ): $[[16384, 4142, \le 40]]$ $[[16384, 4142, \leq 40]]$ .
  - Physical qubits: 16,384.
  - Logical qubits: 4,142.
  - Design rate: $1/4$ .
  - Stabilizer weight: 8.
Decoding Performance:
- Model: Code-capacity depolarizing model (perfect syndrome extraction).
- Performance: At a physical error probability $p = 0.085$ , the Frame Error Rate (FER) achieved is approximately $10^{-8}$ .
- Comparison: The performance curve is close to the Density Evolution (DE) threshold ( $p \approx 0.1009$ ) of a random $(3, 8)$ -regular ensemble, despite the strict CSS orthogonality constraints. This suggests the CPM lift provides sufficient "randomness" to mimic random ensembles.
Distance Bound:
- During simulation, a specific logical residual of weight 40 was observed that satisfied the syndrome but was not a stabilizer.
- This provides a confirmed upper bound: $d \le 40$ .
- The authors note this is an observed bound, not a proof of the exact distance.

5. Significance

Bridging Theory and Practice: The paper demonstrates that high-girth, regular quantum LDPC codes can be constructed explicitly for finite lengths, moving beyond asymptotic existence proofs.
Validation of CPM Lifts: It shows that CPM lifts, when constrained by the local congruence condition derived from the base geometry, can effectively preserve the desirable properties of the base code (regularity, girth, orthogonality) while scaling to practical block lengths.
Decoder Insights: The results highlight that even with a fixed, structured base, the decoder performance approaches that of random ensembles. This implies that the "randomness" introduced by the CPM shifts is sufficient to break the correlations that usually plague structured codes.
Future Direction: The work sets a baseline for analyzing distance growth in lifted codes. The observed $d \le 40$ for $n=16384$ suggests the distance scaling is sub-linear, prompting future work on better distance analysis and more advanced post-processing to close the gap between observed and theoretical distances.

In summary, this paper presents a rigorous, geometric construction of a high-performance quantum LDPC code family, validating its finite-length properties through explicit decoding experiments and providing a concrete benchmark for future quantum error correction research.