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

IEEE International Symposium on Information Theory (ISIT)

An Efficient Algorithm to Sample Dual-Containing Low-Density Parity-Check Codes

Paolo Santini

Published Jun 1, 2026• 0 citations
Publisher

Abstract

In this paper, we present an efficient algorithm to sample a random, sparse rectangular matrix H such that HH⊤= 0. Such matrices can be used, for instance, to define dual containing Low-Density Parity-Check (LDPC) codes, which are useful for building quantum codes according to the Calderbank-Shor-Steane (CSS) construction. Differently from existing works, we do not start from any strong algebraic structure but aim to obtain a matrix H as random as possible. We do this by sampling the matrix row by row, enforcing that each new row is orthogonal to all the rows we have already found. Technically, this is done by searching for a low weight codeword in the dual of the space generated by the already found rows. Interestingly, to efficiently find such a codeword, we rely on Information Set Decoding (ISD), which is a technique used for the cryptanalysis of code-based cryptosystems. We show that, when the desired row weight for H is low enough, our algorithm is likely to succeed and run efficiently; numerical simulations confirm the efficiency and effectiveness of our approach.

DOI
10.1109/isit62367.2026.11653937

Related papers

An Efficient Algorithm to Sample Quantum Low-Density Parity-Check Codes

Paolo Santini

In this paper, we present an efficient algorithm to sample random sparse matrices to be used as check matrices for quantum Low-Density Parity-Check (LDPC) codes. To ease the treatment, we mainly describe our algorithm as a technique to sample a dual-containing binary LDPC code, hence, a sparse matrix $\mathbf H\in\mathbb F_2^{r\times n}$ such that $\mathbf H\mathbf H^\top = \mathbf 0$. However, as we show, the algorithm can be easily generalized to sample dual-containing LDPC codes over non binary finite fields as well as more general quantum stabilizer LDPC codes. While several constructions already exist, all of them are somewhat algebraic as they impose some specific property (e.g., the matrix being quasi-cyclic). Instead, our algorithm is purely combinatorial as we do not require anything apart from the rows of $\mathbf H$ being sparse enough. In this sense, we can think of our algorithm as a way to sample sparse, self-orthogonal matrices that are as random as possible. Our algorithm is conceptually very simple and, as a key ingredient, uses Information Set Decoding (ISD) to sample the rows of $\mathbf H$, one at a time. The use of ISD is fundamental as, without it, efficient sampling would not be feasible. We give a theoretical characterization of our algorithm, determining which ranges of parameters can be sampled as well as the expected computational complexity. Numerical simulations and benchmarks confirm the feasibility and efficiency of our approach.

arXiv:2601.08387•Jan 13, 2026•0 citations

Construction of Quantum LDPC Codes From Classical Row-Circulant QC-LDPCs

Zunaira Babar, Panagiotis Botsinis, Dimitrios Alanis +2 more

Classical row-circulant quasi-cyclic (QC) low-density parity check (LDPC) matrices are known to generate efficient high-rate short and moderate-length QC-LDPC codes, while the comparable random structures exhibit numerous short cycles of length-4. Therefore, we conceive a general formalism for constructing nondual-containing Calderbank-Shor-Steane (CSS)-type quantum low-density parity check (QLDPC) codes from arbitrary classical row-circulant QC-LDPC matrices. We apply our proposed formalism to the classical balanced incomplete block design (BIBD)-based row-circulant QC-LDPC codes for demonstrating that our designed codes outperform their dual-containing CSS-type counterparts as well as the entanglement-assisted (EA)-QLDPC codes.

IEEE Communications Letters•Dec 10, 2015•18 citations

Quantum Quasi-Cyclic Low-Density Parity-Check Codes

Min-Hsiu Hsieh, Todd A. Brun, Igor Devetak

We investigate the construction of quantum low-density parity-check (LDPC) codes from classical quasi-cyclic (QC) LDPC codes with girth greater than or equal to 6. We have shown that the classical codes in the generalized Calderbank-Shor-Steane (CSS) construction do not need to satisfy the dual-containing property as long as pre-shared entanglement is available to both sender and receiver. We can use this to avoid the many 4-cycles which typically arise in dual-containing LDPC codes. The advantage of such quantum codes comes from the use of efficient decoding algorithms such as sum-product algorithm (SPA). It is well known that in the SPA, cycles of length 4 make successive decoding iterations highly correlated and hence limit the decoding performance. We show the principle of constructing quantum QC-LDPC codes which require only small amounts of initial shared entanglement.

