Graphical Analysis of Lifted Product Code Constructions

arXiv:2606.11987 · cs.IT, math.CO, math.IT · Submitted 2026-06-10 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Graphical Analysis of Lifted Product Code Constructions".

Jane: Here's the gist of the paper. 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.

Tom: Understanding the structure of their parity-check matrices HX and HZ, as well as the associated Tanner graphs, is essential for analyzing their decoding behavior and error-floor performance.

Jane: In this work, we show that the Tanner graphs of HX and HZ are indeed isomorphic, and investigate their graph-theoretical structure.

Tom: 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.

Paper summary: Tom: So, to wrap up this paper, "Graphical Analysis of Lifted Product Code Constructions," we’ve seen they establish that the Tanner graphs HX and HZ are isomorphic and they’ve provided conditions for connectivity based on the base matrix B >

Jane: And beyond that, they give bounds on girth and minimal absorbing sets, which directly ties these graph-theoretical properties to the error floor performance of these lifted quantum low-density parity-check codes >

Lu: So what this means in simpler terms is that by understanding how the graphs are structured, we can predict how well the code will perform when it’s actually being used for quantum error correction >

Meng: It gives us a roadmap for choosing design parameters like the lift size and matrix entries to make sure we avoid bad structures that cause performance issues at scale >

Lalam: And they show how absorbing sets in the base graph GBX lift to GHX, which is crucial because it helps us understand the error floor when we scale up these codes >

Tom: The main implication for someone listening here is that this work provides concrete tools to ensure that iterative decoding based on the graph structure will actually be robust and not just a theoretical idea >

Conclusion: Tom: So we've been looking at these complex parity check matrices, HX and HZ from this paper titled "Graphical Analysis of Lifted Product Code Constructions."

Jane: It boils down to showing that these two different structures are actually the same thing, they are isomorphic.

Lu: The authors prove this by building permutation matrices P and Q so you can relabel the nodes in both graphs.

Meng: So, structurally, they are identical graphs when you look at how the connections are made between variables and checks.

Tom: That's a big deal because it means if you understand one graph, you understand the other completely.

Jane: And they go further by setting up conditions for when these graphs connect properly so that your decoding algorithm actually works well.

Lu: They define a condition on this two by two base matrix B where the greatest common divisor of beta and r has to be one for the graph to be connected.

Meng: A condition like that is good, but what does it mean for the actual size of these codes we're trying to build?

Tom: It sets a minimum requirement on how big your lift size r needs to be compared to n and m just so you get a connected graph.

Jane: And they look at things like girth, which is basically the shortest cycle in the graph, and they find that for connected graphs here it's always eight.

Lu: They also characterize these minimal absorbing sets, which are basically where errors get stuck and those bounds give us a handle on how bad the error floor gets.

Meng: So if I'm trying to ship a code that runs reliably at scale, knowing exactly how many of these absorbing sets there can be is really helpful for my deployment plan.

Tom: Exactly. This work gives us the specific tools needed to optimize those design choices—like picking the right entries for that base matrix B—to get better performance in practice.

Jane: And they show precisely how those error traps in the basic graph translate into traps in the actual lifted code, which is crucial for understanding long-term reliability.

Lu: It’s a comprehensive analysis of these combinatorial structures that directly impacts how we design quantum codes.

Tom: So, this paper lays out the structural blueprint and gives us the rules to build better codes from that blueprint.

Jane: Now, it leaves us wondering what happens when we try to use these conditions on much bigger matrices than this specific two by two case.

cs.IT, math.CO, math.IT

Submitted: 2026-06-10

Updated: 2026-11-06

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 77/100

The gist: 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.

Key concepts

Tanner Graphs (HX and HZ)
These are bipartite graphs used to represent the structure of parity-check codes. They show how variables (nodes on one side) are connected to checks (nodes on the other side). Analyzing their structure is key to understanding how errors propagate during decoding.
Isomorphism
The paper proves that the Tanner graphs for HX and HZ are isomorphic, meaning they have the exact same underlying structure. This equivalence simplifies analysis because properties found in one graph apply directly to the other, allowing for a unified study of their performance.
Absorbing Sets
These sets represent specific configurations of errors that can cause decoding to fail or stall at a certain error floor. The paper characterizes these sets by dividing them into types (left, right, mixed), which gives insight into the worst-case error behavior of the code.

