Exact Fold-and-Lift Enumeration of Low-Weight Codewords in Quasi-Cyclic Codes with Circulant Size π¦π β ππ: Theory, Algorithms, Certificates and Verification
We give an exact method for enumerating every codeword of weight at most W in the kernel of a block matrix over S[x]/(xM+1), where S is a commutative GF(2)-algebra with a fixed basis and M = m0Β·2L. The class contains quasi-cyclic codes of any index, block-circulant matrices with several block rows, generalized and bivariate bicycle codes, and two-block group-algebra codes over abelian groups with a cyclic factor of order m0Β·2L. The method rests on x2m+1 = (xm+1)2 in characteristic two: the kernel folds onto half the length without increasing weight, and every low-weight word is recovered exactly from its fold. The paper proves the recursion in this generality, reduces it to one representative per symmetry orbit, specifies the lift step in full, proves every implementation step and the whole algorithm correct, gives a dimension formula (k = 2 deg gcd(ru, rv, xm+1) for two-block CSS codes) and a certified-distance procedure for CSS codes, degenerate ones included, with certificates checkable by a proof assistant, and a random-code heuristic that predicts where the cost concentrates. A worked [[24,4,4]] example and a case study at length 832 are included: the method certifies d = 15 for a [[832,10]] code in about one second per sector, three separately written implementations agree, and the dimension formula explains the whole tower and proves k = 10. Code. The reference implementation, the tests and the example scripts are in the companion record doi:10.5281/zenodo.23466024. Related records. Case study paper v2.1: doi:10.5281/zenodo.23466181 (version 1.0: doi:10.5281/zenodo.23327681). Verification bundle 1.2.2: doi:10.5281/zenodo.23463892. License. CC BY 4.0. Copyright (c) 2026 Guillaume Lessard.
We give an exact method for enumerating every codeword of weight at most W in the kernel of a block matrix over S[x]/(xM+1), where S is a commutative GF(2)-algebra with a fixed basis and M = m0Β·2L. The class contains quasi-cyclic codes of any index, block-circulant matrices with several block rows, generalized and bivariate bicycle codes, and two-block group-algebra codes over abelian groups with a cyclic factor of order m0Β·2L. The method rests on x2m+1 = (xm+1)2 in characteristic two: the kernel folds onto half the length without increasing weight, and every low-weight word is recovered exactly from its fold. The paper proves the recursion in this generality, reduces it to one representative per symmetry orbit, specifies the lift step in full, proves every implementation step and the whole algorithm correct, gives a dimension formula (k = 2 deg gcd(ru, rv, xm+1) for two-block CSS codes) and a certified-distance procedure for CSS codes, degenerate ones included, with certificates checkable by a proof assistant, and a random-code heuristic that predicts where the cost concentrates. A worked [[24,4,4]] example and a case study at length 832 are included: the method certifies d = 15 for a [[832,10]] code in about one second per sector, three separately written implementations agree, and the dimension formula explains the whole tower and proves k = 10. Code. The reference implementation, the tests and the example scripts are in the companion record doi:10.5281/zenodo.23466024. Related records. Case study paper v2.1: doi:10.5281/zenodo.23466181 (version 1.0: doi:10.5281/zenodo.23327681). Verification bundle 1.2.2: doi:10.5281/zenodo.23463892. License. CC BY 4.0. Copyright (c) 2026 Guillaume Lessard.
We determine the exact minimum distance of a two-block quasi-cyclic CSS quantum LDPC code with n = 832 physical qubits and k = 10 logical qubits (genus5 GB CLEAN, QECTOR artifact lineage). Earlier releases had established 10 β€ d β€ 15. We prove d = 15: in each CSS sector the classical kernel contains no nonzero word of weight 1 to 14 and exactly 416 words of weight 15, forming a single orbit under simultaneous cyclic shifts, all of them nontrivial logical operators. The proof uses the repeated-root structure of the kernel over F2[x]/(x^416 + 1): since 416 = 13Β·2^5 and x^(2m) + 1 = (x^m + 1)^2 over F2, the kernel folds exactly to a 26-bit code and lifts back without loss, giving an exact, symmetry-reduced enumeration of low-weight words. An 18-check validation suite passes, a separately written re-implementation reproduces every intermediate count, and both implementations show that no kernel word has weight 16 to 20. Computer-assisted proof, not formally verified. Version 2.1 supersedes version 1.0 (version 2.0 was an internal revision, not released). Changes: summary box, notation table, algorithm listing and pipeline figure; narrower novelty statement, related-work section and 20 additional references, independent re-implementation, extended enumeration to weight 20, full re-run for bundle release 1.2.2, corrected availability statement. Results unchanged. The code specification is published in Appendix C, and the verification bundle, with machine-checked proofs of the upper bound, is public (doi:10.5281/zenodo.23463892).
Quantum Bicycle LDPC Codes with High kd2/n from Divisor-Driven Search
Bicycle (two-block circulant) quantum low-density parity-check (LDPC) codes include some of the best known small quantum codes, yet their design has relied on group-algebra formulations in which the dimension and distance are accessible only through matrix computation. We show that in the cyclic case the construction collapses into the polynomial ring $\F_2[x]/(x^{l}-1)$: self-orthogonality is automatic, the quantum dimension is read off from a polynomial gcd, and the minimum distance is certified exactly through the Calderbank correspondence to additive codes over $\F_4$, turning code search into an algebraically pre-filtered enumeration that reaches parameter regimes poorly covered by existing tables. A computer search based on this framework recovers the short codes [[42,12,4]]2β and [[62,12,4]]2β and produces a family of codes with competitive figure of merit kd2/n, including [[66,20,7]]2β with kd2/n=14.85, above the bivariate bicycle code [[144,12,12]]2β (kd2/n=12) at less than half the block length, together with [[46,2,8]]2β, [[66,2,9]]2β, [[66,4,8]]2β, [[66,6,8]]2β and, at n=90, [[90,16,6]]2β, [[90,18,6]]2β, [[90,20,6]]2β. An exhaustive census at n=48 delineates the boundary of this picture: we exhibit a [[48,10,6]]2β code from a minimal 48-element group (the Aydin--Tamo--Barg realization uses 72 elements), and prove that distance 5 forces a stabilizer-rank loss, which excludes [[48,10,5]]2β from the weight-8 symmetric coset family. The framework thus opens a systematic route to bicycle-type quantum LDPC codes beyond the reach of group-theoretic searches, and identifies exactly where genuinely coset-theoretic phenomena begin.
We determine the exact minimum distance of a two block quasi cyclic CSS code with 832 physical and 10 logical qubits. Earlier work had shown 10 β€ d β€ 15. We close the interval and prove d = 15. In each CSS sector the classical kernel has no nonzero word of weight 1 to 14 and exactly 416 words of weight 15, one orbit under cyclic shifts, all of them nontrivial logical operators. The proof uses the identity x^(2m) + 1 = (x^m + 1)^2 over GF(2). Since 416 = 13 Β· 2^5, the kernel folds down to a 26 bit code and lifts back exactly, so all low weight words can be enumerated level by level in about one second per sector. The paper gives the full proofs, the results, an 18 check validation suite, and the limits: this is a computer assisted proof, not a formally verified one. The code matrices and source files are not part of this record. They are held in a separate restricted record [restricted record link], and SHA256 digests in the paper pin every file.
Quasi-cyclic low-density parity-check (QC-LDPC) codes based on protographs are of great interest to code designers because analysis and implementation are facilitated by the protograph structure and the use of circulant permutation matrices for protograph lifting. However, these restrictions impose undesirable fixed upper limits on important code parameters, such as minimum distance and girth. In this paper, we consider an approach to constructing QC-LDPC codes that uses a two-step lifting procedure based on a protograph, and, by following this method instead of the usual one-step procedure, we obtain improved minimum distance and girth properties. We also present two new design rules for constructing good QC-LDPC codes using this two-step lifting procedure, and in each case we obtain a significant increase in minimum distance and achieve a certain guaranteed girth compared to one-step circulant-based liftings. The expected performance improvement is verified by simulation results.
Quasi-cyclic low-density parity-check (QC-LDPC) codes based on protographs are of great interest to code designers because analysis and implementation are facilitated by the protograph structure and the use of circulant permutation matrices for protograph lifting. However, these restrictions impose undesirable fixed upper limits on important code parameters, such as minimum distance and girth. In this paper, we consider an approach to constructing QC-LDPC codes that uses a two-step lifting procedure based on a protograph, and, by following this method instead of the usual one-step procedure, we obtain improved minimum distance and girth properties. We also present two new design rules for constructing good QC-LDPC codes using this two-step lifting procedure, and in each case, we obtain a significant increase in minimum distance and achieve a certain guaranteed girth compared with one-step circulant-based liftings. The expected performance improvement is verified by simulation results.