Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2607.13666

Spectral and Additive Combinatorial Methods for Cycles and Absorbing Sets in Lifted-Product Quantum LDPC Codes

Aida Abiad, Nichola Castriota

Published Jul 15, 2026• 0 citations
arXivHTMLPDF

Abstract

The finite-length performance of quantum low-density parity-check (LDPC) codes under iterative decoding is governed by small substructures of the Tanner graph, principally short cycles and absorbing sets. While the classical theory of these substructures for quasi-cyclic codes is well developed through discrete Fourier transform (DFT) methods, these tools do not directly address the two-block tensor structure $H_X = [\,\widetilde{H}_1 \mid I \otimes \widetilde{B}^T\,]$ of the lifted-product (quasi-cyclic generalised hypergraph product, QC-GHP) codes that dominate current quantum LDPC constructions. In this paper we develop a quantum-specific spectral framework that exploits this structure. At its core is a DFT block-diagonalisation of $H_X H_X^T$ that reduces moment-trace and cycle computations from an $(r_1\ell)\times(r_1\ell)$ matrix to a sum of $\ell$ small $r_1\times r_1$ Hermitian matrices, with the second block entering only as a scalar shift. From this result we derive a closed-form $4$-cycle count for generalised bicycle codes via additive energies, a joint Sidon characterisation of girth $6$ in the spirit of Fossorier's classical criterion, a Fourier expression for the number of $(3,3)$ elementary absorbing sets in column-weight-$3$ codes via the Wang-Dolecek-Wesel triangle bijection, and a lower bound on stopping-set sizes using the expander mixing lemma.

DOI
10.48550/arxiv.2607.13666

Related papers

Combinatorial Analysis of Dyadic and Quasi-Dyadic Codes

Anthony Gómez-Fonseca, Gretchen L. Matthews, Kirsten D. Morris +1 more

Quantum low-density parity-check (QLDPC) codes offer a promising route to scalable fault-tolerant quantum computation, but their performance under iterative decoding is strongly influenced by short-cycle structure and other harmful subgraphs in the associated Tanner graphs. This paper develops an algebraic framework for constructing and analyzing (Q)LDPC codes from dyadic and quasi-dyadic matrices-translation-invariant $2^\ell \times 2^\ell$ binary matrices specified compactly by a signature row and forming a commutative ring with recursive block structure. Leveraging this structure, we relate cycles in lifted Tanner graphs to tailless backtrackless closed walks in the protograph and derive efficient, implementable methods to enumerate and control short cycles (notably $4$-, $6$-, and $8$-cycles). We introduce dyadic-aware PEG-style construction algorithms that use forbidden sets of shifts to maximize attainable girth when possible and otherwise minimize the multiplicity of the shortest cycles at the target girth. Motivated by error-floor phenomena, we further characterize and explicitly enumerate absorbing sets in key dyadic layout boundary cases, identifying configurations that induce abundant $(a,0)$-absorbing sets. Finally, we propose CSS-oriented dyadic constructions that satisfy commutation constraints by design and demonstrate via belief-propagation simulations that reducing short-cycle multiplicity can yield substantial decoding gains even when girth cannot be increased.

cs.ITCross-listedarXiv:2605.01942•May 5, 2026•2 citations

Matrix-Theoretic Design of Cycle-Aware Quasi-Cyclic LDPC Codes

Qianfan Wang, Hengzhou Xu, Ji Zhang +3 more

Quasi-cyclic low-density parity-check (QC-LDPC) codes are widely adopted in modern communication standards due to their near-capacity performance and hardware-friendly structures. In this paper, we propose a matrix-theoretic, cycleaware framework for constructing QC-LDPC codes from arbitrary base matrices by systematically optimizing their shift values to maximize the girth and minimize the number of cycles with length girth. We present a cycle-aware iterative algorithm that identifies critical edges on the largest number of shortest cycles and modifies their shift values to break multiple cycles simultaneously. The framework supports flexible lifting sizes, which enable a single base matrix to generate codes with arbitrary lengths. Constructive bounds show that girth-6 and girth-8 codes can be achieved with lifting sizes as small as 4 and 14, respectively. Simulation results show that the proposed codes achieve good performance under iterative decoding while retaining the quasicyclic structure essential for hardware implementation.