Terminology

Summary

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. p. 0

Where the paper says it

Graphical Analysis of Lifted Product Code Constructions Ragnar Freij-Hollanti, Kirsten D. Morris, Patricija Šapokait˙e June 11, 2026 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 HX and HZ, as well as the associated Tanner graphs, is essential for analyzing their decoding behavior and error-floor performance. p. 0
Where the paper says it

Morris, Patricija Šapokait˙e June 11, 2026 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 HX and HZ, 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 HX and HZ are indeed isomorphic, and investigate their graph-theoretical structure. p. 0
Where the paper says it

Understanding the structure of their parity-check matrices HX and HZ, 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 HX and HZ 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. p. 0
Where the paper says it

In this work, we show that the Tanner graphs of HX and HZ 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.

Structural Equivalence of Tanner Graphs

The paper establishes a fundamental structural equivalence between the Tanner graphs associated with the lifted product quantum CSS codes, showing that they are isomorphic. This isomorphism is proven by constructing permutation matrices P and Q such that BX = P(BZ)Q, which leads to the relabeling of check nodes and variable nodes in HX and HZ. p. 6

Where the paper says it

This correspondence between BX and BZ lifts to HX and HZ. Graphically, this relabeling of the row and column indices is equivalent to relabeling the check nodes and variable nodes, and thus the Tanner graphs corresponding to HX = h B ⊗ In Im ⊗ B∗ i and HZ = h In ⊗ B B∗ ⊗ Im i are isomorphic.

The graphs GBX and GBZ decompose into disjoint copies of GB on the left and right, leading to a complete (n, m)-bipartite intersection graph. p. 4
Where the paper says it

These identified nodes then serve as the check nodes of the big graph GBX , as in Figure 2. The intersection graph between the subgraphs Gi , G′ j thus itself forms a complete (n, m)- bipartite graph.

Connectivity Conditions for Robust Decoding

The connectivity of the lifted graph GHX is determined by analyzing permutation products along cycles in the base graph GB. The paper introduces conditions on a 2 × 2 base matrix B, stating that G˜B is connected if and only if gcd(β, r) = 1, where β:= ε11 − ε12 − ε21 + ε22 (mod r). p. 6

Where the paper says it

The graph lift G˜B is connected if and only if gcd(β, r) = 1, where β := ε11 − ε12 − ε21 + ε22 (mod r). The base graph GB = K2,2 is a 4-cycle, so G˜B consists only of the preimage of this cycle.

This condition ensures that the number of connected components equals 1, which is necessary for GHX to be connected. p. 7
Where the paper says it

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 .

Girth and Absorbing Set Analysis

The analysis extends to girth and absorbing sets, providing bounds on error-floor performance. For a 2 × 2 base matrix B over C2 such that GHX is connected, the paper proves that GHX has girth 8. p. 1

Where the paper says it

In Section 3, we give conditions on the base matrix B such that the resulting lifted graph GHX is connected. We provide an analysis of girth and minimal absorbing set structures in Section 4.

Furthermore, it characterizes minimal absorbing sets of GBX by dividing them into left type, right type, and mixed type absorbing sets.

Optimization for Code Construction

The authors outline a hierarchy for choosing the lift size and permutation entries of B to optimize code properties, prioritizing connectivity, maximizing g(GHX), minimizing short cycles, and minimizing minimal absorbing sets. They suggest selecting the first row and column of B to have identity permutation values to simplify the analysis of fundamental cycles. p. 9

Where the paper says it

2) In total, we selected mn + n 2 + m2 − 1 edges. The first row of each left B block attaches all left variables to the first check row, the first column of the first left B block connects the m check rows together, and the right-hand choices attach the right variables without creating cycles.

The requirement that GHX has girth 8 implies that the lift size r must satisfy r ≥ max(m, n). p. 1
Where the paper says it

