⚛️ quantum physics

Systematic Non-Binary Extension of LDPC-CSS Codes Preserving Orthogonality

This paper presents a systematic method for extending binary LDPC-CSS codes to arbitrary finite fields by constructing non-binary generalizations that preserve the original binary support and the orthogonality condition of the parity-check matrices.

Original authors: Kenta Kasai

Published 2026-08-17

📖 6 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

The Quantum Puzzle: Why We Need Better Codes

Imagine you are trying to send a secret message across a stormy sea. The waves (noise) are huge, and they love to flip your letters upside down or swap them around. To survive, you don't just send the message once; you send it wrapped in a complex, redundant package. This is the world of error-correcting codes. In the realm of quantum computing, where information is stored in fragile particles called qubits, these codes are the only thing standing between a working computer and total chaos.

One of the most promising types of these codes is called a CSS code (named after its creators, Calderbank, Shor, and Steane). Think of a CSS code as a giant, intricate web of rules. To keep the message safe, the code uses two sets of "checkers" (matrices) that constantly verify the data. For the system to work, these two sets of checkers must be perfectly orthogonal. In plain English, this means they must look at the data in a way that their "gazes" never clash in a confusing manner; they overlap in a very specific, even number of spots, like two dancers stepping on the same floor tiles an even number of times so they never trip each other.

For a long time, scientists have been building these codes using simple "binary" rules (just 0s and 1s). But recently, researchers discovered that if they could upgrade these codes to use "non-binary" rules (using a whole alphabet of numbers instead of just two), the codes could become much stronger and better at fixing errors. However, there was a massive hurdle: upgrading the rules while keeping the delicate "orthogonal" dance intact was like trying to change the choreography of a ballet without breaking the dancers' legs. It was a math problem so hard that many thought it might be impossible to solve for complex codes. This is where the story of the paper begins.

The Paper's Discovery: A New Way to Dance

The paper, titled "Systematic Non-Binary Extension of LDPC-CSS Codes Preserving Orthogonality" by Kenta Kasai, tackles this exact problem. The author asks: How can we take a binary quantum code and upgrade it to a more powerful non-binary version without breaking the strict "orthogonality" rules that make it work?

The paper finds that while this sounds like a nightmare of complex math (specifically, a "multivariate quadratic feasibility problem" which is notoriously difficult), there is a clever way to simplify it. The author proposes a method to translate the problem from the confusing world of multiplying numbers into the simpler world of adding numbers.

Here is how the magic trick works:
Instead of trying to guess the right numbers for the new code, the author suggests treating every non-zero number in the code as a "power" of a special base number (called a primitive element). If you have a number like $X$ , you can think of it as "Base to the power of 5." By doing this, the difficult rule of "multiplying numbers to get zero" transforms into a much easier rule: "adding the powers to get zero."

This transformation turns a tangled knot of hard equations into a neat, sparse system of simple addition problems. The paper demonstrates that you can solve these addition problems efficiently using standard math tools (like a method called Smith normal decomposition or a lightweight elimination process). Once you have the correct "powers" (exponents), you simply convert them back into the fancy non-binary numbers, and you have a new, stronger code that still dances perfectly with its partner.

The "Easy" Way vs. The "Smart" Way

The paper also explores a "baseline" or "easy" method to create these codes, which the author calls the Canonical Separable Assignment (CSA). Imagine you are painting a mural where every column of the wall has a specific color pattern. The "easy" method says, "Just paint every column with a color that depends only on the row and the column, ignoring the specific relationship between the two checkers."

The paper shows that this easy method always works mathematically. It guarantees that the orthogonality condition is met, no matter how the code is built. However, the author points out a major flaw: this easy method is too predictable. It keeps all the "weak spots" (short logical operators) that existed in the original binary code. It's like upgrading a car's engine but keeping the same rusty brakes; the car goes faster, but it still stops poorly.

To fix this, the paper argues that we must use the "smart" method described earlier (solving the exponent congruence equations). This method allows for a diverse, random assignment of numbers that breaks up those weak spots. By carefully choosing the "powers," we can eliminate the short, weak logical operators that plague the binary versions, potentially creating codes with much higher "minimum distance" (a measure of how much error the code can handle).

What the Paper Rules Out and What It Proves

It is important to note what this paper does not claim. The author explicitly rules out the idea that simply assigning constant coefficients (like making every number the same) or using the "easy" separable assignment is the best solution. While those methods work mathematically, the paper argues they fail to improve the code's ability to fight errors because they preserve the bad habits of the original binary code.

The paper does not claim to have solved the problem for every single possible code in existence with a formal proof that covers every edge case. Instead, it presents a systematic construction method that works for a wide range of codes, particularly those where rows overlap by 0 or 2 positions (which covers many practical designs like quasi-cyclic and protograph-based codes).

The confidence in the results comes from two sources:

Mathematical Logic: The paper proves that the complex multiplication problem can be converted into a solvable addition problem.
Simulations and Examples: The author tested this method on specific examples, including a "hypergraph-product" code. In these simulations, the method successfully generated valid non-binary codes that satisfied all orthogonality rules. The paper notes that in every sparse LDPC-CSS instance they tried, the system could be solved using simple row swaps and additions, without needing complex division.

The Takeaway

In summary, this paper provides a roadmap for upgrading quantum error-correcting codes. It shows that by changing how we look at the numbers (switching from multiplication to addition of exponents), we can systematically build stronger, non-binary codes that keep their structural integrity. While a straightforward way to build these codes exists, the paper suggests that the "smart," systematic approach is necessary to truly unlock the potential of these codes, potentially leading to more robust quantum computers in the future. The work is a blend of clever mathematical reformulation and practical demonstration, offering a new tool for engineers designing the next generation of quantum technology.

