CS Paper Radar

New distance bounds for one-generator quasi-cyclic codes with applications to Hermitian LCD codes and entanglement-assisted quantum codes

Kanat Abdukhalikov, Duy Ho, Rasha M. Shat

cs.IT ·submitted 2026-09-25 14:09 UTC · v1

Abstract

We introduce lower bounds on the minimum distance of one-generator quasi-cyclic codes of arbitrary index, obtained by puncturing and shortening the code at the level of its blocks. For balanced codes, these bounds form a nondecreasing chain whose first term is the Jensen bound. We apply these bounds to conduct a computer search and obtain many Hermitian LCD codes with good parameters. Among them there are six codes of length at most 30 which improve the corresponding lower bounds of Araya and Harada. These codes further give maximal-entanglement entanglement-assisted quantum codes, which we compare with the parameters currently recorded in the literature.

Closest papers

Nearest neighbours by meaning across the whole index.

Quantum synchronizable codes, polynomial and quasi-polynomial shifts

cs.IT ·2026-11-07 ·Edgar Martínez-Moro, Miguel de los Ríos de Antonio
theory similarity 0.66
Abstract

Quantum synchronizable codes protect quantum information against Pauli errors and against misalignments of the block boundaries. Almost all known constructions use cyclic codes, because the channel shifts the transmitted block cyclically. We study what happens when the algebraic shift of the code differs from the physical one. When one uses a twisted padding, constacyclic codes synchronize at no cost, and they are the only polycyclic codes with this property for a linear padding. For the other polycyclic codes, we measure the cost of each misaligned position, and we show that the phase damage it causes can be corrected as erasures. Using annihilator duality, we extend the construction to quasi-polycyclic codes, in which the cost is confined to a single block. We prove that the usual quasi-cyclic families have a distance bound that does not grow with the length, and show that quasi-polycyclic codes over repeated-root trinomials overcome it, giving synchronizable codes with larger dimension and distance than the known synchronizable codes of the same length.

0.21

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.66
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

Ancestor Lifting of Quasi-Cyclic Additive Codes and Certified Quantum Codes

cs.IT quant-ph ·2026-10-27 ·Liangdong Lu, Ran Xu, Ruipan Yang, Qiang Fu
theory similarity 0.66
Abstract

Additive codes over $\Ffour$ that are self-orthogonal under the trace inner product correspond to binary quantum stabilizer codes. We study 1-generator $(1,2)$-quasi-cyclic (QC) additive codes and their exact quantum distances. For composite lengths $n=\ell m$, an ancestor-lifting theorem transports dual words of the folded ancestor to the length-$n$ code. A two-layer decomposition for $\ell=2$ and a CRT splitting for odd $\ell$ yield dimension laws and explain equality, escape, and mixed-branch behavior in the certified examples. A palindromic criterion ensures symplectic self-orthogonality, while reversal pairing and a symplectic Gram rank formula describe broader construction families. Exact distances are established by information-set decoding screening, Brouwer--Zimmermann computation on the additive dual, and independent witness verification. We certify twenty-one record-breaking binary quantum codes across twenty entries of Grassl's code table, with twenty-eight certified members in total. Propagation improves thirty-four further entries, and explicit constructions are supplied for three table-tying GV entries marked Code Missing Construction. Six additional candidates are reported only with rigorous upper bounds and heuristic screening evidence. The results connect divisor-lattice structure in additive quasi-cyclic codes with reproducible certification of exact quantum distances.

0.10

Optimal Pure Quantum $(r,δ)$-LRCs from Euclidean and Hermitian Dual-Containing Cyclic Codes

cs.IT ·2026-09-18 ·Astha Agrawal, Shayan Srinivasa Garani
similarity 0.66
Abstract · 29 pages, 4 tables

Locally recoverable codes (LRCs) combine global error correction with the ability to repair a small number of erased coordinates by accessing only a limited number of other coordinates. Motivated by their quantum counterparts, we construct several families of optimal cyclic $(r,δ)$-LRCs that are Euclidean or Hermitian dual-containing. In the Euclidean case, we obtain four families of optimal dual-containing cyclic $(r,δ)$-LRCs over $\mathbb{F}_q$ with a range of minimum distances extending beyond the local distance $δ$. In the Hermitian case, we derive analogous families over $\mathbb{F}_{q^2}$ that are Hermitian dual-containing, when $(r+δ-1)\mid(q^2-1)$. In addition, we develop a distinct construction for the case $(r+δ-1)\mid(q^2+1)$ using symmetric defining sets and odd $δ$, which yields optimal codes with minimum distances $\ell+2$, $δ+2$, $2δ-2$, and $2δ$. The Euclidean Calderbank-Shor-Steane (CSS) and Hermitian stabilizer constructions then give corresponding quantum cyclic $(r,δ)$-LRCs over~$\mathbb{F}_q$. Further, the resulting stabilizer codes are pure; they meet the relevant quantum Singleton-type bound, and are therefore \textit{optimal}. We also provide a comparison with previous works, highlighting the parameter regimes and minimum distance ranges covered by our results that are not attained by existing constructions. Explicit examples illustrate the constructions and verify the dual-containment and purity conditions.