In Section 3, we give conditions on the base matrix B such that the resulting lifted graph GHX is connected. We provide an analysis of girth and minimal absorbing set structures in Section 4.

Lifting Absorbing Sets

The paper details how absorbing sets in GBX lift to those in GHX. Specifically, a (2, 0) absorbing set in GBX lifts to an (a', 0) absorbing set in GHX, where a' = 2·ord(ι(γ)), with ord(ι(γ)) = r/gcd(r,ι(γ)). This lifting mechanism is crucial for understanding the error-floor performance of the lifted codes. p. 0

Where the paper says it

Morris, Patricija Šapokait˙e June 11, 2026 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 HX and HZ, as well as the associated Tanner graphs, is essential for analyzing their decoding behavior and error-floor performance.

Conclusion and Future Work

In conclusion, this work analyzes the structure of the Tanner graphs corresponding to HX and HZ for a particular case of the lifted product code construction. The authors provide conditions to ensure that the graph is connected, which is necessary to ensure robust graph-based iterative decoding. p. 1

Where the paper says it

In Section 2, we provide the necessary background. In Section 3, we give conditions on the base matrix B such that the resulting lifted graph GHX is connected.

p. 1
Where the paper says it

In Section 2, we provide the necessary background. In Section 3, we give conditions on the base matrix B such that the resulting lifted graph GHX is connected.

Future work includes further analysis on choosing the entries of the base matrix B to optimize the properties of the Tanner graph for well-performing iterative decoding. p. 0
Where the paper says it

In particular, the relationship between the base protograph and the resulting Tanner graph requires more care, influencing the analysis of structural properties such as connectivity, girth, and the presence of small substructures that influence decoding performance [6, 7, 8]. In this work, we investigate these questions for a class of lifted product constructions derived from a single base matrix B as described in [9].

p. 0
Where the paper says it

In particular, the relationship between the base protograph and the resulting Tanner graph requires more care, influencing the analysis of structural properties such as connectivity, girth, and the presence of small substructures that influence decoding performance [6, 7, 8]. In this work, we investigate these questions for a class of lifted product constructions derived from a single base matrix B as described in [9].

The paper is organized as follows. p. 1
Where the paper says it

Building on this result, we then explore the implications of this connectivity criterion for the girth and absorbing sets of the resulting graphs. This paper is organized as follows.

p. 1
Where the paper says it

Building on this result, we then explore the implications of this connectivity criterion for the girth and absorbing sets of the resulting graphs. This paper is organized as follows.

References

[1] D. Gottesman, “Fault-tolerant quantum computation with constant overhead,” Quantum Inform. p. 0

Where the paper says it

Constructing quantum error correcting code families that are efficient and practically implementable remains an active area of research. Quantum low-density parity-check (LDPC) codes are particularly promising candidates for quantum error correction, especially given Gottesman’s result proving constant overhead of fault tolerant quantum computation when using quantum LDPC codes with a constant encoding rate [1].

and Computation, vol. p. 0
Where the paper says it

Constructing quantum error correcting code families that are efficient and practically implementable remains an active area of research. Quantum low-density parity-check (LDPC) codes are particularly promising candidates for quantum error correction, especially given Gottesman’s result proving constant overhead of fault tolerant quantum computation when using quantum LDPC codes with a constant encoding rate [1].

14, pp. 1338–1372, nov 2014.

[2] P. Panteleev and G. Kalachev, “Asymptotically good quantum and locally testable classical LDPC codes,” in Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, 2022, pp. p. 0

Where the paper says it

Pantaleev and Kalachev resolved this open question with the introduction of lifted product (LP) codes, the first construction of asymptotically good quantum LDPC codes [2]. These codes combine the protograph based structure from classical LDPC codes along with tensoring operations, yielding codes with both constant rate and growing distance.

375–388.

[3] D. G. Mitchell, R. Smarandache, and D. J. Costello, “Quasi-cyclic LDPC codes based on pre-lifted protographs,” IEEE Transactions on Information Theory, vol. p. 0

Where the paper says it

Pantaleev and Kalachev resolved this open question with the introduction of lifted product (LP) codes, the first construction of asymptotically good quantum LDPC codes [2]. These codes combine the protograph based structure from classical LDPC codes along with tensoring operations, yielding codes with both constant rate and growing distance.

60, no. 10, pp. 5856–5874, 2014.

[4] 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. p. 0

Where the paper says it

These codes combine the protograph based structure from classical LDPC codes along with tensoring operations, yielding codes with both constant rate and growing distance. However, a detailed understanding of the structural and combinatorial properties of these codes, particularly explicit constructions, remains open.

[5] L. Dolecek, D. p. 1

Where the paper says it

An important combinatorial invariant of a Tanner graph is its absorbing sets. These were first introduced by Dolecek et.

Divsalar, Y. Sun, and B. Amiri, “Non-binary protograph-based LDPC codes: Enumerators, analysis, and designs,” IEEE transactions on information theory, vol. p. 0
Where the paper says it

Pantaleev and Kalachev resolved this open question with the introduction of lifted product (LP) codes, the first construction of asymptotically good quantum LDPC codes [2]. These codes combine the protograph based structure from classical LDPC codes along with tensoring operations, yielding codes with both constant rate and growing distance.

60, no. 7, pp. 3913–3941, 2014.

[6] Y. Mao and A. H. Banihashemi, “A heuristic search for good low-density parity-check codes at short block lengths,” in ICC 2001. p. 0

Where the paper says it

Quantum low-density parity-check (LDPC) codes are particularly promising candidates for quantum error correction, especially given Gottesman’s result proving constant overhead of fault tolerant quantum computation when using quantum LDPC codes with a constant encoding rate [1]. Despite this promise, constructing quantum LDPC codes that are asymptotically good while also maintaining desirable decoding performance in the finite block length regime has been nontrivial.

IEEE International Conference on Communications. p. 3
Where the paper says it

The condition that CX ⊆ C⊥ Z implies that HZHT X = 0, hence the stabilizer generators for the code commute and CSS(CX, CZ) forms a valid stabilizer code. In quantum communications channels, the X errors, or bit-flip errors, and Z errors, or phase-flip errors, are typically correlated, but we ignore this correlation for CSS codes [15] and decode X and Z errors separately, using HX to decode Z errors and HZ to decode X errors.

Conference Record (Cat. No. 01CH37240), vol. 1, pp. 41–44.

[7] 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.

[8] M. Karimi and A. H. Banihashemi, “Efficient algorithm for finding dominant trapping sets of LDPC codes,” IEEE Transactions on Information Theory, vol. p. 0

Where the paper says it

Constructing quantum error correcting code families that are efficient and practically implementable remains an active area of research. Quantum low-density parity-check (LDPC) codes are particularly promising candidates for quantum error correction, especially given Gottesman’s result proving constant overhead of fault tolerant quantum computation when using quantum LDPC codes with a constant encoding rate [1].

58, no. 11, pp. 6942–6958, 2012.

[9] N. Raveendran, D. Declercq, and B. Vasić, “On the minimum distances of finite-length lifted product quantum LDPC codes,” 2025. p. 0

Where the paper says it

Despite this promise, constructing quantum LDPC codes that are asymptotically good while also maintaining desirable decoding performance in the finite block length regime has been nontrivial. Pantaleev and Kalachev resolved this open question with the introduction of lifted product (LP) codes, the first construction of asymptotically good quantum LDPC codes [2].

[10] R. Tanner, “A recursive approach to low complexity codes,” IEEE Transactions on Information Theory, vol. p. 0

Where the paper says it

Morris, Patricija Šapokait˙e June 11, 2026 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 HX and HZ, as well as the associated Tanner graphs, is essential for analyzing their decoding behavior and error-floor performance.

27, no. 5, pp. 533–547, 1981.

[11] L. Dolecek, Z. p. 1

Where the paper says it

An important combinatorial invariant of a Tanner graph is its absorbing sets. These were first introduced by Dolecek et.

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. p. 3
Where the paper says it

In quantum communications channels, the X errors, or bit-flip errors, and Z errors, or phase-flip errors, are typically correlated, but we ignore this correlation for CSS codes [15] and decode X and Z errors separately, using HX to decode Z errors and HZ to decode X errors. For this reason, the performance of iterative graph-based decoders for these codes reduces to understanding the two Tanner graphs separately.

6261–6268.

[12] K. D. Morris, T. Pllaha, and C. A. Kelley, “Absorbing sets in quantum LDPC codes,” Advances in Mathematics of Communications, vol. p. 3

Where the paper says it

The condition that CX ⊆ C⊥ Z implies that HZHT X = 0, hence the stabilizer generators for the code commute and CSS(CX, CZ) forms a valid stabilizer code. In quantum communications channels, the X errors, or bit-flip errors, and Z errors, or phase-flip errors, are typically correlated, but we ignore this correlation for CSS codes [15] and decode X and Z errors separately, using HX to decode Z errors and HZ to decode X errors.

23, no. 0, pp. 234–254, 2026. p. 0
Where the paper says it

Graphical Analysis of Lifted Product Code Constructions Ragnar Freij-Hollanti, Kirsten D. Morris, Patricija Šapokait˙e June 11, 2026 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.

[13] J. L. Gross and T. W. Tucker, Topological graph theory, Courier Corporation, 2001. p. 1

Where the paper says it

2 Preliminaries 2. 1 Graph Theory Tools Let n be a natural number and let [n] denote the set {1, 2, .

[14] A. R. Calderbank and P. p. 3

Where the paper says it

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) codes[14], constructed from two classical linear codes.

W. Shor, “Good quantum error-correcting codes exist,” Phys. p. 3
Where the paper says it

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) codes[14], constructed from two classical linear codes.

