Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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

cs.DMquant-phSubmitted Oct 3, 2026• Announced Oct 6, 2026• 0 citations
arXivHTMLPDF

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

No sign of AI-generated textIncrementalUnclear noveltyMissing comparisonPossible error

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

Related papers

Quantum codes and symplectic matroids

Pradeep Kiran Sarvepalli

The correspondence between linear codes and representable matroids is well known. But a similar correspondence between quantum codes and matroids is not known. We show that representable symplectic matroids over a finite field Fqcorrespond to Fq-linear quantum codes. This connection is straightforward but it does not appear to have been made earlier in literature. This correspondence is made through isotropic subspaces. We show that Calderbank-Shor-Steane (CSS) codes correspond to homogenous symplectic matroids while graph states, which figure so prominently in measurement based quantum computation, correspond to a special class of symplectic matroids, namely Lagrangian matroids. This association is useful in that it enables the study of symplectic matroids in terms of quantum codes and vice versa. Furthermore, it has application in the study of quantum secret sharing schemes.

arXiv:1104.1171•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•3 citations

Linear Codes Over Finite Fields From Lattice Polytopes: Structure, Duality, and Quantum Constructions

Sihem Mesnager, Rameez Raja

Linear codes constructed from combinatorial and geometric structures have played a central role in both classical and quantum coding theory. In this paper, we discuss a class of linear codes over finite fields, calledpolytope codes, obtained via defining sets derived from lattice polytopes. Unlike evaluation-based constructions, our approach exploits the intersection structure of polytope faces to directly control the algebraic and metric properties of the resulting codes. We develop a general defining-set framework for polytope codes and explicitly determine their lengths, dimensions, minimum distances, and Hamming weight distributions. This leads to infinite families of projective, few-weight, distance-optimal, and almost distance-optimal codes. Sufficient conditions for minimality are derived, resulting in new minimal codes that are well suited for applications to secret-sharing schemes. We further study the duals and hulls of polytope codes and provide explicit characterizations of self-orthogonal and linear complementary dual (LCD) families. One of the central results of the paper is a complete classification of quantum codes arising from polytope codes via the Calderbank-Shor-Steane (CSS) construction. We show that the geometry of face intersections fully determines whether the resulting quantum code is a standard CSS code, an LCD-based code, or an entanglement-assisted quantum error-correcting code, and we explicitly compute the required entanglement in the latter case. As a consequence, new families of binary, ternary, and prime-power quantum codes with previously unattained parameters are obtained. The proposed polytope-based framework unifies classical and quantum code constructions under a common geometric principle and opens new avenues for applications in cryptography, distributed storage, and quantum information processing.Mathematics Subject Classification. 94B05, 52B20, 11T71, 94A62, 94A45.

IEEE Transactions on Information Theory•Sep 7, 2026•0 citations

Self-Orthogonal Codes Constructed from Posets and Their Applications in Quantum Communication

Yansheng Wu, Yoonjin Lee

It is an important issue to search for self-orthogonal codes for construction of quantum codes by CSS construction (Calderbank-Sho-Steane codes); in quantum error correction, CSS codes are a special type of stabilizer codes constructed from classical codes with some special properties, and the CSS construction of quantum codes is a well-known construction. First, we employ hierarchical posets with two levels for construction of binary linear codes. Second, we find some necessary and sufficient conditions for these linear codes constructed using posets to be self-orthogonal, and we use these self-orthogonal codes for obtaining binary quantum codes. Finally, we obtain four infinite families of binary quantum codes for which the minimum distances are three or four by CSS construction, which include binary quantum Hamming codes with length n≥7. We also find some (almost) “optimal” quantum codes according to the current database of Grassl. Furthermore, we explicitly determine the weight distributions of these linear codes constructed using posets, and we present two infinite families of some optimal binary linear codes with respect to the Griesmer bound and a class of binary Hamming codes.

Mathematics•Sep 3, 2020•8 citations

Quantum LDPC Codes from Polynomial Minors

Vahid Nourozi, Roxana Smarandache, David G. M. Mitchell

We construct quantum codes from codewords of a cyclic code and the minors of a polynomial matrix. The construction uses a two-row, three-column matrix whose minors yield a second matrix satisfying the CSS orthogonality condition. We derive the code dimension from the greatest common divisors of the entries and minors, with a simplified formula for odd lifting factors. A residue characterization identifies additional common factors of the minors and leads to a method for controlling the dimension through polynomial selection. We also give a condition for changing the minor generator without changing the code. Explicit polynomial constructions yield 13 quantum codes with verified minimum distances, including a $[[255,80,12]]$ code of rate $80/255$.

quant-pharXiv:2610.19459•Oct 15, 2026•0 citations

On the Application of Error-Correcting Codes with Low-Density Generator Matrix over Different Quantum Channels

Hanqing Lou, Javier Garcia‐Frias

We propose the use of linear codes with low-density generator matrix in the context of error correction over different quantum channels. The basic idea is to construct a Calderbank-Shor-Steane (CSS) code based on the generator matrix and the parity-check matrix of an LDGM code, applying row operations in both matrices to achieve the desired quantum rate. Decoding is performed in an iterative manner, using message passing over the corresponding graphs. The proposed codes allow greater flexibility and are easier to design than existing sparse-graph quantum codes, while leading to better performance.

•Apr 3, 2006•23 citations

Quantum codes over rings

Kenza Guenda, Thomas Aaron Gulliver

