Explicit Construction of Quantum Quasi-Cyclic Low-Density Parity-Check Codes with Column Weight 2 and Girth 12
Daiki Komoto and Kenta Kasai · 2025
Read Explicit Construction of Quantum Quasi-Cyclic Low-Density Parity-Check Codes with Column Weight 2 and Girth 12 by Daiki Komoto and 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-2501-13444.txt.
Introduction
Daiki Komoto and Kenta Kasai wrote a paper in two thousand twenty-five on building quantum error-correcting codes. Such codes protect fragile quantum data from noise. The codes they study are built from sparse check patterns that repeat in blocks, and short loops in those patterns can weaken how well errors are fixed.
The authors give a direct recipe, based on algebra, for codes with no short loops up to a set length. The design keeps a paired structure that quantum codes need. They also extend the recipe to codes over larger symbol sets and to linked, chain-like codes. The point is to get strong codes by design, without long random searches for good patterns.
Catalog record
| CREATOR | Daiki Komoto and Kenta Kasai |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 33 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-13444
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Explicit Construction of Quantum Quasi-Cyclic Low-Density Parity-Check Codes with Column Weight 2 and Girth 12 Daiki Komoto and Kenta Kasai Abstract This study proposes an explicit construction method for quantum quasi-cyclic low-density parity-check (QC-LDPC) codes with a girth of 12. The proposed method designs parity-check matrices that maximize the girth while maintaining an orthogonal structure suitable for quantum error correction. By utilizing algebraic techniques, short cycles are eliminated, which improves error correction performance. Additionally, this method is extended to non-binary LDPC codes and spatially-coupled LDPC codes, demonstrating that both the girth and orthogonality can be preserved. The results of this study enable the design of high-performance quantum error-correcting codes without the need for random search. I Introduction low-density parity-check (LDPC) codes are a class of error-correcting codes that allow efficient decoding via the Sum-Product (SP) algorithm. However, it is well known that the presence of short cycles in the Tanner graph defining an LDPC code significantly degrades the error-correction performance of the SP algorithm [ 1 ] . To mitigate this issue, considerable research has been devoted to designing parity-check matrices that maximize the minimum cycle length, referred to as the girth, in the associated Tanner graph. A common approach for constructing LDPC codes with large girth involves randomly generating candidate matrices and selecting those with the largest observed minimum cycle length. Quasi-cyclic (QC-) LDPC codes [ 2 ] are regular LDPC codes—whose parity-check matrices have constant column and row weights J and L , respectively—constructed using circulant permutation matrices (CPMs), which provide structured algebraic properties suitable for hardware implementation. The girth of QC-LDPC codes is upper-bounded by 12 [ 2 ] . Although many works have aimed to explicitly construct QC-LDPC codes while avoiding short cycles [ 3 , 4 , 5 , 6 , 7 ] , achieving larger girth typically required random search. In contrast, a deterministic construction that achieves girth 12 eliminates this step entirely. The Calderbank-Shor-Steane (CSS) codes [ 8 , 9 ] form a class of quantum error-correcting codes that are constructed using two classical codes. A fundamental requirement for a CSS code is that its check matrices, H_{X} and H_{Z} , must satisfy the orthogonality condition: H_{X}H_{Z}^{\mathsf{T}}=O . When CSS codes are constructed using classical LDPC codes as component codes, they are referred to as quantum LDPC (QLDPC) codes. Similar to their classical counterparts, QLDPC codes employ the SP algorithm for efficient decoding. Consequently, it is crucial to design the underlying orthogonal classical LDPC matrices while eliminating short cycles to enhance the decoding performance. To date, quantum QC-LDPC codes with a girth greater than 4 have been proposed [ 10 ] , but due to the difficulty of constructing QC-LDPC matrix pairs while maintaining orthogonality, it has not been possible to increase the girth in the quantum case. Hagiwara and Imai proposed a construction of orthogonal QC-LDPC matrix pairs with girth greater than 4 in [ 10 ] . This construction has been extended to non-binary [ 11 ] and spatially coupled [ 12 ] formats to improve the performance of quantum LDPC codes; however, none of these constructions have explicitly achieved girth 12. Furthermore, [ 13 ] showed that the finite field extension method proposed in [ 11 ] is not always applicable to general orthogonal QC-LDPC matrix pairs and clarified the conditions under which it can be applied. While these conditions enable non-binary extensions, no SC-NB-QC-LDPC codes with J=2 and girth 12 have been proposed to date. Column weight J=2 is particularly important because (i) the girth upper bound for quantum QC-LDPC codes is limited to 6 when J\geq 3 [ 14 ] , (ii) NB-LDPC codes generally perform best at J=2 [ 15 ] , and (iii) the extension method to orthogonal NB-LDPC matrix pairs in [ 11 ] applies specifically to J=2 . In this study, we first provide an explicit construction method for QC-LDPC matrices with column weight J=2 , which achieves the upper bound of girth 12, in Subsection IV-A . In this subsection, we prove that the constructed matrices achieve a girth of 12. Furthermore, in Subsection IV-B and subsequent sections, we demonstrate that the same approach can be applied to prove girth 12 for other constructions as well. Next, in Subsection IV-B , we propose a construction method for orthogonal QC-LDPC matrix pairs for quantum LDPC codes. Specifically, we describe how to construct orthogonal matrix pairs using the matrices introduced in Subsection IV-A . This construction method for orthogonal QC-LDPC matrix pairs is based on the method proposed by Hagiwara and Imai for orthogonal QC-LDPC matrix pairs [ 10 ] . Furthermore, we show in Section V and Section VII that the proposed orthogonal QC-LDPC matrix pairs can be extended to NB-LDPC and SC-LDPC matrix pairs while preserving both orthogonality and girth 12. The extension to NB-LDPC matrices is based on the method proposed by Kasai et al. [ 11 ] , and the extension to SC-LDPC matrices is based on the method by Hagiwara et al. [ 12 ] . The performance evaluation results are almost the same as those presented in [ 13 ] . II QC-LDPC Matrices In this paper, we define \mathbb{Z}_{P}\overset{\text{\small def}}{=}\mathbb{Z}/P\mathbb{Z}=\{0,\cdots,P-1\},L/2+\mathbb{Z}_{L/2}=\{L/2,\cdots,L-1\} . One approach to constructing regular LDPC matrices is to arrange multiple permutation matrices in a structured layout. Since permutation matrices have a row weight and column weight of 1, a parity-check matrix constructed by arranging J\times L permutation matrices of size P results in a (J,L,P) -regular LDPC matrix. An arbitrary permutation matrix F of size P can be defined using a permutation mapping f , which is a bijective function \mathbb{Z}_{P}\to\mathbb{Z}_{P} , such that (F)_{f(i),i}=1 . We denote the set of permutation matrices of size P as \mathcal{M}_{P} and the set of permutation mappings as \mathcal{F}_{P} . Moreover, for a given permutation matrix F\in\mathcal{M}_{P} and its corresponding permutation mapping f\in\mathcal{F}_{P} , we express their relationship as F\sim f . A simple example of a permutation matrix is the circulant permutation matrix (CPM). A CPM is a permutation matrix defined by a permutation mapping of a specific algebraic form, referred to as a CPM mapping. Definition 1 (CPM and QC-LDPC Matrices) . For any b\in\mathbb{Z}_{P} , the function f(x)=x+b\pmod{P} defines a permutation mapping. The permutation matrix corresponding to f is called a CPM. A QC-LDPC code is a classical linear code whose parity-check matrix H is constructed by arranging J\times L CPMs. The matrix H can also be defined using a function array F(H) , where each CPM corresponds to a permutation mapping. Specifically, F_{jl}\sim f_{jl} , and the following representations hold: \displaystyle H=\begin{bmatrix}F_{11}&\cdots&F_{1L}\\ \vdots&\ddots&\vdots\\ F_{J1}&\cdots&F_{JL}\end{bmatrix},\quad F(H)=\begin{bmatrix}f_{11}&\cdots&f_{1L}\\ \vdots&\ddots&\vdots\\ f_{J1}&\cdots&f_{JL}\end{bmatrix}. (1) In general, QC-LDPC matrices are represented by an array of exponents consisting only of b in the function f=x+b . However, in this paper, we represent QC-LDPC matrices using the function array F(H) as shown above. Furthermore, we will use 0-based indexing for the matrices in this paper. Hereafter, unless otherwise stated, we assume that F\sim f and G\sim g represent CPMs and their corresponding CPM mappings of size P . Additionally, while the composition of f and g is usually denoted as f\circ g or g\circ f , for simplicity, we write them as fg and