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:2606.11987

Graphical Analysis of Lifted Product Code Constructions

Ragnar Freij-Hollanti, Kirsten D. Morris, Patricija Šapokaitė

Published Jun 10, 2026• 0 citations
arXivHTMLPDF

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.

DOI
10.48550/arxiv.2606.11987

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

Linear Time Iterative Decoders for Hypergraph-Product and Lifted-Product Codes

Asit Kumar Pradhan, Nithin Raveendran, Narayanan Rengaswamy +1 more

Quantum low-density parity-check (QLDPC) codes with asymptotically non-zero rates are prominent candidates for achieving fault-tolerant quantum computation, primarily due to the low operational depth of their syndrome-measurement circuits. Numerous studies advocate the necessity of fast decoders to fully harness the capabilities of QLDPC codes, thus driving the focus towards designing low-complexity iterative decoders. However, empirical investigations indicate that such iterative decoders are susceptible to having a high error floor when decoding QLDPC codes. The main objective of this paper is to analyze the decoding failures of thehypergraph-product(HGP) andlifted-product(LP) codes and to design decoders that mitigate these failures, thus achieving a reduced error floor. The suboptimal performance of these codes can predominantly be ascribed to two structural phenomena: (1) stabilizer-induced trapping sets (TS), which correspond to stabilizer-induced subgraphs in the Tanner graphs, and (2) classical trapping sets (TS), which originate from the classical codes used in the construction of HGP and LP codes. The dynamics of stabilizer-induced TSs are examined, and a straightforward modification of iterative decoders is proposed to circumvent these TSs. Moreover, this work proposes a systematic methodology for designing decoders that can circumvent the classical TSs in both HGP and LP codes by deriving them from decoders capable of avoiding the TSs in the parent classical LDPC codes. When decoders that can avoid stabilizer-induced TSs are run in parallel with those that can mitigate the effect of classical TSs, the logical error rate improves significantly in the error-floor region.

arXiv:2504.01728•IEEE Transactions on Information Theory•Apr 27, 2026•7 citations

Disassembling qLDPC codes for depth-optimal parity-check circuits

Minh T. P. Nguyen, Maximilian Rimbach-Russ, Stefano Bosco

Quantum low-density parity-check (qLDPC) codes offer a promising route to scalable fault-tolerant quantum computing, but their practical implementation requires efficient circuits for syndrome extraction. Many qLDPC families are assembled from a small set of components through explicit operations that imprint edge symmetries on their Tanner graphs. We show that disassembling the code by quotienting its symmetries one at a time, reduces parity-check circuit design to a much smaller problem acting only on the underlying components. Solutions to the reduced problem can then be lifted to the full code, yielding circuit constructions that apply to entire families of codes built from the same components. For lifted-product codes, our approach provides an optimal analytical construction for parity-check circuits achieving the lower bound on CNOT depth. We obtain analogous constructions for balanced-product codes and quantum--classical homological product codes. For quantum Tanner codes, the reduced problem is small enough to solve numerically, reaching the CNOT-depth lower bound for nearly all instance tested, including codes with up to 576 data qubits.

quant-pharXiv:2608.19917•Aug 21, 2026•2 citations

Quasi-Cyclic Qudit Lifted Product Codes with Almost Linear Minimum Distance

Shantom Kumar Borah, Abhinav Vaishya, V. Lalitha +3 more

Quantum low-density parity-check (QLDPC) codes are a promising route to fault-tolerant quantum computation with low overhead, and qudits offer advantages over qubits including more efficient information representation, improved magic state distillation, and richer algebraic structure for code design. Asymptotically good QLDPC codes arise from the lifted product (LP) construction with non-abelian lifts, but cyclic lifts remain attractive in practice because the resulting quasi-cyclic codes have circulant structure that hardware decoders exploit, which matters especially for non-binary decoders with costly check node operations. We introduce a qudit generalization of the LP construction over cyclic group algebras, which extends hypergraph product and LP codes to arbitrary prime-power dimensions and yields quasi-cyclic qudit CSS codes for every stacking order. We bound encoding rates via a connection to additive codes, and show that in the fully stacked case, qudit LP codes built from lifted Tanner codes on expander graphs form families with $Θ(\log N)$ logical qudits and almost linear minimum distance $Θ(N/\log N)$, via a distance bound that holds for a general class of LP factors. We also study an additive decoder for general qudit codes and a linear merged-syndrome decoder for fully stacked codes. Monte Carlo simulations under a depolarizing channel with equal symbol error probability show that qudit codes achieve lower frame error rates than comparable qubit codes, and that the linear decoder gives further gains for fully stacked codes.

