Commutative algebra and coding theory, with applications to quantum error-correction

Abstract

Algebraic Coding Theory plays an important role not only in many different aspects of communication but also in cryptography and quantum computing. In this thesis we are interested in using tools from Commutative Algebra to derive properties of linear codes. We focus mainly on evaluation codes, since they have a natural connection to Commutative Algebra, but we also consider other types of codes such as cyclic codes (which can be viewed as subfield subcodes of evaluation codes) or matrix-product codes. Many aspects of evaluation codes can be understood by means of the vanishing ideal of the set of points considered. A natural question that arises is how to compute this vanishing ideal. In the projective setting one usually has to compute the radical of an ideal. We give an alternative and more efficient way of computing the vanishing ideal by using the saturation with respect to the homogeneous maximal ideal. Another option to study evaluation codes over the projective space is to consider a set of fixed representatives of the points, regarded as a subset of the affine space, and its vanishing ideal. We give a universal Gröbner basis for this vanishing ideal when the set of points corresponds to certain subsets of the projective line, or to the whole projective space. Obtaining long codes with good parameters over a small finite field, which is desirable for applications, is a complicated problem in general. One approach to achieve this is to consider subfield subcodes. We obtain bases for the subfield subcodes of projective Reed-Solomon codes and projective Reed-Muller codes in many cases. We also give an alternative approach using a recursive construction for projective Reed-Muller codes. The interest of the generalized Hamming weights of a linear code originates from the fact that they determine its performance on the wire-tap channel of type II, but many other applications have been found for them since then. We provide lower and upper bounds for the generalized Hamming weights of projective Reed-Muller codes, determining the true values in many cases. We also provide bounds for the generalized Hamming weights of matrix-product codes. As a sample of our results, we obtain the exact value of the generalized Hamming weights of matrix-product codes obtained with two Reed-Solomon codes. The development of reliable quantum computing and communication requires error-correction to deal with noise and decoherence. To perform error-correction, we can consider stabilizer quantum codes. The CSS construction provides a way to construct such codes using a pair of classical linear codes. The dimension of the relative hull of this pair of classical codes gives the minimum number required of maximally entangled pairs. We have used the subfield subcodes of projective Reed-Solomon codes to construct both symmetric and asymmetric entanglement-assisted quantum error-correcting codes. Moreover, we have computed the hulls of projective Reed-Muller codes over the projective plane, determining all the parameters of the corresponding quantum codes. We also study how to change the dimension of the hull of projective Reed-Muller codes by considering monomially equivalent codes, giving rise to families of codes with a flexible amount of entanglement. One of the main problems for quantum computing is the fault-tolerant implementation of non-Clifford gates. We study CSS-T codes, which are quantum codes derived from the CSS construction that support the transversal T gate. We give a new characterization of CSS-T codes, and we use it to determine which CSS-T codes can be constructed from cyclic codes. Moreover, we also obtain a propagation rule for nondegenerate CSS-T codes, and we use it to obtain CSS-T codes with better parameters than those available in the literature.

La Teoría de Códigos Algebraica juega un papel importante no solo en muchos aspectos diferentes de la comunicación, sino también en la criptografía y la computación cuántica. En esta tesis, nos interesa utilizar herramientas de Álgebra Conmutativa para derivar propiedades de códigos lineales. Nos centramos principalmente en los códigos de evaluación, ya que tienen una conexión natural con el Álgebra Conmutativa, pero también consideramos otros tipos de códigos, como los códigos cíclicos (que pueden ser vistos como subcódigos subcuerpo de códigos de evaluación) o códigos producto de matrices. Muchos aspectos de los códigos de evaluación pueden entenderse mediante el ideal de anulación del conjunto de puntos considerado. Una pregunta natural que surge es cómo calcular este ideal de anulación. En el caso proyectivo, en general hay que calcular el radical de un ideal. Damos una forma alternativa y más eficiente de calcular el ideal de anulación mediante la saturación con respecto al ideal homogéneo maximal. Otra opción para estudiar códigos de evaluación en el espacio proyectivo es considerar un conjunto de representantes fijados de los puntos, considerados como un subconjunto del espacio afín, y su ideal de anulación. Proporcionamos una base de Gröbner universal para este ideal de anulación cuando el conjunto de puntos corresponde a ciertos subconjuntos de la recta proyectiva o a todo el espacio proyectivo. Obtener códigos largos con buenos parámetros sobre un cuerpo finito pequeño, lo cual es deseable para aplicaciones, es un problema complicado en general. Un enfoque para lograr esto es considerar subcódigos subcuerpo. Obtenemos bases para los subcódigos subcuerpo de códigos Reed-Solomon proyectivos y códigos Reed-Muller proyectivos en muchos casos. También damos un enfoque alternativo utilizando una construcción recursiva para códigos Reed-Muller proyectivos. El interés en los pesos de Hamming generalizados de un código lineal se origina en el hecho de que determinan su rendimiento en el canal “wire-tap” de tipo II, pero se han encontrado muchas otras aplicaciones para ellos desde entonces. Proporcionamos cotas inferiores y superiores para los pesos de Hamming generalizados de los códigos Reed-Muller proyectivos, determinando los valores reales en muchos casos. También proporcionamos cotas para los pesos de Hamming generalizados de códigos producto de matrices. Como muestra de nuestros resultados, obtenemos el valor exacto de los pesos de Hamming generalizados de códigos producto de matrices obtenidos con dos códigos Reed-Solomon. El desarrollo de la computación y comunicación cuántica fiable requiere corrección de errores para lidiar con el ruido y la decoherencia. Para realizar la corrección de errores, podemos considerar códigos cuánticos estabilizadores. La construcción CSS proporciona una manera de construir tales códigos utilizando un par de códigos lineales clásicos. La dimensión del “hull” relativo de este par de códigos clásicos da el número mínimo requerido de pares entrelazados maximalmente. Hemos utilizado subcódigos subcuerpo de códigos Reed-Solomon proyectivos para construir tanto códigos cuánticos asistidos por entrelazamiento simétricos como asimétricos. Además, hemos calculado los “hulls” de códigos Reed-Muller proyectivos sobre el plano proyectivo, determinando todos los parámetros de los códigos cuánticos correspondientes. También estudiamos cómo cambiar la dimensión del “hull” de los códigos Reed-Muller proyectivos considerando códigos monomialmente equivalentes. Uno de los principales problemas para la computación cuántica es la implementación tolerante a fallos de puertas “non-Clifford”. Estudiamos los códigos CSS-T, que son códigos cuánticos derivados de la construcción CSS que soportan la puerta transversal T. Damos una nueva caracterización de los códigos CSS-T, y la usamos para determinar qué códigos CSS-T pueden construirse a partir de códigos cíclicos. Además, también obtenemos una regla de propagación para los códigos CSS-T no degenerados, y la usamos para obtener códigos CSS-T con mejores parámetros que los disponibles en la literatura.