Rev. A, vol. 54, pp. 1098–1105, aug 1996.

[15] D. J. MacKay, G. Mitchison, and P. L. McFadden, “Sparse-graph codes for quantum error correction,” IEEE Transactions on Information Theory, vol. p. 3

Where the paper says it

v1 v2 c1 c2 P 0 P 1 P 1 P 0 v1,1 v1,2 v2,1 v2,2 c1,1 c1,2 c2,1 c2,2 Figure 1: A labeled protograph GA and its lift G ′ A from Ex. 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.

50, no. 10, pp. 2315–2330, 2004.

[16] H. V. Henderson and S. R. Searle, “The vec-permutation matrix, the vec operator and kronecker products: A review,” Linear and multilinear algebra, vol. p. 5

Where the paper says it

The graphs GHX and GHZ are isomorphic. The Kronecker product has the property that A ⊗ B = P(B ⊗ A)Q for some permutation matrices P and Q [16].

9, no. 4, pp. 271–288, 1981.

Conclusion

This work analyzes the structure of the Tanner graphs corresponding to HX and HZ for a particular case of the lifted product code construction. The authors provide conditions to ensure that the graph is connected, which is necessary to ensure robust graph-based iterative decoding. Future work includes further analysis on choosing the entries of the base matrix B to optimize the properties of the Tanner graph for well-performing iterative decoding. The paper is organized as follows.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Identify structural properties of quantum error-correcting codes by analyzing their Tanner graphs HX and HZ through isomorphism proofs, allowing for more robust analysis of decoding behavior and error floor performance.

  2. Determine connectivity conditions for lifted product codes based on permutation products along cycles in the base graph GBX, enabling the selection of base matrices B that guarantee connected Tanner graphs GHX.

  3. Characterize minimal absorbing sets for GBX by classifying them into left type, right type, and mixed type sets to understand how these combinatorial structures lift to the lifted graph GHX.

  4. Predict the girth of the lifted graph GHX for 2 times 2 base matrices over C2 by establishing that GHX has girth 8 if GHX is connected and using Theorem 3.7.

  5. Optimize design parameters for base matrices B by systematically choosing entries to ensure connectivity of GHX, maximize its girth, and minimize the number of minimal absorbing sets.

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 and H, 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 and H 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.

Sources

Related papers