0.20

Solutions to Three Conjectures and an Open Problem on Binary BCH Codes

cs.IT ·2026-09-01 ·Xiaoqiang Wang, Jiawei He, Boru Yi, Dabin Zheng
theory similarity 0.65
Abstract

BCH codes are among the most important classes of cyclic codes and have played a central role in coding theory and its applications. One of the fundamental problems in the study of BCH codes is to determine their exact minimum distances, which directly govern their error-correcting capability. Although the BCH bound provides a general lower bound, determining the exact minimum distance is often difficult, and many parameter families remain unresolved. In this paper, we investigate three conjectures and an open problem on binary BCH codes proposed by Chen, Xie, and Ding in \cite{Chen59}. We settle these conjectures on the exact minimum distances of three families of binary BCH codes by constructing codewords attaining the BCH bound. Beyond these conjectures, we further study the more difficult family codes and determine its minimum distance for some cases. We further study Open Problem 8.4: affirmative answers are obtained for the first two length families, while for the third family a sufficient condition is established and a counterexample shows that the unrestricted assertion does not hold in general.

0.20

Euclidean Hulls of Double Cyclic Codes of Arbitrary Block Lengths

cs.IT ·2026-11-10 ·Awadhesh Kumar Shukla, Om Prakash Pandey, Sachin Pathak, Ashish Upadhyay
similarity 0.65
Abstract

Gao et al. \cite{GWF23} recently explored the Euclidean hulls of double cyclic codes over $\mathbb{Z}_2$. While they found answers for non-separable codes with coprime lengths ($\gcd(r, s) = 1$), the non-coprime case ($\gcd(r, s) > 1$) remained an open question. This paper completely solves that problem for all possible block lengths. We calculate the exact generator polynomials for the hull and show the precise conditions needed for a non-separable code to turn into a separable one. Using this, we show how to construct non-separable LCD codes. We also include several numerical examples to confirm our findings.

0.11

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.65
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

Uniform Three-Fold Product Expansion of Algebraic-Geometry Codes over a Fixed Field

cs.IT math.AG ·2026-11-05 ·Cassie Ding, Min-Hsiu Hsieh
theory similarity 0.65
Abstract · 76 pages

A collection of classical codes $C_1,\dots,C_m$ has product expansion if every low-weight word in the sum of their extensions to the product space can be written as a sum of words supported on few lines, each line being a codeword of the corresponding $C_i$. For $m=2$ product expansion is equivalent to robust testability of the tensor code, while for $m\ge 3$ it is strictly stronger; it is the hypothesis on the local codes behind recent constructions of good quantum LDPC codes, good quantum locally testable codes, and quantum codes with transversal non-Clifford gates. No explicit family over a fixed field was previously known to achieve constant rate, linear distance for both the code and its dual, and 3-fold product expansion at growing length. We prove that for the one-point evaluation codes $C_i$ of length $N_i=728\cdot27^{\,i-1}$ and pole order $\lfloor N_i/5\rfloor$ on the Garcia--Stichtenoth tower over $\mathbb{F}_{729}$, the triple $(C_i,C_i,C_i)$ has product expansion with a constant independent of $i$. The dual codes $C_i^\perp$ then form an explicit fixed-field family of rate tending to $109/130$ and relative distance at least $8/65$. The proof is geometric: we view the words of the sum code as arrays on the product of three copies of the $i$-th curve of the tower, where the parity checks are sections of a line bundle. An exact generation theorem describes the sum-code words supported on the grid footprint of a suitable divisor. A support-localisation argument then shows that every low-weight array lies on such a divisor, after deleting a small number of coordinates. We also give a sufficient criterion for three-fold product expansion in terms of degree and genus ratios, yielding explicit families over every non-prime finite field of order at least $512$. The principal conclusions have been formally verified in Lean 4.

0.16