Graphical Analysis of Lifted Product Code Constructions
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 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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 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
.Where the paper says it
Where the paper says it
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 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.Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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.Where the paper says it
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 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. 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. 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]. 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]. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
References
[1] D. Gottesman, “Fault-tolerant quantum computation with constant overhead,” Quantum Inform. p. 0 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]. 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].Where the paper says it
Where the paper says it
[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 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.Where the paper says it
[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 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.Where the paper says it
[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 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.Where the paper says it
[5] L. Dolecek, D. p. 1 An important combinatorial invariant of a Tanner graph is its
absorbing sets. These were first introduced by Dolecek et. 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.Where the paper says it
Where the paper says it
[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 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. 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.Where the paper says it
Where the paper says it
[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 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].Where the paper says it
[9] N. Raveendran, D. Declercq, and B. Vasić, “On the minimum distances of finite-length lifted product quantum LDPC codes,” 2025. p. 0 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].Where the paper says it
[10] R. Tanner, “A recursive approach to low complexity codes,” IEEE Transactions on Information Theory, vol. p. 0 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.Where the paper says it
[11] L. Dolecek, Z. p. 1 An important combinatorial invariant of a Tanner graph is its
absorbing sets. These were first introduced by Dolecek et. 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.Where the paper says it
Where the paper says it
[12] K. D. Morris, T. Pllaha, and C. A. Kelley, “Absorbing sets in quantum LDPC codes,” Advances in Mathematics of Communications, vol. p. 3 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. 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.Where the paper says it
Where the paper says it
[13] J. L. Gross and T. W. Tucker, Topological graph theory, Courier Corporation, 2001. p. 1 2 Preliminaries
2. 1 Graph Theory Tools
Let n be a natural number and let [n] denote the set {1, 2, .Where the paper says it
[14] A. R. Calderbank and P. p. 3 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. 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.Where the paper says it
Where the paper says it
[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 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.Where the paper says it
[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 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].Where the paper says it
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
-
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.
-
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.
-
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.
-
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. -
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
- The Gaussian Multiuser Channel Capacity Region
- The mathematical landscape of partial information decomposition: A comprehensive review of properties and measures
- Electromagnetic Signal and Information Theory: A Continuous-Aperture Array Perspective
- Analytically Characterized Optimal Power Control for Signal-Level-Integrated Sensing, Computing and Communication in Federated Learning
- Information Spectrum Methods for Multiple-Access Channels--Part I: epsilon-Capacity Regions in the Mixed Gaussian Case
- Seed Recycling: Explicit Codes for Mixed Synchronization Errors Matching the Leading Term of the Gilbert--Varshamov Bound