CS Paper Radar

Singleton-Optimal Rank-Metric CSS Codes : Equality Structure and Exact Projected-Recovery Radii

Myeongjun Kim, Suseong Lee, Jaeho Jeon, Young-Sik Kim

cs.IT ·submitted 2026-09-29 01:24 UTC · v1
theory

Abstract

Correlated faults from shared control can have dense physical support yet low rank over a base field, motivating rank-metric quantum codes for stacked architectures. We prove an asymmetric rank-metric Singleton bound for Calderbank--Shor--Steane codes, including degenerate codes, and characterize equality through commuting maximum-rank-distance matrix codes. Optimal pairs exist for every admissible parameter triple and are necessarily pure. Comparison with erasure bounds establishes an exact advantage in stacked rank distance for general stabilizer codes at fixed physical resources on certain tall layouts. We determine whether relaxing the recovery target enlarges the worst-case correctable radius. For Singleton-optimal pairs with positive logical dimension, the measured syndrome determines the projected error modulo stabilizers exactly at radii strictly below half the sector rank distance, on every layout and for every nonzero projector. The projected syndrome is recoverable at arbitrary radii exactly when the complementary check space is invariant under the adjoint projector; otherwise, the same radius limit applies. For nontrivial idempotents, this invariance requires more rows than columns or sector distance one. For trace-self-adjoint projectors, linear ambient projected-syndrome interfaces in both sectors exist exactly when the code splits as a tensor product across the projector. Designs placing the two check spaces in complementary projector images are necessarily one-sided whenever they encode logical information. Two explicit families realize the extreme cases of the equality structure, including a two-sided family with an efficient certifying decoder attaining the optimal unique-decoding radius.

Comment
29pages

Closest papers

Nearest neighbours by meaning across the whole index.

Bounds for Pure Disjoint $(r,δ)$-Quantum Locally Recoverable Codes

cs.IT quant-ph ·2026-08-11 ·Evagoras Stylianou, Holger Boche
publishedtheory similarity 0.70
Abstract · Accepted for presentation at the 2026 IEEE International Symposium on Information Theory (ISIT 2026)

We study pure disjoint $(r,δ)$-quantum locally recoverable codes (qLRCs) without assuming a stabilizer structure. We formulate local Knill--Laflamme conditions for recovery from up to $δ-1$ erasures within a recovery block, and introduce blockwise Shor--Laflamme and unitary weight enumerators that capture how error weight is distributed across recovery sets. We establish several properties of these enumerators and use them to derive a Singleton-like bound that strengthens the known bound for disjoint $(r,δ)$-qLRCs under a purity assumption, as well as a linear-programming upper bound on the code dimension. These results provide a non-stabilizer, weight-enumerator-based approach to the study of pure disjoint $(r,δ)$-qLRCs.

0.52

CSS Quantum LRCs with Intersecting Recovery Sets: Constructions and Bounds

cs.IT quant-ph ·2026-08-11 ·Evagoras Stylianou, Vinayak Ramkumar, Holger Boche, Rawad Bitar
similarity 0.69
Abstract · Accepted for presentation at the 2026 IEEE Information Theory Workshop (ITW 2026)

In this work, we study $(r,t,x)$ quantum locally recoverable codes (qLRCs) with locality $r$, $t$ recovery sets per qudit, and intersection parameter $x$. We first show that, assuming the underlying classical codes have dual minimum distance at least two, a CSS code is an $(r,t,x)$-qLRC if and only if the underlying classical codes are $(r,t,x)$ classical LRCs (cLRCs) with common recovery sets. We then use subset-inclusion matrices to construct families of binary dual-containing $(r,t,x)$-cLRCs, which yield binary $(r,t,x)$-qLRCs via the CSS construction. For CSS $(r,t,x)$-qLRCs, we derive upper bounds on the dimension and rate, minimum-distance bounds in the pure case, and a Singleton-like dimension bound in the exact case. Finally, we show that these families attain high rates and nontrivial minimum distances.

0.49

Subsystem Stabilizer $(r,δ)$-Locally Recoverable Codes: Characterization, Bounds and Constructions

cs.IT ·2026-11-17 ·Yaozong Zhang, Sihem Mesnager, Xiaoqiang Wang, Jian Gao
similarity 0.69
Abstract

