CS Paper Radar

Quantum synchronizable codes, polynomial and quasi-polynomial shifts

Edgar Martínez-Moro, Miguel de los Ríos de Antonio

cs.IT ·submitted 2026-11-07 18:51 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Quantum Locally Repairable Codes from Negacyclic and Repeated-Root Cyclic Codes over Small Fields

cs.IT ·2026-08-22 ·Ruipan Yang, Qiang Fu, Liangdong Lu
theory similarity 0.71
Abstract

Quantum locally recoverable codes (qLRCs), introduced recently by Golowich and Guruswami, allow any single-qudit erasure to be recovered from a small set of other qudits. Most known constructions require a large alphabet. We systematically investigate qLRCs obtained, via the CSS construction, from classical constacyclic codes over small fields $\Ff_q$ with $q\in\{2,3,4,5,7\}$. First, we prove that a nonzero dual-containing $λ$-constacyclic code exists only when $λ^2=1$, so that negacyclic and (repeated-root) cyclic codes exhaust the constacyclic route to qLRCs. Second, we show that the locality of a constacyclic code equals the minimum distance of its dual minus one, and we give a simple purity criterion for the resulting quantum codes. Third, we show that odd-like duadic codes whose splitting is given by $μ_{-1}$ yield pure qLRCs; specializing to $q$-ary quadratic residue codes of prime length $p\equiv 3 \pmod 4$ gives an infinite family of pure qLRCs with unbounded minimum distance and certified locality. Finally, by means of concrete computations, we obtain a classification of qLRCs from cyclic, negacyclic, and repeated-root cyclic codes of moderate lengths, which contains the first binary qLRCs from repeated-root cyclic codes and many parameter sets that cyclic codes cannot attain.

0.40

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.68
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.38

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

Quantum codes in the Lee metric

cs.IT quant-phmath.COmath.MG ·2026-10-04 ·Jinkang Guo, Yiqiu Han, Aranya Chakraborty, Shubham P. Jain, Tianhao Liu +2 more
theory similarity 0.67
Abstract

We introduce a quantum coding framework for discrete small-shift noise, in which errors on qudits are modeled as low-weight $X$- and $Z$-type Pauli shifts, analogous to small phase-space displacements in continuous-variable systems. This structure is approximately respected by nuclear-spin noise and captured by the Lee metric, motivating a quantum extension of classical Lee-metric coding theory. We develop such a formalism for stabilizer codes over $\mathbb{Z}_q$ for arbitrary $q$, using joint and separate Lee metrics for the $X$- and $Z$-components of errors. For qubits, the joint metric counts $Y$ errors twice and can yield codes that detect and correct $X$ and $Z$ errors with fewer physical qubits than codes designed for the conventional Hamming metric. We discuss Lee-weight spreading under Clifford gates and qubitize codes over $\mathbb{Z}_4$ via the Gray map, finding codes with two-fold transversal non-qubit-Clifford gates. For quantum CSS Lee-LDPC codes on $n$ qudits, we prove that the Lee distance cannot exceed $O(n)$, uniformly in $q$, demonstrating an unexpected obstruction to using the large internal Hilbert space of a large-$q$ qudit to make high-Lee-distance codes. Under local Metropolis dynamics, certain classical $q$-ary ``helical repetition codes'' have exponentially long memory times at fixed temperature for sufficiently large $q$ (that grows with system length), which can be understood as spontaneous symmetry breaking at finite temperature, even in local one-dimensional models. Hypergraph products of these helical repetition codes provide local two-dimensional quantum codes that inherit self-correction for $Z$ errors, but self-correction for $X$ errors remains an open question.

0.49

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

cs.IT ·2026-09-25 ·Kanat Abdukhalikov, Duy Ho, Rasha M. Shat
similarity 0.66
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.

0.14

Quantum Matrix-Product Codes: CSS-T Characterization and Maximality

cs.IT ·2026-09-08 ·Delio Jaramillo-Velez, Alessandro Neri, Adway Patra, Diego Ruano, Flavio Salizzoni
similarity 0.66
Abstract · Comments are welcome

CSS-T codes are quantum error-correcting codes that play an important role in fault-tolerant quantum computation, as they help mitigate the proliferation of errors. They admit a transversal T-gate and are defined from a pair of nested classical binary linear codes satisfying a specific algebraic condition expressed in terms of their Schur square. We extend this algebraic characterization to the propagation rule known as the $(u \mid u+v)$-construction, that is, the matrix-product code constructed from two constituent codes. Moreover, for cyclic constituent codes, we provide an explicit characterization in terms of the defining cyclotomic sets, which extends existing results for cyclic codes. This framework allows the construction of new and longer CSS-T codes.

0.41

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

Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time

cs.IT quant-ph ·2026-09-30 ·William Gay, Fernando Granha Jeronimo, Abhi Shukul
top venue similarity 0.66
Abstract · SODA 2027, to Appear

In classical coding theory, the quest for explicit codes achieving list decoding capacity has been an important driving force. While random codes are easily shown to achieve capacity, an explicit construction was only discovered decades later in the seminal work [Guruswami and Rudra, STOC 2006]. In quantum coding theory, it is highly desirable that a code family be LDPC. While good quantum codes were known for decades, obtaining the additional LDPC property was elusive. In fact, only very recently that good quantum LDPC codes were discovered in a breakthrough work [Panteleev and Kalachev, STOC 2022]. In this context, a natural question is to ask for an explicit family of quantum codes achieving list decoding capacity while also possessing the important LDPC property. In this work, we provide (to the best of our knowledge) the first explicit constructions of quantum LDPC codes achieving list decoding capacity, namely, with a list decoding radius approaching the quantum Singleton bound with constant list sizes. Furthermore, we provide near-linear time (in the block-length) list decoding algorithms approaching capacity. Our explicit code construction are based on expander graphs via the quantum analogue of Alon-Edmonds-Luby (AEL) amplification [Bergamaschi, Golowich and Gunn, STOC 2024], and this enables the important LDPC property. Our efficient list decoding algorithms are obtained by generalizing the classical expander-based weak-regularity list decoding algorithms [Srivastava and Tulsiani, FOCS 2025] [Jeronimo and Singh, 2025] to suitable instantiations of quantum AEL.

0.58