arXiv:2611.15952•Nov 11, 2026•0 citations

Lifting Lifted Product Codes

Yuta Hirasaki, Jong Yeon Lee

Lifted product (LP) codes form an important class of quantum error correcting codes with favorable code parameters. We introduce a systematic construction of LP code families based on group extensions and graph lifts. The construction increases the code size while preserving the local structure of the Tanner graph, and relates code parameters, logical operators, and fault-tolerant logical-operation gadgets within the families through chain and cochain maps. As a first application, we obtain LP codes with better code parameters than previously reported ones. We then demonstrate that code-surgery gadgets can be transferred across the selected finite lifts through chain maps and, in several cases, implemented with lower space overhead. We also develop parallel product surgery for lifted clustered cyclic codes. Finally, we propose lifting as a systematic first step toward defining thermodynamic families for algebraically defined qLDPC codes without an underlying Euclidean lattice. For several base codes and selected lifts, coherent information exhibits finite-size crossings, while our results also indicate that additional conditions are needed to determine a unique family.

quant-pharXiv:2607.28621•Jul 31, 2026•7 citations

The Minimal Product Parity Check Matrix and Its Application

Morteza Esmaeili

In decoding a linear block code C by iterative decoding algorithms, these algorithms are essentially applied on a graphical representation of C such as Tanner graph and factor graph. Due to the impact of the structure of these graphs on the performance of code, we consider minimal parity check matrices(matrices with minimum number of nonzero entries) of product codes. An algorithm constructing such matrices is given. It turns out that under the given construction method, product coding technique is indeed a powerful method to construct irregular LDPC codes. Given two codes A and B, the construction method produces a Tanner graph with girth g := min {8, ga, gb} for the product code A ⊗ B, where ga and gb are the girth of Tanner graphs representing A and B, respectively. Simulation results confirm the positive practical impact of the minimality of the parity check matrices.