Local erasure recovery limits the number of physical systems accessed to repair a distributed quantum memory. For subsystem stabilizer codes (SSCs), a basic question is whether erasures can be corrected within a prescribed repair set. In this paper, we study subsystem stabilizer $(r,δ)$-locally recoverable codes ($(r,δ)$-SSLRCs), in which each coordinate belongs to a repair set of size between $δ$ and $r+δ-1$ that corrects any set of up to $δ-1$ erasures while preserving the logical subsystem and allowing the gauge subsystem to change. We first characterize local erasure recovery algebraically and apply this criterion to Calderbank-Shor-Steane (CSS) and Hermitian hull constructions for $(r,δ)$-SSLRCs. For $(r,δ)$-SSLRCs, without assuming purity, we derive a redundancy bound for disjoint repair sets, a supported-subspace bound based on supported stabilizer and gauge subspaces, and a mixed counting bound for known erasures within selected repair sets and errors at unknown positions outside their union. For pure $(r,δ)$-SSLRCs with overlapping repair sets, we establish the Singleton-type and alphabet-dependent bounds, together with explicit Griesmer, Hamming, and Plotkin bounds. Moreover, we construct nine classes of $\F_q$-linear pure $(r,δ)$-SSLRCs from maximum distance separable (MDS) stabilizer codes, Reed-Solomon (RS) codes, and linear codes with MDS Hermitian hulls, which are simultaneously optimal with respect to several bounds for $(r,δ)$-SSLRCs.

0.31

From Random Quantum Codes to Explicit qLDPC Codes via Local Properties

cs.IT quant-ph ·2026-09-30 ·Fernando Granha Jeronimo, Xiaojuan Ma, Nikhil Shagrithaya
theory similarity 0.69
Abstract

Constructing explicit codes matching the parameters of random codes has been a central and largely elusive question in coding theory. The quantum setting is even more challenging since it is highly desirable that the quantum code be an LDPC code. Local coordinate-wise linear (LCL) [Levi, Mosheiff, and Shagrithaya, FOCS 2025] witnesses provide a unifying language for many coding-theoretic properties, from distance to list decoding and list recovery. In particular, it provides a framework to study properties of random linear codes, which achieve optimal parameters for many properties of linear codes. For CSS quantum codes, however, a local witness has two distinct ranks: its physical rank before quotienting by stabilizers and its logical rank after quotienting. We develop a quantum version of the LCL framework for nested spaces $S \subseteq C$, in which local constraints are imposed on physical representatives while independence is measured in the logical quotient $C/S$. The resulting theory gives a threshold theorem for random CSS codes, and as a consequence shows that the per-sector rate threshold is equal to the classical rate threshold. We also define a quantum analogue of subspace design [Guruswami and Xing, STOC 2013] and show that they can be described in a natural manner within the quantum-LCL framework. Finally, we give explicit constructions for arbitrary folded quantum-LCL properties, in a manner similar to the LCL derandomization of [Jeronimo and Shagrithaya, STOC 2026]. As a consequence, we obtain the first explicit constructions of quantum list-decodable codes and list-recoverable codes that have optimal list sizes, in addition to explicit quantum subspace design codes. We note that all our explicit constructions are qLDPC codes, an important property for quantum error-correcting codes.

0.42

Optimal Impure $(r,δ)$-Quantum Locally Recoverable Codes with Explicit Minimum Localities

cs.IT ·2026-11-19 ·Yang Li, Shitao Li, Gaojun Luo, San Ling
similarity 0.67
Abstract