•Mar 2, 2008•8 citations

Design of near-optimum quantum error-correcting codes based on generator and parity-check matrices of LDGM codes

Javier Garcia‐Frias, Kejing Liu

We study the design of near-optimum quantum error correcting codes based on the use of sparse matrices. The basic idea is to construct a Calderbank-Shor-Steane (CSS) code based on the generator and parity-check matrices of a classical channel code with low density generator matrix (LDGM code), which is designed with a specific structure inspired in the parallel concatenation of regular LDGM codes. Then, row operations are performed in both matrices to achieve the desired quantum rate. Decoding is performed in an iterative manner, by applying message passing over the corresponding graphs. The proposed codes allow greater flexibility and are easier to design than existing sparse-graph quantum codes, while leading to better performance.

Conference on Information Sciences and Systems•Mar 1, 2008•14 citations

Approach for the construction of non-Calderbank-Steane-Shor low-density-generator-matrix–based quantum codes

Patricio Fuentes, Josu Etxezarreta Martínez, Pedro M. Crespo +1 more

Quantum low-density generator matrix (QLDGM) codes based on Calderbank-Steane-Shor (CSS) constructions have shown unprecedented error correction capabilities, displaying much improved performance in comparison to other sparse-graph codes. However, the nature of CSS designs and the manner in which they must be decoded limit the performance that is attainable with codes that are based on this construction. This motivates the search for quantum code design strategies capable of avoiding the drawbacks associated with CSS codes. In this article, we introduce non-CSS quantum code constructions based on classical LDGM codes. The proposed codes are derived from CSS QLDGM designs by performing specific row operations on their quantum parity check matrices to modify the associated decoding graphs. The application of this method results in performance improvements in comparison to CSS QLDGM codes, while also allowing for greater flexibility in the design process. The proposed non-CSS QLDGM scheme outperforms the best quantum low-density parity check codes that have appeared in the literature.

Physical Review A•Jul 22, 2020•18 citations

Design and Analysis of Quantum Dual-Containing CSS LDPC Codes based on Quasi-Dyadic Matrices

Alessio Baldelli, Marco Baldi, Massimo Battaglioni +2 more

Quantum error correcting codes are essential to achieve fault-tolerant quantum computation. This work introduces two constructions of high-rate, dual-containing (DC) Calderbank--Shor--Steane low-density parity-check (LDPC) codes based on quasi-dyadic matrices. We characterize the automorphism group of such codes, investigate their minimum distance behavior, and provide several theoretical results on their cycle properties. Monte Carlo simulations under depolarizing and phenomenological noise show better finite-length logical error rates than the considered DC benchmark codes and competitive performance against several state-of-the-art quantum LDPC code families. Finally, we employ an automorphism-ensemble belief propagation decoder to improve their decoding performance.

