arXiv:2610.04617
New Methods for Constructing Classical and Quantum Codes from Graphs and Matroids
Anderson S. Barbosa, Franklin de L. Marquezino, Giuliano G. La Guardia
Abstract
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.
AI Summary
The paper studies classical linear codes defined as kernels of graph incidence matrices and asks how graph and matroid structure can specify their parameters and ensure compatibility for CSS constructions. Its main construction takes the $2$-sum of the cycle matroids of two identical book graphs $B_{n,c}$, each consisting of $c$ length-$n$ cycles sharing one edge, using that shared edge for the sum. The resulting codes have parameters $[2c(n-1),2c-1,2n-2]$. Length, dimension and distance are obtained from the matroid’s ground-set size, rank and girth. Four binary examples are identified as having optimal minimum distance for their length and dimension: $[8,3,4]_2$, $[12,5,4]_2$, $[12,3,6]_2$ and $[16,3,8]_2$. Explicit generator matrices are supplied; the first example is acknowledged as previously known. For CSS codes, a sufficient nesting criterion is proved: if every circuit of one binary matroid is a disjoint union of circuits of another, their associated kernel codes are nested. The proof uses spanning by minimal-support codewords. Applying this criterion to a cycle and a disjoint union of cycles produces distance-$2$ CSS codes, including a $[[6,1,2]]$ example with $d_X=3$ and $d_Z=2$. The paper also establishes that an oriented incidence matrix defines an $[|E|,|E|-|V|+\omega,g]_q$ code over every finite field, where $\omega$ counts connected components and $g$ is graph girth. The quantum treatment is restricted to binary stabilizer codes, and the cycle-based quantum constructions presented have distance $2$.
Error found: The main theorem asserts optimal minimum distances for four binary codes without supplying the upper bounds needed to establish optimality, although the claimed optimal parameters are correct. The main theorem's proof reverses the girth condition in one sentence: a shortest circuit avoiding the identified edge survives the 2-sum and prevents the claimed girth increase. The finite-field theorem's unrestricted claim that row reduction preserves entries in {0,±1} is false for arbitrary elementary row operations, although it holds for the reduced row-echelon form of an oriented incidence matrix.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 19 pages, 4 figures