CS Paper Radar

High-Girth QLDPC Codes from Circulant and Affine Permutation Matrices

Vahid Nourozi, Roxana Smarandache, David G. M. Mitchell†

cs.IT math.QA ·submitted 2026-10-14 02:37 UTC · v1

Abstract

We study two explicit constructions of binary Calderbank--Shor--Steane quantum low-density parity-check (QLDPC) codes with check weight six. The first uses a fixed circulant shift pattern and yields parameters $\code{6N}{2N+2}{6}$ with Tanner graph girth twelve for $N=31$ and every $N\ge37$. A graph incidence interpretation gives the ranks and girths, and a uniform weight six logical operator establishes the exact distance. The second construction uses fixed matrix polynomials with circulant and affine permutation coefficients. Here, a polynomial commutation identity guarantees orthogonality for every cyclic lift. Four realizations give $[[192,16,8]]$, $[[288,16,12]]$, $[[384,16,14]]$, and $[[576,32,20]]$, with Tanner girth eight and computationally certified distances. We give reproducible construction data, distinguish classical cycle distance from quantum distance, and identify the limitations of both families.

Closest papers

Nearest neighbours by meaning across the whole index.

Quantum bivariate bicycle codes with weight-8 checks surpassing the BB benchmark

cs.IT quant-ph ·2026-09-06 ·Liangdong Lu, Ruipan Yang, Guanmin Guo
benchmarktheory similarity 0.79
Abstract

Bivariate bicycle (BB) codes of Bravyi \emph{et al.}~\cite{Bravyi2024} are quantum low-density parity-check codes with weight-$6$ checks, exemplified by $[[144,12,12]]$ with $kd^2/n=12$. We develop the algebraic structure theory of BB-type codes with weight-$8$ checks (weight-$4$ generator polynomials) and use it, together with an exactly validated search pipeline, to construct and certify new codes. We prove an exact dimension formula $k=2\dim R/(A,B)$ (forcing even $k$), a $4\ell m$-element symmetry group on generator pairs, an $X/Z$ distance equality $d_X=d_Z$, and a family of subgroup-coset kernel vectors giving rigorous distance upper bounds and a design rule for high-distance constructions; all distances are computed exhaustively by a cross-validated bit-mask verifier. At $n=144$ the pipeline returns a census of $53$ codes whose strongest members surpass the BB benchmark: $[[144,6,d\ge 15]]$ exceeds the benchmark distance $12$ (certified $d\ge 15$), $[[144,10,12]]$ reaches it with weight-$8$ checks, and $[[144,16,10]]$ encodes a third more logical qubits at $kd^2/n=11.11$ ($7.4\%$ below benchmark) while decoding no worse. At $n=72$, $[[72,14,8]]$ attains $kd^2/n=12.44$---more than twice the same-length BB code---and decodes better; a circuit-level memory experiment places our weight-$8$ codes at $\approx 0.1\%$ pseudo-threshold versus $\approx 0.4\%$ for the BB reference under an identical model, quantifying the threshold cost of the heavier checks. All structural statements are verified numerically on the whole census.

0.16

Quantum Bicycle LDPC Codes with High $kd^2/n$ from Divisor-Driven Search

