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•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•0 citations

A Construction of High Performance Quasicyclic LDPC Codes: A Combinatoric Design Approach

Muhammad Asif, Wuyang Zhou, Muhammad Ajmal +2 more

This correspondence presents a construction of quasicyclic (QC) low-density parity-check (LDPC) codes based on a special type of combinatorial designs known as block disjoint difference families (BDDFs). The proposed construction of QC-LDPC codes gives parity-check matrices with column weight three and Tanner graphs having a girth lower-bounded by 6. The proposed QC-LDPC codes provide an excellent performance with iterative decoding over an additive white Gaussian-noise (AWGN) channel. Performance analysis shows that the proposed short and moderate length QC-LDPC codes perform as well as their competitors in the lower signal-to-noise ratio (SNR) region but outperform in the higher SNR region. Also, the codes constructed are quasicyclic in nature, so the encoding can be done with simple shift-register circuits with linear complexity.

Wireless Communications and Mobile Computing•Feb 3, 2019•12 citations

Tanner $(J,L)$ Quasi-Cyclic LDPC Codes: Girth Analysis and Derived Codes

Hengzhou Xu, Huaan Li, Baoming Bai +2 more

Girth plays an important role in the design of low-density parity-check (LDPC) codes. Motivated by the works on the girth of some classes of Tanner quasi-cyclic (QC) LDPC codes, e.g., Tanner (3, 5), (3, 7), (3, 11), and (5, 7) codes, we, in this paper, study the girth of Tanner$(J,L)$QC-LDPC codes where$J$and$L$can be any two positive integers. According to the sufficient and necessary conditions for the existence of cycles of lengths 4, 6, 8, and 10, we propose an algorithm to determine the girth of Tanner$(J,L)$QC-LDPC codes with finite code lengths. Through the analysis of the obtained girth values, we generalize the laws of the girth distributions of Tanner$(J,L)$QC-LDPC codes. Furthermore, based on the exponent matrices of Tanner$(J,L)$QC-LDPC codes with known girths, we employ the column selection method and/or the masking technique to construct binary/nonbinary LDPC codes. The numerical results show that the constructed LDPC codes have good performance under iterative decoding over the additive white Gaussian noise channel.

IEEE Access•Dec 10, 2018•21 citations

Two-dimensional Entanglement-assisted Quantum Quasi-cyclic Low-density Parity-check Codes

Pavan Kumar, Shayan Srinivasa Garani

For any positive integer $g \ge 2$, we derive general condition for the existence of a $2g$-cycle in the Tanner graph of two-dimensional ($2$-D) classical quasi-cyclic (QC) low-density parity-check (LDPC) codes. Depending on whether $p$ is an odd prime or a composite number, we construct two distinct families of $2$-D classical QC-LDPC codes with girth $>4$ by stacking $p \times p \times p$ tensors. Furthermore, using generalized Behrend sequences, we propose an additional family of $2$-D classical QC-LDPC codes with girth $>6$, constructed via a similar tensor-stacking approach. All the proposed $2\text{-D}$ classical QC-LDPC codes exhibit an erasure correction capability of at least $p \times p$. Based on the constructed $2\text{-D}$ classical QC-LDPC codes, we derive two families of $2\text{-D}$ entanglement-assisted (EA) quantum low-density parity-check (QLDPC) codes. The first family of $2\text{-D}$ EA-QLDPC codes is obtained from a pair of $2\text{-D}$ classical QC-LDPC codes and is designed such that the unassisted part of the Tanner graph of the resulting EA-QLDPC code is free of $4$-cycles, while requiring only a single ebit to be shared across the quantum transceiver. The second family is constructed from a single $2\text{-D}$ classical QC-LDPC code whose Tanner graph is free from $4$-cycles. Moreover, the constructed EA-QLDPC codes inherit an erasure correction capability of $p \times p$, as the underlying classical codes possess the same erasure correction property.

arXiv:2601.08927•Jan 13, 2026•0 citations

An Efficient Strategy to Count Cycles in the Tanner Graph of Quasi-Cyclic LDPC Codes

Anthony Gómez-Fonseca, Roxana Smarandache, David G. M. Mitchell

In this paper, we present an efficient strategy to enumerate the number of k-cycles, g≤k<2g, in the Tanner graph of a quasi-cyclic low-density parity-check (QC-LDPC) code with girth g using its polynomial parity-check matrix H. This strategy works for both (dv,dc)-regular and irregular QC-LDPC codes. In this approach, we note that the mth power of the polynomial adjacency matrix can be used to describe walks of length m in the protograph and can therefore be sufficiently described by the matrices Bm(H)(HHT)m/2H(m2), where m≥0. We provide formulas for the number of k-cycles, Nk, by just taking into account repetitions in some multisets constructed from the matrices Bm(H). This approach is shown to have low complexity. For example, in the case of QC-LDPC codes based on the 3×nv fully-connected protograph, the complexity of determining Nk, for k=4,6,8,10 and 12, is O(nv2log(N)), O(nv2log(nv)log(N)), O(nv4log4(nv)log(N)), O(nv4log(nv)log(N)) and O(nv6log6(nv)log(N)), respectively. The complexity, depending logarithmically on the lifting factor N, gives our approach, to the best of our knowledge, a significant advantage over previous works on the cycle distribution of QC-LDPC codes.

