A Two-Branch Finite-Field Construction for Regular CSS LDPC Bases

This paper introduces a two-branch finite-field construction for regular CSS LDPC quantum codes that decouples base matrix design from cyclic lifting to satisfy orthogonality and girth constraints, demonstrating through a specific (3,10)-regular example that the resulting [[10240,4108]] code achieves a frame error rate of $1.0\times10^{-7}$ at a depolarizing probability of 0.058 using joint belief propagation with low-complexity post-processing.

The Gist

Imagine you are building a massive, ultra-secure vault to protect digital information. In the world of quantum computing, this vault is called a Quantum Error-Correcting Code. Its job is to stop "noise" (like static on a radio) from scrambling the data inside.

This paper presents a new, highly organized blueprint for building the locks and keys (mathematical structures) for these vaults. The authors, Koki Okada and Kenta Kasai, propose a method to design these locks so they are strong, efficient, and don't have hidden weak spots.

Here is the breakdown of their work using simple analogies:

1. The Problem: The "Tangled Web"

Think of a quantum code as a giant web of strings connecting nodes.

• The Goal: You want the web to be sparse (not too many strings) so it's easy to check, but strong enough to catch errors.
• The Catch: In the quantum world, the web has two layers (X and Z) that must fit together perfectly without tangling. If they tangle, the vault breaks.
• The Weak Spots: If the web has small loops (like a tiny circle of 4 strings), errors can hide inside them, confusing the repair crew. The authors wanted to build a web with no tiny loops and no tangles.

2. The Solution: The "Two-Branch Factory"

The authors invented a "factory" to build these webs using a specific mathematical recipe called a Two-Branch Finite-Field Construction.

• The Blueprint (The Base): First, they design a small, perfect "master pattern" (the base matrix). They use a mathematical tool called a Finite Field (think of it as a specialized, limited alphabet of numbers) to arrange the strings.

  • They split the work into two branches (Branch 0 and Branch 1).
  • Branch 0 and Branch 1 are like two teams of architects. They work together to ensure the two layers of the web (X and Z) fit perfectly without tangling (this is called CSS Orthogonality).
  • They also ensure that no small loops (4-cycles) are formed within a single team's work.

• The Expansion (The Lift): The master pattern is too small to be a real vault. So, they use a Cyclic Lift.

  • Imagine taking your small master pattern and photocopying it 64 times, then stitching them together in a specific, randomized way.
  • This creates a massive vault (10,240 bits long) from the small blueprint.
  • The authors carefully chose how to stitch these copies so that no new small loops (6-cycles) accidentally form during the expansion.

3. The "Security Check" (Certification)

Before declaring the vault safe, the authors ran a rigorous security audit:

• No Tiny Loops: They proved mathematically that the smallest loop in the final web is at least 8 strings long. This prevents errors from getting trapped in small circles.
• No Hidden Backdoors: They specifically checked for a known type of "backdoor" (a specific pattern of 16 bits that could act as a fake key). They proved their design eliminates this specific backdoor.
• The Result: They built a vault with 10,240 total bits, 4,108 of which are actual data, and the rest are for error checking. They are 100% sure the vault can fix any error involving up to 9 bits, and they found a specific example of a 32-bit error it can handle.

4. The Repair Crew (The Decoder)

Even with a perfect vault, errors happen. The paper also tested a "repair crew" (a decoder) that tries to fix the data when noise hits.

• The Crew's Job: They use a method called Belief Propagation (a smart guessing game) to figure out where the errors are.
• The "Post-Processing" Trick: Sometimes the crew gets stuck on a tiny, confusing pattern of errors. The authors added a set of simple, low-complexity rules (like "if you see three broken strings in a row, flip this one") to fix these stubborn cases.
• The Performance: When they tested this vault against heavy noise (5.8% error rate), the repair crew succeeded almost every time. They only failed 18 times out of 180 million attempts. That is a success rate of 99.99999%.

Summary

In everyday terms, this paper is like an architect saying:

"I have designed a new, mathematically perfect blueprint for a quantum vault. I built a small model, proved it has no weak loops, and then expanded it into a giant structure. I also hired a repair crew and tested them; they fixed almost every mistake we threw at them. Here is the proof that the vault is strong, and here is the data showing how well the repair crew works."

The authors are not claiming this is the only way to build a vault, nor are they saying it will be used in a specific product tomorrow. They are simply providing a verified, high-quality blueprint and proving that it works better than many previous attempts for specific sizes.

Technical Summary

Technical Summary: A Two-Branch Finite-Field Construction for Regular CSS LDPC Bases

Problem Statement
The paper addresses the challenge of constructing finite-length, regular Calderbank–Shor–Steane (CSS) quantum low-density parity-check (LDPC) codes. While asymptotic constructions have achieved strong rate and distance guarantees, finite-length design requires the simultaneous control of degree distribution, girth (specifically the absence of short cycles), and the commutation (orthogonality) condition inherent to CSS codes. A central difficulty lies in reconciling the algebraic constraints required for CSS orthogonality with the graph-theoretic properties (such as regularity and large girth) necessary for effective iterative decoding. Existing explicit constructions often struggle to satisfy these constraints simultaneously without relying on randomization that may not be easily verifiable or reproducible.

