pith. sign in

arxiv: 2606.11987 · v1 · pith:D4HJW6HHnew · submitted 2026-06-10 · 💻 cs.IT · math.CO· math.IT

Graphical Analysis of Lifted Product Code Constructions

Ragnar Freij-Hollanti , Kirsten D. Morris , Patricija \v{S}apokait\.e This is my paper

Pith reviewed 2026-06-27 08:13 UTC · model grok-4.3

classification 💻 cs.IT math.COmath.IT
keywords lifted product codesTanner graphsquantum LDPC codesabsorbing setsgraph isomorphismconnectivityparity-check matrices
0
0 comments X

The pith

The Tanner graphs of H_X and H_Z in lifted product codes are isomorphic.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that the Tanner graphs associated with the X and Z parity-check matrices of lifted product codes are isomorphic. This structural equivalence is used to derive conditions that guarantee the graphs are connected and to obtain bounds on the sizes of their minimal absorbing sets. These graph properties directly influence the decoding behavior and error-floor performance of the resulting quantum LDPC codes. A sympathetic reader would care because lifted product codes were the first family proven to be asymptotically good, so clarifying their common combinatorial structure simplifies analysis across the entire family.

Core claim

For lifted product codes constructed from classical base codes via the standard lifting and product operations, the Tanner graphs of H_X and H_Z are isomorphic; the paper gives explicit conditions ensuring connectivity of these graphs and supplies upper bounds on the cardinality of their minimal absorbing sets.

What carries the argument

The isomorphism between the Tanner graphs of the X-parity-check matrix and the Z-parity-check matrix.

If this is right

  • Isomorphism implies that any combinatorial property derived for one graph transfers immediately to the other.
  • Connectivity conditions ensure the parity-check matrices define connected Tanner graphs without isolated components.
  • Bounds on minimal absorbing sets limit the size of the smallest trapping sets that can cause decoder failure.
  • The shared graph structure unifies the study of X- and Z-error decoding floors within this code family.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The isomorphism may allow a single decoder architecture to be reused for both X and Z error correction without separate graph analysis.
  • The connectivity and absorbing-set bounds could be compared directly against other QLDPC constructions to identify which families have fewer small trapping sets.
  • If the bounds are tight, they supply a concrete combinatorial criterion for selecting base codes that minimize error floors.

Load-bearing premise

The codes examined are precisely the lifted product codes obtained from classical base codes by the usual lifting and product construction.

What would settle it

Exhibit one explicit lifted product code (with given base matrices and lift size) whose Tanner graph for H_X is not isomorphic to the Tanner graph for H_Z.

Figures

Figures reproduced from arXiv: 2606.11987 by Kirsten D. Morris, Patricija \v{S}apokait\.e, Ragnar Freij-Hollanti.

