Graph and matroid methods build new classical and quantum codes
New Methods for Constructing Classical and Quantum Codes from Graphs and Matroids
Discrete Mathematics
Summary
Finding ways to make reliable codes for data and quantum computing is important. The authors show how to create such codes from pictures made of points and lines called graphs, and mathematical structures called matroids. They explain how to build classical codes that are very strong for their size and how this approach also helps make special quantum codes. Their work connects the shape of these graphs and matroids to the properties needed in error-correcting codes.
What this means in practice
- •For quantum hardware developers: Construct CSS quantum error-correcting codes based on graph and matroid properties to improve quantum memory reliability.
- •For communications engineers: Design binary error-correcting codes with maximal minimum distance for specified lengths using constructions from book graphs.
Authors
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.