cs.ITCross-listedarXiv:2605.03631•May 6, 2026•3 citations
In this paper, we present an efficient algorithm to sample a random, sparse rectangular matrix H such that HH⊤= 0. Such matrices can be used, for instance, to define dual containing Low-Density Parity-Check (LDPC) codes, which are useful for building quantum codes according to the Calderbank-Shor-Steane (CSS) construction. Differently from existing works, we do not start from any strong algebraic structure but aim to obtain a matrix H as random as possible. We do this by sampling the matrix row by row, enforcing that each new row is orthogonal to all the rows we have already found. Technically, this is done by searching for a low weight codeword in the dual of the space generated by the already found rows. Interestingly, to efficiently find such a codeword, we rely on Information Set Decoding (ISD), which is a technique used for the cryptanalysis of code-based cryptosystems. We show that, when the desired row weight for H is low enough, our algorithm is likely to succeed and run efficiently; numerical simulations confirm the efficiency and effectiveness of our approach.
In this paper, we present an efficient algorithm to sample random sparse matrices to be used as check matrices for quantum Low-Density Parity-Check (LDPC) codes. To ease the treatment, we mainly describe our algorithm as a technique to sample a dual-containing binary LDPC code, hence, a sparse matrix H∈F2r×n\mathbf H\in\mathbb F_2^{r\times n}H∈F2r×n​ such that HH⊤=0\mathbf H\mathbf H^\top = \mathbf 0HH⊤=0. However, as we show, the algorithm can be easily generalized to sample dual-containing LDPC codes over non binary finite fields as well as more general quantum stabilizer LDPC codes. While several constructions already exist, all of them are somewhat algebraic as they impose some specific property (e.g., the matrix being quasi-cyclic). Instead, our algorithm is purely combinatorial as we do not require anything apart from the rows of H\mathbf HH being sparse enough. In this sense, we can think of our algorithm as a way to sample sparse, self-orthogonal matrices that are as random as possible. Our algorithm is conceptually very simple and, as a key ingredient, uses Information Set Decoding (ISD) to sample the rows of H\mathbf HH, one at a time. The use of ISD is fundamental as, without it, efficient sampling would not be feasible. We give a theoretical characterization of our algorithm, determining which ranges of parameters can be sampled as well as the expected computational complexity. Numerical simulations and benchmarks confirm the feasibility and efficiency of our approach.
Classical row-circulant quasi-cyclic (QC) low-density parity check (LDPC) matrices are known to generate efficient high-rate short and moderate-length QC-LDPC codes, while the comparable random structures exhibit numerous short cycles of length-4. Therefore, we conceive a general formalism for constructing nondual-containing Calderbank-Shor-Steane (CSS)-type quantum low-density parity check (QLDPC) codes from arbitrary classical row-circulant QC-LDPC matrices. We apply our proposed formalism to the classical balanced incomplete block design (BIBD)-based row-circulant QC-LDPC codes for demonstrating that our designed codes outperform their dual-containing CSS-type counterparts as well as the entanglement-assisted (EA)-QLDPC codes.
We investigate the construction of quantum low-density parity-check (LDPC) codes from classical quasi-cyclic (QC) LDPC codes with girth greater than or equal to 6. We have shown that the classical codes in the generalized Calderbank-Shor-Steane (CSS) construction do not need to satisfy the dual-containing property as long as pre-shared entanglement is available to both sender and receiver. We can use this to avoid the many 4-cycles which typically arise in dual-containing LDPC codes. The advantage of such quantum codes comes from the use of efficient decoding algorithms such as sum-product algorithm (SPA). It is well known that in the SPA, cycles of length 4 make successive decoding iterations highly correlated and hence limit the decoding performance. We show the principle of constructing quantum QC-LDPC codes which require only small amounts of initial shared entanglement.
We study the design of near-optimum quantum error correcting codes based on the use of sparse matrices. The basic idea is to construct a Calderbank-Shor-Steane (CSS) code based on the generator and parity-check matrices of a classical channel code with low density generator matrix (LDGM code), which is designed with a specific structure inspired in the parallel concatenation of regular LDGM codes. Then, row operations are performed in both matrices to achieve the desired quantum rate. Decoding is performed in an iterative manner, by applying message passing over the corresponding graphs. The proposed codes allow greater flexibility and are easier to design than existing sparse-graph quantum codes, while leading to better performance.
Quantum low-density generator matrix (QLDGM) codes based on Calderbank-Steane-Shor (CSS) constructions have shown unprecedented error correction capabilities, displaying much improved performance in comparison to other sparse-graph codes. However, the nature of CSS designs and the manner in which they must be decoded limit the performance that is attainable with codes that are based on this construction. This motivates the search for quantum code design strategies capable of avoiding the drawbacks associated with CSS codes. In this article, we introduce non-CSS quantum code constructions based on classical LDGM codes. The proposed codes are derived from CSS QLDGM designs by performing specific row operations on their quantum parity check matrices to modify the associated decoding graphs. The application of this method results in performance improvements in comparison to CSS QLDGM codes, while also allowing for greater flexibility in the design process. The proposed non-CSS QLDGM scheme outperforms the best quantum low-density parity check codes that have appeared in the literature.
Quantum error correcting codes are essential to achieve fault-tolerant quantum computation. This work introduces two constructions of high-rate, dual-containing (DC) Calderbank--Shor--Steane low-density parity-check (LDPC) codes based on quasi-dyadic matrices. We characterize the automorphism group of such codes, investigate their minimum distance behavior, and provide several theoretical results on their cycle properties. Monte Carlo simulations under depolarizing and phenomenological noise show better finite-length logical error rates than the considered DC benchmark codes and competitive performance against several state-of-the-art quantum LDPC code families. Finally, we employ an automorphism-ensemble belief propagation decoder to improve their decoding performance.