International Conference on Communications•Jun 1, 2006•4 citations
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 HXH_{\mathsf{X}}HX​ and HZH_{\mathsf{Z}}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 HXH_{\mathsf{X}}HX​ and HZH_{\mathsf{Z}}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.
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.
Quantum low-density parity-check (QLDPC) codes with asymptotically non-zero rates are prominent candidates for achieving fault-tolerant quantum computation, primarily due to the low operational depth of their syndrome-measurement circuits. Numerous studies advocate the necessity of fast decoders to fully harness the capabilities of QLDPC codes, thus driving the focus towards designing low-complexity iterative decoders. However, empirical investigations indicate that such iterative decoders are susceptible to having a high error floor when decoding QLDPC codes. The main objective of this paper is to analyze the decoding failures of thehypergraph-product(HGP) andlifted-product(LP) codes and to design decoders that mitigate these failures, thus achieving a reduced error floor. The suboptimal performance of these codes can predominantly be ascribed to two structural phenomena: (1) stabilizer-induced trapping sets (TS), which correspond to stabilizer-induced subgraphs in the Tanner graphs, and (2) classical trapping sets (TS), which originate from the classical codes used in the construction of HGP and LP codes. The dynamics of stabilizer-induced TSs are examined, and a straightforward modification of iterative decoders is proposed to circumvent these TSs. Moreover, this work proposes a systematic methodology for designing decoders that can circumvent the classical TSs in both HGP and LP codes by deriving them from decoders capable of avoiding the TSs in the parent classical LDPC codes. When decoders that can avoid stabilizer-induced TSs are run in parallel with those that can mitigate the effect of classical TSs, the logical error rate improves significantly in the error-floor region.
Quantum low-density parity-check (qLDPC) codes offer a promising route to scalable fault-tolerant quantum computing, but their practical implementation requires efficient circuits for syndrome extraction. Many qLDPC families are assembled from a small set of components through explicit operations that imprint edge symmetries on their Tanner graphs. We show that disassembling the code by quotienting its symmetries one at a time, reduces parity-check circuit design to a much smaller problem acting only on the underlying components. Solutions to the reduced problem can then be lifted to the full code, yielding circuit constructions that apply to entire families of codes built from the same components. For lifted-product codes, our approach provides an optimal analytical construction for parity-check circuits achieving the lower bound on CNOT depth. We obtain analogous constructions for balanced-product codes and quantum--classical homological product codes. For quantum Tanner codes, the reduced problem is small enough to solve numerically, reaching the CNOT-depth lower bound for nearly all instance tested, including codes with up to 576 data qubits.
Quantum low-density parity-check (QLDPC) codes are a promising route to fault-tolerant quantum computation with low overhead, and qudits offer advantages over qubits including more efficient information representation, improved magic state distillation, and richer algebraic structure for code design. Asymptotically good QLDPC codes arise from the lifted product (LP) construction with non-abelian lifts, but cyclic lifts remain attractive in practice because the resulting quasi-cyclic codes have circulant structure that hardware decoders exploit, which matters especially for non-binary decoders with costly check node operations. We introduce a qudit generalization of the LP construction over cyclic group algebras, which extends hypergraph product and LP codes to arbitrary prime-power dimensions and yields quasi-cyclic qudit CSS codes for every stacking order. We bound encoding rates via a connection to additive codes, and show that in the fully stacked case, qudit LP codes built from lifted Tanner codes on expander graphs form families with Θ(log⁡N)Θ(\log N)Θ(logN) logical qudits and almost linear minimum distance Θ(N/log⁡N)Θ(N/\log N)Θ(N/logN), via a distance bound that holds for a general class of LP factors. We also study an additive decoder for general qudit codes and a linear merged-syndrome decoder for fully stacked codes. Monte Carlo simulations under a depolarizing channel with equal symbol error probability show that qudit codes achieve lower frame error rates than comparable qubit codes, and that the linear decoder gives further gains for fully stacked codes.
Lifted product (LP) codes form an important class of quantum error correcting codes with favorable code parameters. We introduce a systematic construction of LP code families based on group extensions and graph lifts. The construction increases the code size while preserving the local structure of the Tanner graph, and relates code parameters, logical operators, and fault-tolerant logical-operation gadgets within the families through chain and cochain maps. As a first application, we obtain LP codes with better code parameters than previously reported ones. We then demonstrate that code-surgery gadgets can be transferred across the selected finite lifts through chain maps and, in several cases, implemented with lower space overhead. We also develop parallel product surgery for lifted clustered cyclic codes. Finally, we propose lifting as a systematic first step toward defining thermodynamic families for algebraically defined qLDPC codes without an underlying Euclidean lattice. For several base codes and selected lifts, coherent information exhibits finite-size crossings, while our results also indicate that additional conditions are needed to determine a unique family.
In decoding a linear block code C by iterative decoding algorithms, these algorithms are essentially applied on a graphical representation of C such as Tanner graph and factor graph. Due to the impact of the structure of these graphs on the performance of code, we consider minimal parity check matrices(matrices with minimum number of nonzero entries) of product codes. An algorithm constructing such matrices is given. It turns out that under the given construction method, product coding technique is indeed a powerful method to construct irregular LDPC codes. Given two codes A and B, the construction method produces a Tanner graph with girth g := min {8, ga, gb} for the product code A ⊗ B, where ga and gb are the girth of Tanner graphs representing A and B, respectively. Simulation results confirm the positive practical impact of the minimality of the parity check matrices.