Methodology
The authors propose a two-branch multiplicative-coset construction over a finite field to generate regular CSS base matrices. The methodology is divided into two distinct stages:

1. Base Matrix Construction (Finite-Field Stage):

   • The construction defines two binary matrices, $H_X$ and $H_Z$, using translations of a multiplicative subgroup $M$ within a finite field $\mathbb{F}$.
   • Regularity: The design ensures a column weight $J$ and an even row weight $L = 2|M|$.
   • CSS Orthogonality: This is enforced by a "cross-type" coset condition. Specifically, the difference sets of coefficients between the two branches must generate identical cosets in the quotient group $\mathbb{F}^\times/M$. This ensures that every row pair $(X, Z)$ shares either zero or two columns, allowing the commutation condition to be satisfied via cyclic lifting.
   • Same-Type 4-Cycle Exclusion: To prevent 4-cycles within the $X$ or $Z$ Tanner graphs, the construction requires "same-type" difference cosets to be disjoint.
   • A normalized exhaustive search is employed to find coefficient sets satisfying these quotient-coset conditions for various $(J, L)$ pairs.

2. Cyclic Lift (Finite-Length Stage):

   • Once a valid base is selected, a $P$-fold cyclic lift is applied. This stage introduces randomness to break deterministic structures while preserving the algebraic constraints.
   • Orthogonality Preservation: The lift labels (exponents of circulant permutation matrices) must satisfy zero congruence constraints derived from the base matrix's shared column pairs.
   • Girth Enhancement: Nonzero congruence constraints are imposed to ensure that same-type base 6-cycles do not close in the lifted graph, thereby guaranteeing a girth of at least 8.
   • Low-Weight Support Exclusion: The method includes a specific check to exclude designated low-weight logical-support orbits (e.g., weight-16 patterns) by verifying that the lift labels do not satisfy the necessary linear congruences for these patterns to become valid logical operators.

Key Contributions

• General Construction Principle: The paper provides a field-independent, verifiable principle for constructing regular CSS bases. It reduces the complex problem of finding commuting sparse matrices to a finite search over quotient-coset conditions.
• Explicit Coefficient Examples: Through exhaustive search, the authors provide explicit coefficient arrays for numerous regularities, including $(3, 6), (3, 8), \dots, (3, 30)$ and $(4, 8), \dots, (4, 30)$.
• Detailed Finite-Length Instance: The paper presents a comprehensive case study of a $(3, 10)$-regular CSS code lifted 64-fold.
  • Parameters: The resulting code has length $N=10,240$, dimension $K=4,108$, and rate $R \approx 0.401$.
  • Distance Certificates: The construction certifies a distance lower bound of $d \ge 10$ (via exhaustive enumeration of logical representatives) and an upper bound of $d \le 32$ (via explicit logical witnesses).
  • Girth: The lifted Tanner graphs are certified to have a girth of at least 8.
• Decoding Framework: The authors implement joint log-domain belief propagation (BP) combined with low-complexity deterministic post-processing rules. These rules target small residual syndromes, including repairs for patterns with two unsatisfied checks, without using global low-weight syndrome solvers or post-hoc logical corrections.

Results

• Decoding Performance: For the $(3, 10)$ example, Frame Error Rate (FER) measurements were conducted over a depolarizing channel. At a depolarizing probability of $p = 0.058$, the post-processing FER achieved was $1.0 \times 10^{-7}$ (based on 18 failures out of 180 million trials).
• Structural Verification: The specific 64-fold lift successfully excluded the targeted weight-16 nondegenerate logical-support orbit and ensured no same-type 6-cycles closed, validating the algebraic constraints.
• Distance Bounds: The rigorous lower bound of $d \ge 10$ and the existence of weight-32 logical witnesses establish the range $10 \le d \le 32$. The absence of observed logical errors in the decoding experiments suggests the actual distance may be closer to the upper bound, though this is not rigorously proven.

Significance and Claims
The paper positions itself as a contribution to the finite-length line of quantum LDPC research, distinct from asymptotic constructions. Its primary significance lies in:

1. Separation of Concerns: It decouples the design of the degree distribution and orthogonality (handled by the base matrix) from the randomization and girth constraints (handled by the lift).
2. Verifiability: It offers a constructive, reproducible method where every step—from base coefficient selection to lift label verification—is explicitly checked against algebraic conditions.
3. Modest Scope: The authors explicitly state they do not propose a new asymptotic family or claim an exact distance theorem for a broad class of codes. Instead, they provide a general construction principle and a detailed, verified example of a specific code instance.
4. Future Directions: The paper suggests that future work could focus on strengthening the base stage to inherently possess higher girth (removing the need for 6-cycle exclusion constraints in the lift) or extending the construction to finite groups and rings beyond finite fields.

The work serves as a concrete demonstration that regular CSS LDPC codes with specific finite-length parameters can be systematically constructed, certified for structural properties, and decoded with high reliability using joint BP and targeted post-processing.