Systematic Non-Binary Extension of LDPC-CSS Codes Preserving Orthogonality
Kenta Kasai · 2025
Read Systematic Non-Binary Extension of LDPC-CSS Codes Preserving Orthogonality by Kenta Kasai (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-25583.txt.
Introduction
Kenta Kasai extends LDPC-CSS codes beyond binary alphabets. His 2025 paper studies finite-field extensions preserving support. CSS codes are quantum error-correcting codes with special form. Their parity-check matrices must satisfy an orthogonality setting. Corresponding rows overlap in an even number of positions. Sparse constructions usually allow at most two overlaps. Preserving binary support matters for useful code design.
He studies extensions that keep the same support pattern. Parity-check matrices define the given binary CSS code. Beyond low-density settings, a systematic construction is proposed. It extends to arbitrary CSS codes in general. Feasible finite-field generalizations maintain binary support there. The orthogonality setting is also maintained throughout extension. Non-binary codes can offer advantages over binary ones. Preserving support keeps current code form intact. Orthogonality ensures the CSS construction remains valid quantum mechanically. Systematic methods help generalize known binary codes.
Catalog record
| CREATOR | Kenta Kasai |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-25583
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Systematic Non-Binary Extension of LDPC-CSS Codes Preserving Orthogonality Kenta Kasai Abstract We study finite-field extensions that preserve the same support as the parity-check matrices defining a given binary CSS code. Here, an LDPC-CSS code refers to a CSS code whose parity-check matrices are orthogonal in the sense that each pair of corresponding rows overlaps in an even (possibly zero) number of positions, typically at most twice in sparse constructions. Beyond the low-density setting, we further propose a systematic construction method that extends to arbitrary CSS codes, providing feasible finite-field generalizations that maintain both the binary support and the orthogonality condition. I Introduction In this paper, we address the problem of extending a binary CSS code to a finite-field representation while preserving its structural properties. Given a pair of binary parity-check matrices whose corresponding rows overlap in an even number of positions, we seek to construct non-binary matrices over a finite field that share the same pattern of nonzero entries and remain orthogonal. Although this task can be viewed as a multivariate quadratic feasibility problem over a finite field, it is generally hard to solve due to the nonlinear nature of the constraints and the exponential size of the solution space. The method originally proposed in [ 1 ] transforms a pair of orthogonal binary matrices into non-binary matrices over a finite field while keeping the same support pattern. This technique was first developed for quasi-cyclic LDPC codes [ 2 ] with column weight two, later applied to toric codes [ 3 ] , and subsequently generalized to protograph-based constructions [ 4 ] . The resulting non-binary CSS codes, as demonstrated in recent works [ 4 , 5 ] , achieved decoding performance close to the hashing bound when joint belief propagation was used. However, these previous approaches were limited to cases where each column contains exactly two ones. Extending the construction to more general CSS codes—where column weights may vary across different rows and matrices—remains a challenging problem. In such settings, one must simultaneously preserve the binary support and maintain the orthogonality between the two parity-check matrices, while also avoiding short cycles and ensuring sufficient flexibility in assigning non-binary coefficients. Although orthogonality can be trivially maintained by assigning constant coefficients to each column or by setting all nonzero entries to one, such simple constructions tend to degrade important code properties such as minimum distance and error-floor performance. Our goal, therefore, is to characterize the entire space of feasible finite-field extensions so that one can systematically or randomly generate valid non-binary instances with diverse coefficient configurations. To achieve this, we parameterize the non-binary entries using multiplicative representations over the finite field and translate the orthogonality constraints into a sparse system of linear congruences among integer exponents. This system can be efficiently solved either in canonical form using Smith normal decomposition or through a lightweight elimination process involving only integer additions and row swaps. Once a feasible set of exponents is obtained, the corresponding non-binary matrices are recovered by standard linear algebra over the finite field. As a simple baseline, we introduce a separable assignment of coefficients that always guarantees orthogonality for any even-overlap pattern. II Problem Setting This section formulates the finite-field extension problem for arbitrary CSS codes. Let (H_{C},H_{D}) be a binary orthogonal pair with H_{C}\in\{0,1\}^{M_{X}\times N} and H_{D}\in\{0,1\}^{M_{Z}\times N} . Write the entries of H_{C} and H_{D} as c_{i,j} and d_{i^{\prime},j} , respectively. They satisfy the binary orthogonality condition H_{C}H_{D}^{\mathsf{T}}=0, which is equivalent to \displaystyle\sum_{j=0}^{N-1}c_{i,j}\,d_{i^{\prime},j}=0\quad\text{for all }i=0,\ldots,M_{X}-1,\;i^{\prime}=0,\ldots,M_{Z}-1. (1) All arithmetic in ( 1 ) is over \mathbb{F}_{2} . Our goal is to construct matrices H_{\Gamma}=(\gamma_{i,j})\in\mathbb{F}_{q}^{M_{X}\times N} and H_{\Delta}=(\delta_{i^{\prime},j})\in\mathbb{F}_{q}^{M_{Z}\times N} such that H_{\Gamma}H_{\Delta}^{\mathsf{T}}=0,\qquad\mathrm{supp}(H_{\Gamma})=\mathrm{supp}(H_{C}),\qquad\mathrm{supp}(H_{\Delta})=\mathrm{supp}(H_{D}). Equivalently, the support constraints enforce \gamma_{i,j}=0\;\;\text{iff}\;\;c_{i,j}=0,\qquad\delta_{i^{\prime},j}=0\;\;\text{iff}\;\;d_{i^{\prime},j}=0, so in particular c_{i,j}=1\Rightarrow\gamma_{i,j}\in\mathbb{F}_{q}^{\times} and d_{i^{\prime},j}=1\Rightarrow\delta_{i^{\prime},j}\in\mathbb{F}_{q}^{\times} . The orthogonality over \mathbb{F}_{q} is then \displaystyle\sum_{j=0}^{N-1}\gamma_{i,j}\,\delta_{i^{\prime},j}=0\quad\text{for all }i=0,\ldots,M_{X}-1,\;i^{\prime}=0,\ldots,M_{Z}-1. (2) All arithmetic in ( 2 ) is over \mathbb{F}_{q} . The unknowns are the entries \{\gamma_{i,j}:c_{i,j}=1\}\cup\{\delta_{i^{\prime},j}:d_{i^{\prime},j}=1\} . The constraints ( 2 ) yield M_{X}M_{Z} homogeneous quadratic equations in these variables over \mathbb{F}_{q} . Thus, finding a feasible assignment is an instance of the multivariate quadratic (MQ) feasibility problem, which is NP-complete [ 6 ] . III Finite-Field Extension for LDPC-CSS Codes The binary orthogonality condition ( 1 ) implies that every row pair (i,i^{\prime}) has an even number of common nonzero columns. Let S_{i,i^{\prime}}\subseteq\{0,1,\ldots,N-1\} denote the set of column indices where both c_{i,j}=1 and d_{i^{\prime},j}=1 ; that is, S_{i,i^{\prime}}\overset{\text{\small def}}{=}\{\,j\mid c_{i,j}=1\text{ and }d_{i^{\prime},j}=1\,\}. By construction, |S_{i,i^{\prime}}| is always even. We focus on the canonical case in which each row pair shares either 0 or 2 columns. This covers many practical CSS constructions (e.g., quasi-cyclic and protograph-based designs) and arises frequently in sparse instances, where pairwise overlaps beyond two are unlikely. Assume H_{C}H_{D}^{\mathsf{T}}=0 , fix q=2^{m} , and let \alpha\in\mathbb{F}_{q}^{\times} be a primitive element. Let H_{\Gamma}=(\gamma_{i,j}) and H_{\Delta}=(\delta_{i^{\prime},j}) preserve the binary support: each zero in (H_{C},H_{D}) remains zero, and each nonzero entry is replaced by an element of \mathbb{F}_{q}^{\times} . We parameterize the nonzero entries multiplicatively as \gamma_{i,j}=\alpha^{e_{i,j}},\qquad\delta_{i^{\prime},j}=\alpha^{f_{i^{\prime},j}}, with exponents e_{i,j},f_{i^{\prime},j}\in\mathbb{Z}/(q-1)\mathbb{Z} . If a row pair (i,i^{\prime}) shares exactly two columns j and j^{\prime} , the orthogonality condition \sum_{j}\gamma_{i,j}\delta_{i^{\prime},j}=0 over \mathbb{F}_{q} reduces to \gamma_{i,j}\delta_{i^{\prime},j}+\gamma_{i,j^{\prime}}\delta_{i^{\prime},j^{\prime}}=0. Since \mathrm{char}(\mathbb{F}_{q})=2 , we have x+y=0\iff x=y . Hence \gamma_{i,j}\delta_{i^{\prime},j}=\gamma_{i,j^{\prime}}\delta_{i^{\prime},j^{\prime}}\;\Longleftrightarrow\;\alpha^{\,e_{i,j}-e_{i,j^{\prime}}+f_{i^{\prime},j}-f_{i^{\prime},j^{\prime}}}=1, and therefore e_{i,j}-e_{i,j^{\prime}}+f_{i^{\prime},j}-f_{i^{\prime},j^{\prime}}\equiv 0\pmod{q-1}. Collecting these relations over all row pairs (i,i^{\prime}) with |S_{i,i^{\prime}}|=2 produces a sparse system of linear congruences: Av\equiv 0\pmod{q-1}, (3) where v stacks the unknown exponents \{e_{i,j}:c_{i,j}=1\}\cup\{f_{i^{\prime},j}:d_{i^{\prime},j}=1\} . The coefficient matrix A\in\{0,\pm 1\}^{r\times n} has one row for each overlapping pair (i,i^{\prime};j,j^{\prime}) and one column for each nonzero entry of H_{C} or H_{D} . Equation ( 3 ) compactly captures all additive consistency constraints among the exponents. III-A Solving the Linear Congruence System For a modulus n=q-1>0 and an integer matrix A , the homogeneous system Av\equiv 0\pmod{n} can be analyzed via the Smith normal form (SNF) of A over \mathbb{Z} [ 7 ] , which provides a canonical decomposition of the solution space. When q-1 is prime (that is, when 2^{m}-1 is a Mersenne prime), the ring \mathbb{Z}/(q-1)\mathbb{Z} forms a finite field isomorphic to \mathbb{F}_{q-1} . In this case, the system Av\equiv 0 is an ordinary linear equation over \mathbb{F}_{q-1} , and its nullspace can be computed by standard Gaussian elimination. Even when q-1 is composite, it is often possible to solve Av\equiv 0\pmod{q-1} efficiently without computing the SNF. This is because all nonzero coefficients of A are in \{+1,-1\} , so that elimination can proceed using only row swaps and addition or subtraction of rows modulo q-1 , without any division. In practice, this yields a fraction-free elimination process that produces a row-reduced form with unit pivots (each pivot being 1 or -1 ), after which the nullspace can be read off by back-substitution. The elimination proceeds as follows: (1) at each step, choose a pivot column containing an entry \pm 1 , and swap that row into the pivot position; (2) for every other row having a nonzero in the same column, add or subtract the pivot row to zero out that entry; (3) once an echelon pattern is obtained, clear the entries above each pivot using the same \pm row additions; and (4) identify the free variables corresponding to columns without pivots. In our experiments, every sparse LDPC-CSS instance satisfied this condition, and