CS Paper Radar

Stabiliser codes over prime fields as weighted graphs and as quantum sets of lines

Simeon Ball, Gülizar Günay, Robin Simoens, Ricard Vilar

cs.IT math.COquant-ph ·submitted 2026-11-03 19:00 UTC · v1
theory

Abstract

We further develop the theory of quantum stabiliser codes and its links with graph theory and finite geometry. We prove that an [[n,k,d]]_p stabiliser code over a finite field with p elements, p prime, gives rise to a graph on n-k vertices together with two disjoint independent sets of size k. Its edges are weighted with elements of a finite field of size p. If k=0, such codes are known as graph states. Second, we view stabiliser codes as so-called quantum sets of lines in projective space, allowing us to determined their minimum distance geometrically. We describe two geometrical operations to obtain new quantum sets of lines from given quantum sets of lines. As an application, we list the number of stabiliser codes up to equivalence, for given small parameters.

Closest papers

Nearest neighbours by meaning across the whole index.

Lifting an $[n,k,d]$ Binary Linear Code to an $[[n,k,d]]$ Quantum Stabilizer Code

cs.IT quant-ph ·2026-10-09 ·Thamadathil Aswanth, Navin Kashyap
theory similarity 0.69
Abstract · 6 pages, Submitted to ITW 2027

The codeword stabilized (CWS) framework provides a systematic method for constructing quantum error correcting codes from a simple undirected graph and a classical code. When the underlying classical code is linear, the resulting quantum code is a stabilizer code. In this work, we investigate the conditions under which an arbitrary $[n,k,d]$ classical binary linear code can be lifted to an $[[n,k,d]]$ quantum stabilizer code using the CWS framework. We analyze the random CWS code constructed from a given $[n,k,d]$ binary linear code $\mathcal{C}$ and an Erdős-Rényi random graph $\mathrm{G}(n, \frac12)$. We establish a lower bound on the probability that the resulting quantum code preserves the minimum distance $d$ of the classical code. This probabilistic analysis yields a Gilbert-Varshamov-type condition on the $n,k,d$ parameters of the classical code that guarantees the existence of a graph resulting in a quantum code with the same $n,k,d$ parameters.

0.09

On the Length of Maximum Sum-Rank Distance Codes

cs.IT math.CO ·2026-10-16 ·Valentina Astore, Ferdinando Zullo
similarity 0.67
Abstract

The classical theory of arcs in finite projective spaces provides a powerful geometric framework for studying maximum distance separable (MDS) codes and their possible lengths. In this paper, we investigate how this perspective extends to maximum sum-rank distance (MSRD) codes, whose geometric description involves systems of linear sets rather than individual projective points. Our main goal is to understand how the block structure of an MSRD code constrains its length. In dimension three, we determine the possible intersection patterns of lines with the associated linear sets and obtain explicit formulas for their characters and the weight distribution of the corresponding codes. These results lead to new length bounds and show that the block structure comes at a cost: the presence of a block of rank at least two reduces the maximum possible total length by at least $q-1$, and sufficiently long MSRD codes must be classical, that is, MDS codes over $\mathbb F_{q^m}$. We also prove that three-dimensional one-weight MSRD codes do not exist. In arbitrary dimension, we interpret shortening geometrically as projection and establish a general projection bound that extends classical counting arguments for arcs. This yields restrictions depending explicitly on the block profile and, for full-length blocks, identifies parameter ranges in which linearized Reed--Solomon codes attain the maximum possible number of blocks. Finally, we construct an exceptional three-dimensional MSRD code over $\mathbb F_9$ with three blocks of length two and propose a sum-rank analogue of the MDS conjecture.

0.41

New Methods for Constructing Classical and Quantum Codes from Graphs and Matroids

cs.DM quant-ph ·2026-10-03 ·Anderson S. Barbosa, Franklin de L. Marquezino, Giuliano G. La Guardia
similarity 0.65
Abstract · 19 pages, 4 figures

In this paper, we present a method for constructing linear codes derived from book graphs. Applying such a method, we construct binary codes that have the greatest possible minimum distance for their length and dimension by means of the $2$-sum of two equal book graphs. We then utilize matroid and graph theory together to investigate some properties of the resulting linear codes. Furthermore, we show that, from the incidence matrix of any graph, we can obtain a linear code over any finite field maintaining the same parameters. Furthermore, we show how the condition for two linear codes to generate a Calderbank-Shor-Steane (CSS) code translates into matroid theory and, utilizing cycle graphs, we exhibit a way to generate codes that meet this condition.

0.18

Quantum MDS codes from complements of unions of finite-field subsets

cs.IT math-phmath.QA ·2026-09-09 ·Naihong Hu, Hong Ji
similarity 0.64
Abstract · 37 pages

Let $q$ be an odd prime power. We use complements of unions of subsets of $\mathbb F_{q^2}$ as locator sets and establish a sufficient condition under which a generalized Reed--Solomon (GRS) code is Hermitian self-orthogonal. Using cosets of multiplicative subgroups and sets with prescribed trace or norm values, we construct five families of Hermitian self-orthogonal GRS codes over $\mathbb F_{q^2}$. The Hermitian construction then yields five corresponding families of $q$-ary quantum maximum-distance-separable (MDS) codes. Under suitable parameter conditions, these quantum codes have minimum distances greater than $q/2+1$. By comparing codes of the same length, we give conditions under which our codes have strictly larger minimum distances than those obtainable from several previously known constructions based on trace maps, linear transformations, and cosets of multiplicative subgroups, either directly or via the propagation rule. We further show that such improvements occur for infinitely many values of $q$.