IEEE Journal on Selected Areas in Information Theory•Jan 1, 2023•8 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.
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.
This correspondence presents a construction of quasicyclic (QC) low-density parity-check (LDPC) codes based on a special type of combinatorial designs known as block disjoint difference families (BDDFs). The proposed construction of QC-LDPC codes gives parity-check matrices with column weight three and Tanner graphs having a girth lower-bounded by 6. The proposed QC-LDPC codes provide an excellent performance with iterative decoding over an additive white Gaussian-noise (AWGN) channel. Performance analysis shows that the proposed short and moderate length QC-LDPC codes perform as well as their competitors in the lower signal-to-noise ratio (SNR) region but outperform in the higher SNR region. Also, the codes constructed are quasicyclic in nature, so the encoding can be done with simple shift-register circuits with linear complexity.
Tanner (J,L)(J,L)(J,L) Quasi-Cyclic LDPC Codes: Girth Analysis and Derived Codes
Girth plays an important role in the design of low-density parity-check (LDPC) codes. Motivated by the works on the girth of some classes of Tanner quasi-cyclic (QC) LDPC codes, e.g., Tanner (3, 5), (3, 7), (3, 11), and (5, 7) codes, we, in this paper, study the girth of Tanner(J,L)(J,L)(J,L)QC-LDPC codes whereJJJandLLLcan be any two positive integers. According to the sufficient and necessary conditions for the existence of cycles of lengths 4, 6, 8, and 10, we propose an algorithm to determine the girth of Tanner(J,L)(J,L)(J,L)QC-LDPC codes with finite code lengths. Through the analysis of the obtained girth values, we generalize the laws of the girth distributions of Tanner(J,L)(J,L)(J,L)QC-LDPC codes. Furthermore, based on the exponent matrices of Tanner(J,L)(J,L)(J,L)QC-LDPC codes with known girths, we employ the column selection method and/or the masking technique to construct binary/nonbinary LDPC codes. The numerical results show that the constructed LDPC codes have good performance under iterative decoding over the additive white Gaussian noise channel.
For any positive integer g≥2g \ge 2g≥2, we derive general condition for the existence of a 2g2g2g-cycle in the Tanner graph of two-dimensional (222-D) classical quasi-cyclic (QC) low-density parity-check (LDPC) codes. Depending on whether ppp is an odd prime or a composite number, we construct two distinct families of 222-D classical QC-LDPC codes with girth >4>4>4 by stacking p×p×pp \times p \times pp×p×p tensors. Furthermore, using generalized Behrend sequences, we propose an additional family of 222-D classical QC-LDPC codes with girth >6>6>6, constructed via a similar tensor-stacking approach. All the proposed 2-D2\text{-D}2-D classical QC-LDPC codes exhibit an erasure correction capability of at least p×pp \times pp×p. Based on the constructed 2-D2\text{-D}2-D classical QC-LDPC codes, we derive two families of 2-D2\text{-D}2-D entanglement-assisted (EA) quantum low-density parity-check (QLDPC) codes. The first family of 2-D2\text{-D}2-D EA-QLDPC codes is obtained from a pair of 2-D2\text{-D}2-D classical QC-LDPC codes and is designed such that the unassisted part of the Tanner graph of the resulting EA-QLDPC code is free of 444-cycles, while requiring only a single ebit to be shared across the quantum transceiver. The second family is constructed from a single 2-D2\text{-D}2-D classical QC-LDPC code whose Tanner graph is free from 444-cycles. Moreover, the constructed EA-QLDPC codes inherit an erasure correction capability of p×pp \times pp×p, as the underlying classical codes possess the same erasure correction property.
In this paper, we present an efficient strategy to enumerate the number of k-cycles, g≤k<2g, in the Tanner graph of a quasi-cyclic low-density parity-check (QC-LDPC) code with girth g using its polynomial parity-check matrix H. This strategy works for both (dv,dc)-regular and irregular QC-LDPC codes. In this approach, we note that the mth power of the polynomial adjacency matrix can be used to describe walks of length m in the protograph and can therefore be sufficiently described by the matrices Bm(H)(HHT)m/2H(m2), where m≥0. We provide formulas for the number of k-cycles, Nk, by just taking into account repetitions in some multisets constructed from the matrices Bm(H). This approach is shown to have low complexity. For example, in the case of QC-LDPC codes based on the 3×nv fully-connected protograph, the complexity of determining Nk, for k=4,6,8,10 and 12, is O(nv2log(N)), O(nv2log(nv)log(N)), O(nv4log4(nv)log(N)), O(nv4log(nv)log(N)) and O(nv6log6(nv)log(N)), respectively. The complexity, depending logarithmically on the lifting factor N, gives our approach, to the best of our knowledge, a significant advantage over previous works on the cycle distribution of QC-LDPC codes.