Quantum locally recoverable codes with $(r,δ)$-locality ($(r,δ)$-qLRCs) are quantum error-correcting codes in which $δ-1$ erased qudits can be recovered by accessing only $r$ other qudits. The minimum locality of a qLRC is the least $r$ such that it has $(r,δ)$-locality. This paper aims to construct optimal impure $(r,δ)$-qLRCs with disjoint recovering sets and explicit minimum localities, where the optimality is measured by the Singleton-like bound of Guruswami, Kshirsagar, and Trivedi (GKT-optimal). Such qLRCs have particular advantages in recovering as many quantum erasures as possible while operating in parallel and with minimal qudit access overhead. We first characterize the recovering sets and the minimum locality of any CSS code by local relative distances, which are relative minimum distances of punctured codes with respect to shortened codes. We then construct impure qLRCs as CSS codes from nested pairs of generalized monomial-Cartesian codes. Grouping the monomials by their degree in the last variable, we reduce both their minimum distances and their local recovery to nested pairs of codes in the remaining variables, and the coordinates with the same values of these variables form disjoint recovering sets. In this way, we obtain four infinite families of GKT-optimal impure $(r,δ)$-qLRCs with disjoint recovering sets, and determine their minimum localities and the recovering sets attaining them for every admissible $δ$, except for a partial range of $δ$ in one family. These minimum localities need not be monotone in $δ$. In particular, two of the families contain GKT-optimal impure subfamilies of CSS codes CSS$(\mathcal{C},\mathcal{C})$ with $(r,δ)$-locality for some $r<n-δ+1$ at values of $δ$ for which $\mathcal{C}$ has no classical $(r',δ)$-locality for any $0<r'<n$, where $n$ is the length of $\mathcal{C}$.

0.12

Covering radius of rank-metric codes via covering lifts and clubs

cs.IT math.CO ·2026-10-08 ·Giuseppe Marino, Alessandro Neri, Alessia Vallefuoco
theory similarity 0.66
Abstract

We introduce a generator-matrix-based geometric approach to the covering radius of $\mathbb F_{q^m}$-linear rank-metric codes. Starting from the $q$-system associated with the code, we define the notion of covering lift and show that the covering radius can be recovered from the hyperplane weights of such lifts. This yields an exact criterion, in terms of the length and effective length of the code, for the covering radius to attain its largest possible value, together with the upper bound $ρ(\mathcal{C})\le \min\{m,n\}-1$ in all remaining cases. We then specialize our approach to $1$-dimensional codes, for which the effective length coincides with the minimum rank distance. In this setting, codes attaining $ρ(\mathcal{C})= \min\{m,n\}-1$ are related to covering lifts that are clubs. More generally, we characterize this case through linear maps into suitable quotient spaces, obtaining equivalent interpretations in terms of generalised evasive subspaces and auxiliary matrix rank-metric codes. These results determine the covering radius for several boundary values of the minimum distance and for all $1$-dimensional codes with extension degree $m\in\{3,4,5\}$. For $m=6$ and every $q$ we provide constructions and, for $q\in\{2,3\}$, computational results showing that $1$-dimensional rank-metric codes with the same length and minimum distance can have different covering radii.

0.05

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

cs.IT ·2026-09-01 ·Hessam Mahdavifar
similarity 0.64
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

Code distances of matrix rank-metric codes under Add-and-Remove transformations

cs.IT ·2026-10-02 ·Gianira N. Alfarano, Rakhi Pratihar, Adrien Vinçotte
theory similarity 0.64
Abstract

For a matrix rank-metric code $\mathcal{C}$ and an integer $i$, the $i$-th subcode distance of $\mathcal{C}$ is the largest minimum rank distance of an $i$-dimensional subcode of $\mathcal{C}$. We study how subcode distances change under the Add-and-Remove construction, in which a subcode of codimension $\ell_s$ is kept and a space of dimension $\ell_a$ is added; this construction is used, with Gabidulin codes, in the $\mathsf{MIRANDA}$ signature scheme. For arbitrary matrix codes, we give inequalities between the subcode distances of the original and of the new code, and we show that Delsarte duality interchanges $\ell_s$ and $\ell_a$. For matrix Gabidulin codes, whose subcode distances are given by an explicit formula, we show that, if $\ell_s<\max\{m,n\}$, then within each block of indices $(a-1)\max\{m,n\}+1,\ldots,a\max\{m,n\}$ not exceeding $\dim_{\mathbb{F}_q}(\mathcal{C}_s)$, all but the last $\ell_s$ subcode distances are the same as for the Gabidulin code, and the remaining ones decrease by at most one; a small example shows that such a decrease can occur. We also express the minimum distance of the new code in terms of the rank distance between the added space and the common subcode. For $\mathsf{MIRANDA}$, the lower bound on the minimum distance of the dual public code used by the known distinguisher when $\ell_s=0$ is a special case of these results; for the proposed parameters, where $\ell_s>0$, the same bound holds for a subcode of codimension $\ell_s$ of the dual public code.

0.05