Technical Summary: Systematic Non-Binary Extension of LDPC-CSS Codes Preserving Orthogonality

Problem Statement
The paper addresses the challenge of extending binary Calderbank-Shor-Steane (CSS) codes to finite-field (non-binary) representations while strictly preserving two critical structural properties: the binary support pattern (the locations of non-zero entries) and the orthogonality condition between the two parity-check matrices ( $H_C H_D^T = 0$ ).

In a binary CSS code, the orthogonality condition implies that every pair of corresponding rows from the $X$ and $Z$ parity-check matrices overlaps in an even number of positions. The goal is to construct non-binary matrices $H_\Gamma$ and $H_\Delta$ over a finite field $\mathbb{F}_q$ such that:

$\text{supp}(H_\Gamma) = \text{supp}(H_C)$ and $\text{supp}(H_\Delta) = \text{supp}(H_D)$ .
$H_\Gamma H_\Delta^T = 0$ over $\mathbb{F}_q$ .

This problem is inherently difficult because finding such matrices constitutes a multivariate quadratic (MQ) feasibility problem over a finite field, which is generally NP-complete due to the non-linear nature of the constraints and the exponential size of the solution space. While previous methods [1–4] successfully extended specific cases (e.g., quasi-cyclic LDPC codes with column weight two), they struggled to generalize to arbitrary CSS codes where column weights vary and overlaps may exceed two.

Methodology
The author proposes a systematic construction method that transforms the non-linear orthogonality constraints into a tractable linear system. The core methodology involves the following steps:

Multiplicative Parameterization: Non-zero entries in the extended matrices are parameterized using a primitive element $\alpha$ of $\mathbb{F}_q$ . Specifically, entries are written as $\gamma_{i,j} = \alpha^{e_{i,j}}$ and $\delta_{i',j} = \alpha^{f_{i',j}}$ , where the exponents $e_{i,j}$ and $f_{i',j}$ are integers modulo $q-1$ .
Linearization of Constraints: For the canonical case where row pairs overlap in exactly two columns ( $j$ and $j'$ ), the orthogonality condition $\gamma_{i,j}\delta_{i',j} + \gamma_{i,j'}\delta_{i',j'} = 0$ in characteristic 2 simplifies to $\gamma_{i,j}\delta_{i',j} = \gamma_{i,j'}\delta_{i',j'}$ . In terms of exponents, this becomes a linear congruence:
$e_{i,j} - e_{i,j'} + f_{i',j} - f_{i',j'} \equiv 0 \pmod{q-1}$
Collecting these relations for all overlapping row pairs yields a sparse system of linear congruences $Av \equiv 0 \pmod{q-1}$ .
Solution via Integer Elimination: The system is solved for the exponent vector $v$ . The paper notes that because the coefficient matrix $A$ contains only entries from $\{0, \pm 1\}$ , the system can be solved efficiently without modular division. The method employs a lightweight elimination process involving only row swaps and integer additions/subtractions modulo $q-1$ to reach a row-reduced form, from which the nullspace (feasible exponents) can be determined. Alternatively, Smith Normal Decomposition can be used for a canonical analysis.
Canonical Separable Assignment (CSA): As a baseline, the paper introduces a "separable assignment" where coefficients are defined as $\gamma_{i,j} = \alpha^{A_i + C_j}$ and $\delta_{i',j} = \alpha^{B_{i'} - C_j}$ . This construction guarantees orthogonality for any even overlap pattern by making the product $\gamma_{i,j}\delta_{i',j}$ independent of the column index $j$ .

Key Contributions and Results

Generalization to Arbitrary CSS Codes: Unlike prior work limited to column-weight-two constraints, this method provides a systematic way to extend arbitrary CSS codes, handling varying column weights and complex overlap patterns.
Efficient Feasibility: The transformation of the MQ problem into a sparse linear congruence system allows for the efficient generation of valid non-binary instances. The paper demonstrates this via a Hypergraph Product (HGP) code example, successfully solving the exponent system for $q=256$ and recovering valid non-binary matrices.
Feasibility Witness (CSA): The introduction of the Canonical Separable Assignment proves that feasible non-binary extensions exist for any even-overlap pattern, serving as a theoretical lower bound for solvability.
Limitations of Separable Assignments: The paper explicitly demonstrates that while the CSA guarantees orthogonality, it fails to improve code performance. Because the CSA preserves the binary codeword structure (up to scalar multiples), it cannot eliminate short logical operators. Consequently, the paper argues that solving the full exponent congruence system (rather than using the separable baseline) is necessary to achieve the distance improvements observed in previous non-binary LDPC studies.

Significance and Claims
The paper claims to clarify the algebraic structure underlying feasible non-binary CSS codes. By characterizing the entire space of feasible finite-field extensions, the work enables the systematic or random generation of diverse non-binary instances.

The author states that this framework opens possibilities for designing high-performance quantum LDPC and qudit codes. However, the paper remains modest regarding immediate performance claims; it does not present new decoding simulations or distance bounds for the specific examples generated. Instead, it positions the proposed method as a foundational tool for future work, specifically citing the potential application to HGP codes, higher-degree quantum APM-LDPC, and QC-LDPC codes, with the goal of evaluating their joint belief-propagation decoding performance in subsequent research.