cs.IT quant-ph ·2026-08-10 ·Liangdong Lu, Guanmin Guo, Yang Liu, Ruipan Yang
similarity 0.77
Abstract · v2: Added references on decoding comparison

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 $kd^2/n$, including $[[66,20,7]]_2$ with $kd^2/n=14.85$, above the bivariate bicycle code $[[144,12,12]]_2$ ($kd^2/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.

0.32

Lifted-Product QLDPC Codes in the Polynomial Domain

cs.IT ·2026-09-01 ·Vahid Nourozi, Mohsen Moradi, Roxana Smarandache, David G. M. Mitchell
benchmark similarity 0.74
Abstract

This paper presents a finite-length polynomial-domain formulation of lifted-product quantum low-density parity-check (QLDPC) codes. We formulate the code construction over the quotient ring F 2[D]/(D L + 1), where polynomial base matrices are lifted entrywise to binary circulant blocks. This representation gives a compact algebraic description of the lifted-product parity-check matrices and allows CSS orthogonality to be analyzed before binary expansion. We show that the standard circulant lifting map is compatible with polynomial conjugation, which implies that the resulting binary matrices satisfy the CSS commutation constraint. The construction is illustrated with a constraint length 7, rate 1/2 NASA convolutional code example, and numerical examples are provided from a 3 x 4 polynomial parity-check matrix. The finite-length performance of selected constructed codes is then evaluated over the depolarizing channel using various benchmark decoders. The resulting framework gives a structured method to construct finite-length lifted-product QLDPC codes from small polynomial base matrices.

0.28

Low-Density Parity-Check Codes of High Girth from Permutation Polynomials

cs.IT ·2026-10-02 ·Tasawwar Hussain, Anthony Gómez-Fonseca, Tefjol Pllaha
similarity 0.73
Abstract · 6 pages, 1 figure

Quasi-cyclic low-density parity-check (QC-LDPC) codes are widely used in modern communication standards due to their simple structure and efficient encoder and decoder implementations. However, the commutativity of the circulant permutation matrices used in their construction significantly limits their girth and minimum distance, affecting iterative decoding performance. In this paper, we investigate protograph-based codes constructed using permutation polynomials of higher degree, focusing on a closed family of non-commuting binomial permutation polynomials that enables these constructions to exceed both of these girth and minimum distance upper bounds while maintaining a simple representation. Simulation results demonstrate improved decoding performance compared to constructions based on affine permutation polynomials, which include QC-LDPC codes.

0.15

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

cs.IT quant-ph ·2026-11-11 ·Shantom K. Borah, Abhinav Vaishya, V. Lalitha, Asit Kumar Pradhan, Bane Vasic +1 more
similarity 0.71
Abstract · 43 pages, 6 figures

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.

0.24

CPM-LDPC Codes Attaining the Minimum-Distance Bound

cs.IT ·2026-09-15 ·Kenta Kasai
theorycode/data similarity 0.70
Abstract · 13 pages, 1 figure, 2 tables. Verification code and data: https://github.com/kasaikenta/cpm-ldpc-distance

We study binary quasi-cyclic LDPC codes whose parity-check matrices are full arrays of single circulant permutation matrices (CPMs), referred to here as CPM-LDPC codes. Their minimum distance is at most $(J+1)!$, where $J$ is the column weight. For every fixed pair of column and row weights $2\le J<L$, we show that this bound is attained for all sufficiently large integer lift sizes. First, we give one integer exponent matrix independent of the lift size $P$. Second, we show that independent uniform exponent choices attain the bound with probability $1-O_{J,L}(P^{-1})$. Both proofs use cycle conditions required by low-weight codewords and a lower bound on the number of terms in vectors satisfying polynomial check equations. Neither construction requires $P$ to be prime. We also give small-lift arrays attaining the bound 24 for $J=3$, $L=4,\ldots,8$, and arrays with distance at least 28 for $J=4$, $L=5,\ldots,8$, together with computational distance verification.

0.35

High-Rate Quasi-Dyadic Quantum LDPC Codes

cs.IT ·2026-09-21 ·Alessio Baldelli, Sisi Miao, Laurent Schmalen, Massimo Battaglioni, Marco Baldi
similarity 0.70
Abstract

In this work, we propose a novel design of high-rate Calderbank--Shor--Steane (CSS) quantum low-density parity-check (QLDPC) codes based on quasi-dyadic matrices. The Tanner graphs associated with the two component classical codes used to construct the proposed CSS codes are characterized by a girth of at least $6$. We also derive an exact count of length-$4$ cycles in the quaternary representation of the parity-check matrix. Monte Carlo simulations under code-capacity and phenomenological noise models show that the proposed codes have competitive finite-length logical error rate performance compared with state-of-the-art codes in both these settings.

0.05

Quantum LDPC and High-Rate CSS Codes from Fair-Density Parity-Check Codes

cs.IT ·2026-09-01 ·Hessam Mahdavifar
similarity 0.70
Abstract

We construct quantum LDPC (qLDPC) and high-rate CSS codes from our recently introduced classical fair-density parity-check (FDPC) codes. To this end, we introduce a structured sparsification of FDPC parity-check matrices, which reduces their check weights while preserving the underlying combinatorial structure and distance guarantees. Combined with the hypergraph-product construction, this yields finite-length qLDPC codes with analytically controlled blocklength, dimension, certified distance, and stabilizer weight. For quantum blocklengths $N<10^5$, the constructions introduced here span guaranteed rates from approximately $0.35\%$ to $25.8\%$ and certified quantum distances from $12$ to $69$, with stabilizer weights between $8$ and $16$. In the large-blocklength regime, allowing the FDPC order and sparsified check weight to scale moderately with blocklength yields a family of high-rate CSS codes, which we refer to as quantum FDPC (qFDPC) codes, with rate $R_Q$ and minimum distance $D$ satisfying \[ R_Q = 1-O\left(\frac{1}{\log\log N}\right), \ \ D=Ω(N^{1/4}), \] and stabilizer weight $O(\log N\log\log N)$. Finally, the analytically available FDPC weight distribution provides explicit information about the logical operators of the resulting hypergraph-product codes. Over the quantum erasure channel, this structure yields rigorous first-order maximum likelihood (ML) expressions and a higher-order weight-distribution approximation to the ML logical block error probability. This enables estimation of finite-length operating points and the onset of the error-floor regime. To the best of our knowledge, beyond surface-code-type constructions, this is the first finite-rate qLDPC framework to provide both finite-length certified minimum-distance information and an analytical characterization of low-weight logical multiplicities.

0.08