This paper considers the construction of quantum error correcting codes from linear codes over finite commutative Frobenius rings. We extend the Calderbank–Shor–Steane (CSS) construction to these rings. Further, quantum codes are extended to matrix product codes. Quantum codes over 𝔽pk are also obtained from linear codes over rings using the generalized Gray map.

International Journal of Quantum Information•Jun 1, 2014•17 citations
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 222-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.
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 222-sum of the cycle matroids of two identical book graphs Bn,cB_{n,c}Bn,c​, each consisting of ccc length-nnn cycles sharing one edge, using that shared edge for the sum. The resulting codes have parameters [2c(n−1),2c−1,2n−2][2c(n-1),2c-1,2n-2][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[8,3,4]_2[8,3,4]2​, [12,5,4]2[12,5,4]_2[12,5,4]2​, [12,3,6]2[12,3,6]_2[12,3,6]2​ and [16,3,8]2[16,3,8]_2[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-222 CSS codes, including a [[6,1,2]][[6,1,2]][[6,1,2]] example with dX=3d_X=3dX​=3 and dZ=2d_Z=2dZ​=2.
The paper also establishes that an oriented incidence matrix defines an [∣E∣,∣E∣−∣V∣+ω,g]q[|E|,|E|-|V|+\omega,g]_q[∣E∣,∣E∣−∣V∣+ω,g]q​ code over every finite field, where ω\omegaω counts connected components and ggg is graph girth. The quantum treatment is restricted to binary stabilizer codes, and the cycle-based quantum constructions presented have distance 222.
The correspondence between linear codes and representable matroids is well known. But a similar correspondence between quantum codes and matroids is not known. We show that representable symplectic matroids over a finite field Fqcorrespond to Fq-linear quantum codes. This connection is straightforward but it does not appear to have been made earlier in literature. This correspondence is made through isotropic subspaces. We show that Calderbank-Shor-Steane (CSS) codes correspond to homogenous symplectic matroids while graph states, which figure so prominently in measurement based quantum computation, correspond to a special class of symplectic matroids, namely Lagrangian matroids. This association is useful in that it enables the study of symplectic matroids in terms of quantum codes and vice versa. Furthermore, it has application in the study of quantum secret sharing schemes.
Linear codes constructed from combinatorial and geometric structures have played a central role in both classical and quantum coding theory. In this paper, we discuss a class of linear codes over finite fields, calledpolytope codes, obtained via defining sets derived from lattice polytopes. Unlike evaluation-based constructions, our approach exploits the intersection structure of polytope faces to directly control the algebraic and metric properties of the resulting codes. We develop a general defining-set framework for polytope codes and explicitly determine their lengths, dimensions, minimum distances, and Hamming weight distributions. This leads to infinite families of projective, few-weight, distance-optimal, and almost distance-optimal codes. Sufficient conditions for minimality are derived, resulting in new minimal codes that are well suited for applications to secret-sharing schemes. We further study the duals and hulls of polytope codes and provide explicit characterizations of self-orthogonal and linear complementary dual (LCD) families. One of the central results of the paper is a complete classification of quantum codes arising from polytope codes via the Calderbank-Shor-Steane (CSS) construction. We show that the geometry of face intersections fully determines whether the resulting quantum code is a standard CSS code, an LCD-based code, or an entanglement-assisted quantum error-correcting code, and we explicitly compute the required entanglement in the latter case. As a consequence, new families of binary, ternary, and prime-power quantum codes with previously unattained parameters are obtained. The proposed polytope-based framework unifies classical and quantum code constructions under a common geometric principle and opens new avenues for applications in cryptography, distributed storage, and quantum information processing.Mathematics Subject Classification. 94B05, 52B20, 11T71, 94A62, 94A45.
It is an important issue to search for self-orthogonal codes for construction of quantum codes by CSS construction (Calderbank-Sho-Steane codes); in quantum error correction, CSS codes are a special type of stabilizer codes constructed from classical codes with some special properties, and the CSS construction of quantum codes is a well-known construction. First, we employ hierarchical posets with two levels for construction of binary linear codes. Second, we find some necessary and sufficient conditions for these linear codes constructed using posets to be self-orthogonal, and we use these self-orthogonal codes for obtaining binary quantum codes. Finally, we obtain four infinite families of binary quantum codes for which the minimum distances are three or four by CSS construction, which include binary quantum Hamming codes with length n≥7. We also find some (almost) “optimal” quantum codes according to the current database of Grassl. Furthermore, we explicitly determine the weight distributions of these linear codes constructed using posets, and we present two infinite families of some optimal binary linear codes with respect to the Griesmer bound and a class of binary Hamming codes.
We construct quantum codes from codewords of a cyclic code and the minors of a polynomial matrix. The construction uses a two-row, three-column matrix whose minors yield a second matrix satisfying the CSS orthogonality condition. We derive the code dimension from the greatest common divisors of the entries and minors, with a simplified formula for odd lifting factors. A residue characterization identifies additional common factors of the minors and leads to a method for controlling the dimension through polynomial selection. We also give a condition for changing the minor generator without changing the code. Explicit polynomial constructions yield 13 quantum codes with verified minimum distances, including a [[255,80,12]][[255,80,12]][[255,80,12]] code of rate 80/25580/25580/255.
We propose the use of linear codes with low-density generator matrix in the context of error correction over different quantum channels. The basic idea is to construct a Calderbank-Shor-Steane (CSS) code based on the generator matrix and the parity-check matrix of an LDGM code, applying row operations in both matrices to achieve the desired quantum rate. Decoding is performed in an iterative manner, using message passing over the corresponding graphs. The proposed codes allow greater flexibility and are easier to design than existing sparse-graph quantum codes, while leading to better performance.