0.22

The Neighbor Graph of Linear Complementary Dual (LCD) Codes

cs.IT math.CO ·2026-09-07 ·Javier de la Cruz, Anna-Lena Horlemann, Marc Newman, Carlos Vela Cabello, Wolfgang Willems
theory similarity 0.64
Abstract

Linear complementary dual (LCD) codes form an important class of linear codes with applications in cryptography, classical error correction, and quantum coding theory. In this paper, we study the neighbor relation on LCD codes over finite fields and the graph induced by this relation, where two codes are adjacent whenever they intersect in codimension one. We determine the number of neighbors of an LCD code that are also LCD, and we use this result to analyze the structure of the corresponding neighbor graph. In particular, we prove its regularity over arbitrary finite fields and establish further regularity properties for its main structural subgraphs in the binary and odd-characteristic cases. These results provide a graph-theoretic framework for the study of LCD codes and reveal a strong combinatorial regularity in their neighborhood structure.

0.26

Minimum distances of primitive narrow-sense BCH codes via good zero-sets

cs.IT ·2026-09-18 ·Run Zheng
similarity 0.62
Abstract

Determining the exact minimum distances of BCH codes remains a open problem. We establish the minimum distances of several families of primitive narrow-sense BCH codes, showing that they attain their designed distances. Our approach centers on $\mathbb{F}_q$-good zero-sets, which we introduce through a derivative condition on their vanishing polynomials. We show that a $q$-ary primitive narrow-sense BCH code of length $q^m-1$ and designed distance $2\leqδ\leq q^m-1$ has minimum distance $δ$ if and only if there exists an $\mathbb{F}_q$-good zero-set of cardinality $δ+1$ in the finite field $\mathbb{F}_{q^m}$ with $q^m$ elements. To construct $\mathbb{F}_q$-good zero-sets, we develop several methods based on polynomial substitutions, power maps, and shifted inverses, as well as direct constructions using polynomials of special forms. Together with suitable initial $\mathbb{F}_q$-good zero-sets, including those arising from known minimum-distance results, these methods yield new good zero-sets of various cardinalities and hence families of primitive narrow-sense BCH codes whose minimum distances equal their designed distances. These families cover a broad range of designed distances, with several known minimum-distance results recovered as special cases.

0.38

A Simple Explicit Construction of Smaller Strong Blocking Sets

cs.IT math.CO ·2026-10-09 ·Hao Chen
similarity 0.61
Abstract · 12 pages

Alon, Bishnoi, Das and Neri constructed sequences of strong blocking sets in $(k-1)$-dimension projective space $P({\bf F}_q, k-1)$ with sizes at most $Cqk$, where $k$ goes to the infinity and $C$ is a fixed positive constant not depending on $q$, in their paper published in Transactions AMS, vol. 277, pp. 5389-5410, 2024. This is equivalent to a sequence of minimal $[n_i,k_i]_q$ codes with positive rate $\frac{k_i}{n_i} \geq c$, where $k_i$ goes to the infinity and $c$ is a fixed positive constant only depending on $q$. They solved one of the main open problems on minimal codes. The Alon-Bishnoi-Das-Neri construction was based on asymptotically good sequences of algebraic geometric codes and expander graphs. However, the constant $C$ is large for small prime power $q$. In this paper, based on a simple approach using $(q-1)$-power intersecting algebraic geometric codes via concatenation to construct minimal codes, we construct explicit strong blocking sets in $(k-1)$-dimension projective space with sizes around $2(q^2-1)k$, equivalently, explicit minimal $[n,k]_q$ codes with length around $2(q^2-1)k$. This is an essential improvement on the previous result of Alon-Bishnoi-Das-Neri, when $q \leq 11$. For large $q$, strong blocking sets and minimal codes in our construction are worse than the previous construction of Alon-Bishnoi-Das-Neri. However, our approach is much simpler and does not depend on expander graphs.

0.38

Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance

cs.CC quant-phcs.IT ·2026-09-19 ·Rafail Ostrovsky
theory similarity 0.61
Abstract

We prove that the quantum code distance is NP-hard to approximate within an additive error of $c N$, for some constant $c >0$, where $N$ is the number of qubits. Our reductions are deterministic. This improves the previous square-root additive gap to $Ω(N)$ and resolves the explicitly stated linear-gap question of Kapshikar and Kundu. Our result holds for CSS codes with identical $X$- and $Z$-check spaces, and with a constant rate and constant relative distance. For every fixed $λ>1$, there is a constant $c>0$ such that hardness still holds even when every nonidentity stabilizer has weight greater than $λ$ times the quantum distance. We also improve the hardness gap of graph state distance on $N$ vertices of Grigorescu, Jha, and Samperton from cube-root to $Ω(N)$, resolving their explicitly stated open question. Both hardness results are asymptotically optimal since both distances are at most $N$. Our graph state distance hardness result holds for balanced bipartite graphs with a binary adjacency matrix that is its own inverse (mod 2). Our main technique for both hardness bounds above is classical: we show how to convert any code $C$ of length $m$ into a self-dual code $A(C)$ of length $N=Θ(m)$ while exactly doubling the original coset metric. The conversion is deterministic and efficient. We call it the metric self-dual completion of $C$. It comes with a linear embedding $τ: \mathbb F_2^m \hookrightarrow \mathbb F_2^N$. The embedding doubles all Hamming distances between vectors in $\mathbb F_2^m$ and all pairwise distances between corresponding cosets. The embedding also guarantees that all codewords of $A(C)$ of weight at most $2m$ are exactly $τ(C)$.

0.27