Figure 1
Figure 1. Figure 1: A labeled protograph GA and its lift G ′ A from Ex. 2.6. 2.2 Lifted Product Code Construction Quantum low-density parity-check (QLDPC) codes are an important class of quantum error-correcting codes defined by having sparse parity check matrices, making them suitable for low compexity iterative decoding. In this work, we focus on lifted product codes, which are a subclass of Calderbank-Shor-Steane (CSS) cod… view at source ↗
Figure 2
Figure 2. Figure 2: The graph GBX for an m × n base matrix GB. The left and right endpoints of each of the colored lines in the middle represent the same vertex. The edge labels on the left are bi,j , whereas the edge labels on the right are b −1 i,j . With this notation, we have Gi = GBX [{vi,1 . . . , vi,n} ∪ {ci,1, ..., ci,m}] and G ′ i = GBX [{c1,i . . . , cn,i} ∪ {v ′ i,1 , ..., v′ i,m}]. Theorem 2.7. The graphs GHX and … view at source ↗
Figure 3
Figure 3. Figure 3: The projections ΦL : GBX → GL and ΦR : GBX → GR. But the order of P β is the smallest integer m such that P βm = ι, in other words such that βm is a multiple of r. This number is clearly equal to r if and only if gcd(r, β) = 1, which is thus precisely when the number r m of connected components equals 1. ■ We extend this notion of connectivity to the graph lift GHX = G˜BX . In order to apply Theorems 2.4 a… view at source ↗
Figure 4
Figure 4. Figure 4: The graph GBX for a 2 × 2 base graph, with a spanning tree highlighted [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
read the original abstract

Lifted product codes are an important family of quantum low-density parity-check (QLDPC) codes, as they were the first QLDPC code family shown to be asymptotically good. Understanding the structure of their parity-check matrices $H_{\mathsf{X}}$ and $H_{\mathsf{Z}}$, as well as the associated Tanner graphs, is essential for analyzing their decoding behavior and error-floor performance. In this work, we show that the Tanner graphs of $H_{\mathsf{X}}$ and $H_{\mathsf{Z}}$ are indeed isomorphic, and investigate their graph-theoretical structure. We establish conditions ensuring the connectivity of these graphs and provide bounds on their minimal absorbing sets, providing new insight into the combinatorial structures influencing decoding performance.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript analyzes the graphical structure of lifted product codes, an important family of asymptotically good QLDPC codes. It claims that the Tanner graphs of the parity-check matrices H_X and H_Z are isomorphic, establishes conditions ensuring connectivity of these graphs, and provides bounds on their minimal absorbing sets to offer insight into decoding behavior and error-floor performance.

Significance. If rigorously established, the isomorphism result would be a useful structural observation for this code family, potentially simplifying symmetric analysis of the X and Z sectors. The connectivity conditions and absorbing-set bounds could inform decoder design for these codes. The work directly addresses a gap in combinatorial understanding of constructions that were the first shown to be asymptotically good.

major comments (2)
  1. Abstract: the central claims (isomorphism of Tanner graphs, connectivity conditions, and bounds on minimal absorbing sets) are stated without any proof sketches, equations, data, or verification steps, rendering soundness unassessable beyond the assertion level and making these results load-bearing for the paper's contribution.
  2. Abstract / construction section: the manuscript must explicitly confirm that the H_X and H_Z matrices are generated via the exact standard lifting maps and product operations from the lifted-product literature; any non-standard variant would prevent the claimed graph properties from applying to the asymptotically good family referenced.
minor comments (1)
  1. Abstract: notation for H_X and H_Z is introduced without a brief reminder of the base-code parameters or lifting degree, which would aid readability for readers outside the immediate subfield.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed review and constructive suggestions. We address the two major comments point-by-point below and will incorporate revisions to improve clarity and explicitness.

read point-by-point responses

  1. Referee: Abstract: the central claims (isomorphism of Tanner graphs, connectivity conditions, and bounds on minimal absorbing sets) are stated without any proof sketches, equations, data, or verification steps, rendering soundness unassessable beyond the assertion level and making these results load-bearing for the paper's contribution.

    Authors: We agree the abstract is concise and high-level by design. The full manuscript (Sections 3–5) contains the complete proofs: the isomorphism is established via an explicit bijection between the variable and check nodes of the two Tanner graphs; connectivity follows from degree and girth conditions on the base graphs; absorbing-set bounds are derived from combinatorial counting arguments on the lifted graphs. To improve assessability from the abstract alone, we will add one sentence indicating the proof techniques (graph bijection, combinatorial enumeration) while remaining within length limits. revision: partial

  2. Referee: Abstract / construction section: the manuscript must explicitly confirm that the H_X and H_Z matrices are generated via the exact standard lifting maps and product operations from the lifted-product literature; any non-standard variant would prevent the claimed graph properties from applying to the asymptotically good family referenced.

    Authors: The construction in Section 2 follows the standard lifted-product definition exactly (base matrices lifted by the same group action and combined via the Kronecker-type product as in the original references). We will insert an explicit sentence in both the abstract and the construction section stating that the parity-check matrices are obtained via the canonical lifting maps and product operation from the literature, thereby confirming applicability to the asymptotically good family. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The abstract and description present the isomorphism of Tanner graphs of H_X and H_Z, connectivity conditions, and absorbing-set bounds as direct consequences of the standard lifted-product construction from classical base codes. No equations, fitted parameters, or self-citations are shown that reduce any claim to its own inputs by definition. The central graphical results are framed as analysis of an externally defined family, with no load-bearing self-referential steps visible.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Review performed on abstract alone; no free parameters, axioms, or invented entities can be extracted.

pith-pipeline@v0.9.1-grok · 5656 in / 896 out tokens · 15344 ms · 2026-06-27T08:13:01.245451+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 1 canonical work pages

  1. [1]

    Fault-tolerant quantum computation with constant overhead,

    D. Gottesman, “Fault-tolerant quantum computation with constant overhead,”Quantum Inform. and Computation, vol. 14, pp. 1338–1372, nov 2014

    2014

  2. [2]

    Asymptotically good quantum and locally testable classical LDPC codes,

    P. Panteleev and G. Kalachev, “Asymptotically good quantum and locally testable classical LDPC codes,” inProceedings of the 54th annual ACM SIGACT symposium on theory of computing, 2022, pp. 375–388

    2022

  3. [3]

    Quasi-cyclic LDPC codes based on pre-lifted protographs,

    D. G. Mitchell, R. Smarandache, and D. J. Costello, “Quasi-cyclic LDPC codes based on pre-lifted protographs,”IEEE Transactions on Information Theory, vol. 60, no. 10, pp. 5856–5874, 2014

    2014

  4. [4]

    Structural analysis of generalized quasi-cyclic LDPC codes: Rank, design and generator matrices,

    R. Smarandache, D. G. Mitchell, and A. Gómez-Fonseca, “Structural analysis of generalized quasi-cyclic LDPC codes: Rank, design and generator matrices,”IEEE Transactions on Information Theory, 2025

    2025

  5. [5]

    Non-binary protograph-based LDPC codes: Enumerators, analysis, and designs,

    L. Dolecek, D. Divsalar, Y. Sun, and B. Amiri, “Non-binary protograph-based LDPC codes: Enumerators, analysis, and designs,”IEEE transactions on information theory, vol. 60, no. 7, pp. 3913–3941, 2014

    2014

  6. [6]

    A heuristic search for good low-density parity-check codes at short block lengths,

    Y. Mao and A. H. Banihashemi, “A heuristic search for good low-density parity-check codes at short block lengths,” inICC 2001. IEEE International Conference on Communications. Conference Record (Cat. No. 01CH37240), vol. 1. IEEE, 2001, pp. 41–44

    2001

  7. [7]

    An algorithm for counting short cycles in bipartite graphs,

    T. R. Halford and K. M. Chugg, “An algorithm for counting short cycles in bipartite graphs,”IEEE Transactions on Information Theory, vol. 52, no. 1, pp. 287–292, 2005

    2005

  8. [8]

    Efficient algorithm for finding dominant trapping sets of LDPC codes,

    M. Karimi and A. H. Banihashemi, “Efficient algorithm for finding dominant trapping sets of LDPC codes,”IEEE Transactions on Information Theory, vol. 58, no. 11, pp. 6942–6958, 2012. References 15

    2012

  9. [9]

    On the minimum distances of finite-length lifted product quantum LDPC codes,

    N. Raveendran, D. Declercq, and B. Vasić, “On the minimum distances of finite-length lifted product quantum LDPC codes,” 2025. [Online]. Available: https://arxiv.org/abs/2503.07567

    arXiv 2025

  10. [10]

    A recursive approach to low complexity codes,

    R. Tanner, “A recursive approach to low complexity codes,”IEEE Transactions on Information Theory, vol. 27, no. 5, pp. 533–547, 1981

    1981

  11. [11]

    Analysis of absorbing sets for array-based LDPC codes,

    L. Dolecek, Z. Zhang, V. Anantharam, M. J. Wainwright, and B. Nikolić, “Analysis of absorbing sets for array-based LDPC codes,”2007 IEEE International Conference on Communications, pp. 6261–6268, 2007

    2007

  12. [12]

    Absorbing sets in quantum LDPC codes,

    K. D. Morris, T. Pllaha, and C. A. Kelley, “Absorbing sets in quantum LDPC codes,”Advances in Mathematics of Communications, vol. 23, no. 0, pp. 234–254, 2026. [Online]. Available: https://www.aimsciences.org/article/id/69a6ac251c9579521d08fdc7

    2026

  13. [13]

    J. L. Gross and T. W. Tucker,Topological graph theory. Courier Corporation, 2001

    2001

  14. [14]

    Good quantum error-correcting codes exist,

    A. R. Calderbank and P. W. Shor, “Good quantum error-correcting codes exist,”Phys. Rev. A, vol. 54, pp. 1098–1105, aug 1996. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.54.1098

    work page doi:10.1103/physreva.54.1098 1996

  15. [15]

    Sparse-graph codes for quantum error correction,

    D. J. MacKay, G. Mitchison, and P. L. McFadden, “Sparse-graph codes for quantum error correction,” IEEE Transactions on Information Theory, vol. 50, no. 10, pp. 2315–2330, 2004

    2004

  16. [16]

    The vec-permutation matrix, the vec operator and kronecker products: A review,

    H. V. Henderson and S. R. Searle, “The vec-permutation matrix, the vec operator and kronecker products: A review,”Linear and multilinear algebra, vol. 9, no. 4, pp. 271–288, 1981

    1981