International Symposium on Wireless Communication Systems•Aug 1, 2026•0 citations

High-Girth Regular Quantum LDPC Codes from Square-Base Hypergraph Products via CPM Lifts

Koki Okada, Kenta Kasai

We study square-base Calderbank--Shor--Steane (CSS) hypergraph-product codes as a finite-length class for regular high-girth quantum low-density parity-check (LDPC) design. For base matrices of small column weight, we give checkable conditions for regularity, rank deficiency, and short-cycle exclusion, and we present explicit column-weight-three and column-weight-four examples with Tanner girth 6 and 8. We also analyze circulant permutation matrix (CPM) lifts of this class. Using the standard voltage-sum criterion, we identify orthogonality-forced Tanner 8-cycles and show that CPM lifting cannot raise the Tanner girth beyond 8 when these cycles are present. As a representative finite-length instance, a randomized CPM lift of the girth-8 base construction gives a $[[28800,62,18\le d\le192]]$ girth-8 $(3,6)$-regular CSS-LDPC code. Complete enumeration excludes nontrivial logical supports of weight at most $16$ on both sides, giving $d_X,d_Z\ge18$; explicit weight-$192$ representatives give $d_X,d_Z\le192$. Under degeneracy-aware belief-propagation decoding with optional ordered-statistics-decoding-lite post-processing, this code produced zero decoding failures in $2.993\times 10^8$ independent trials at depolarizing probability $p=0.1402$; the Wilson 95\% upper confidence bound is $1.28\times 10^{-8}$.

quant-pharXiv:2604.27817•May 1, 2026•5 citations

Generalized Construction of Quasi-Cyclic Regular LDPC Codes Based on Permutation Matrices

E.M. Gabidulin, Abdolhosein Moinian, Bahram Honary

A new approach is proposed for constructing regular low-density parity-check (LDPC) codes based on tensor product of matrices. In this paper, first a general construction method of regular LDPC codes exploiting permutation matrices is described. Constructed codes have a quasi-cyclic structure with no short cycles of length 4 in their Tanner graph, hence simple encoding while maintaining good performance is achieved. The paper also demonstrates a generalized design, which covers a large family of LDPC codes and number of other construction methods. The new generalized LDPC codes are defined by a small number of parameters and cover a large set of code lengths and rates. Using these codes, LDPC matrices of any column weight and row weight can be constructed. Performance of these codes under iterative decoding compares well with other well-structured as well as random LDPC codes

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•16 citations

Counting Short Cycles of Quasi Cyclic Protograph LDPC Codes

Mehdi Karimi, Amir H. Banihashemi

An efficient method for counting short cycles in the Tanner graphs of quasi cyclic (QC) protograph low-density parity-check (LDPC) codes is presented. The method is based on the relationship between the number of short cycles in the graph and the eigenvalues of the directed edge matrix of the graph. We demonstrate that for a QC protograph LDPC code, the complexity of computing such eigenvalues can be reduced significantly by representing the directed edge matrix as a block circulant matrix. Numerical results are presented to show the lower complexity of the proposed method compared to the existing algorithms for counting short cycles. These results also reveal that QC LDPC codes on average have a superior short cycle and girth distribution compared to similar randomly constructed codes.

IEEE Communications Letters•Feb 10, 2012•33 citations

A new algorithm of counting the number of small stopping sets and girth in QC-LDPC Codes

Lingjun Kong, Yang Xiao

It is well known that the performance of low-density parity check (LDPC) codes under iterative decoding is determined by certain combinatorial structures (such as stopping sets and girth) in the Tanner graph. The difficulty in enumerating all possible combinations of the columns may prevent an efficient search of good LDPC codes with small stopping sets and girth. To solve the problem, this paper presents a new algorithm of counting the number of small stopping sets and girth by analyzing the shapes of the cycles of Tanner graph in parity check matrix for designing good LDPC codes which is less complex than the existing algorithms. This method can be used effectively to evaluate the performance of LDPC codes according to their small stopping sets and girth distributions.

International Conference on Signal Processing•Oct 1, 2008•0 citations
The finite-length performance of quantum low-density parity-check (LDPC) codes under iterative decoding is governed by small substructures of the Tanner graph, principally short cycles and absorbing sets. While the classical theory of these substructures for quasi-cyclic codes is well developed through discrete Fourier transform (DFT) methods, these tools do not directly address the two-block tensor structure HX=[ H~1∣I⊗B~T ]H_X = [\,\widetilde{H}_1 \mid I \otimes \widetilde{B}^T\,]HX​=[H1​∣I⊗BT] of the lifted-product (quasi-cyclic generalised hypergraph product, QC-GHP) codes that dominate current quantum LDPC constructions. In this paper we develop a quantum-specific spectral framework that exploits this structure. At its core is a DFT block-diagonalisation of HXHXTH_X H_X^THX​HXT​ that reduces moment-trace and cycle computations from an (r1ℓ)×(r1ℓ)(r_1\ell)\times(r_1\ell)(r1​ℓ)×(r1​ℓ) matrix to a sum of ℓ\ellℓ small r1×r1r_1\times r_1r1​×r1​ Hermitian matrices, with the second block entering only as a scalar shift. From this result we derive a closed-form 444-cycle count for generalised bicycle codes via additive energies, a joint Sidon characterisation of girth 666 in the spirit of Fossorier's classical criterion, a Fourier expression for the number of (3,3)(3,3)(3,3) elementary absorbing sets in column-weight-333 codes via the Wang-Dolecek-Wesel triangle bijection, and a lower bound on stopping-set sizes using the expander mixing lemma.
Quantum low-density parity-check (QLDPC) codes offer a promising route to scalable fault-tolerant quantum computation, but their performance under iterative decoding is strongly influenced by short-cycle structure and other harmful subgraphs in the associated Tanner graphs. This paper develops an algebraic framework for constructing and analyzing (Q)LDPC codes from dyadic and quasi-dyadic matrices-translation-invariant 2ℓ×2ℓ2^\ell \times 2^\ell2ℓ×2ℓ binary matrices specified compactly by a signature row and forming a commutative ring with recursive block structure. Leveraging this structure, we relate cycles in lifted Tanner graphs to tailless backtrackless closed walks in the protograph and derive efficient, implementable methods to enumerate and control short cycles (notably 444-, 666-, and 888-cycles). We introduce dyadic-aware PEG-style construction algorithms that use forbidden sets of shifts to maximize attainable girth when possible and otherwise minimize the multiplicity of the shortest cycles at the target girth. Motivated by error-floor phenomena, we further characterize and explicitly enumerate absorbing sets in key dyadic layout boundary cases, identifying configurations that induce abundant (a,0)(a,0)(a,0)-absorbing sets. Finally, we propose CSS-oriented dyadic constructions that satisfy commutation constraints by design and demonstrate via belief-propagation simulations that reducing short-cycle multiplicity can yield substantial decoding gains even when girth cannot be increased.
Quasi-cyclic low-density parity-check (QC-LDPC) codes are widely adopted in modern communication standards due to their near-capacity performance and hardware-friendly structures. In this paper, we propose a matrix-theoretic, cycleaware framework for constructing QC-LDPC codes from arbitrary base matrices by systematically optimizing their shift values to maximize the girth and minimize the number of cycles with length girth. We present a cycle-aware iterative algorithm that identifies critical edges on the largest number of shortest cycles and modifies their shift values to break multiple cycles simultaneously. The framework supports flexible lifting sizes, which enable a single base matrix to generate codes with arbitrary lengths. Constructive bounds show that girth-6 and girth-8 codes can be achieved with lifting sizes as small as 4 and 14, respectively. Simulation results show that the proposed codes achieve good performance under iterative decoding while retaining the quasicyclic structure essential for hardware implementation.
We study square-base Calderbank--Shor--Steane (CSS) hypergraph-product codes as a finite-length class for regular high-girth quantum low-density parity-check (LDPC) design. For base matrices of small column weight, we give checkable conditions for regularity, rank deficiency, and short-cycle exclusion, and we present explicit column-weight-three and column-weight-four examples with Tanner girth 6 and 8. We also analyze circulant permutation matrix (CPM) lifts of this class. Using the standard voltage-sum criterion, we identify orthogonality-forced Tanner 8-cycles and show that CPM lifting cannot raise the Tanner girth beyond 8 when these cycles are present. As a representative finite-length instance, a randomized CPM lift of the girth-8 base construction gives a [[28800,62,18≤d≤192]][[28800,62,18\le d\le192]][[28800,62,18≤d≤192]] girth-8 (3,6)(3,6)(3,6)-regular CSS-LDPC code. Complete enumeration excludes nontrivial logical supports of weight at most 161616 on both sides, giving dX,dZ≥18d_X,d_Z\ge18dX​,dZ​≥18; explicit weight-192192192 representatives give dX,dZ≤192d_X,d_Z\le192dX​,dZ​≤192. Under degeneracy-aware belief-propagation decoding with optional ordered-statistics-decoding-lite post-processing, this code produced zero decoding failures in 2.993×1082.993\times 10^82.993×108 independent trials at depolarizing probability p=0.1402p=0.1402p=0.1402; the Wilson 95\% upper confidence bound is 1.28×10−81.28\times 10^{-8}1.28×10−8.
A new approach is proposed for constructing regular low-density parity-check (LDPC) codes based on tensor product of matrices. In this paper, first a general construction method of regular LDPC codes exploiting permutation matrices is described. Constructed codes have a quasi-cyclic structure with no short cycles of length 4 in their Tanner graph, hence simple encoding while maintaining good performance is achieved. The paper also demonstrates a generalized design, which covers a large family of LDPC codes and number of other construction methods. The new generalized LDPC codes are defined by a small number of parameters and cover a large set of code lengths and rates. Using these codes, LDPC matrices of any column weight and row weight can be constructed. Performance of these codes under iterative decoding compares well with other well-structured as well as random LDPC codes
An efficient method for counting short cycles in the Tanner graphs of quasi cyclic (QC) protograph low-density parity-check (LDPC) codes is presented. The method is based on the relationship between the number of short cycles in the graph and the eigenvalues of the directed edge matrix of the graph. We demonstrate that for a QC protograph LDPC code, the complexity of computing such eigenvalues can be reduced significantly by representing the directed edge matrix as a block circulant matrix. Numerical results are presented to show the lower complexity of the proposed method compared to the existing algorithms for counting short cycles. These results also reveal that QC LDPC codes on average have a superior short cycle and girth distribution compared to similar randomly constructed codes.
It is well known that the performance of low-density parity check (LDPC) codes under iterative decoding is determined by certain combinatorial structures (such as stopping sets and girth) in the Tanner graph. The difficulty in enumerating all possible combinations of the columns may prevent an efficient search of good LDPC codes with small stopping sets and girth. To solve the problem, this paper presents a new algorithm of counting the number of small stopping sets and girth by analyzing the shapes of the cycles of Tanner graph in parity check matrix for designing good LDPC codes which is less complex than the existing algorithms. This method can be used effectively to evaluate the performance of LDPC codes according to their small stopping sets and girth distributions.