Quantum álgorithms for the combinatorial invariants of numerical semigroups

Abstract

En esta tesis doctoral investigamos las posibilidades que ofrece la computación cuántica a la hora de resolver los problemas de mayor carga computacional dentro del ámbito de los semigrupos numéricos. Para ello, primero hacemos un resumen de la teoría de semigrupos numéricos, poniendo especial énfasis en los problemas de pertenencia a un semigrupo numérico, cálculo del número de Frobenius y del conjunto de Apéry, y cálculo del denumerante de Sylvester. Después, hacemos uso de las máquinas de Turing y de la teoría de la complejidad computacional para demostrar que, efectivamente, los problemas antes mencionados son difíciles de resolver, y explicamos qué significa exactamente esa dificultad dentro de este contexto. En segundo lugar, dedicamos dos capítulos a la computación cuántica, para explicar desde el punto de vista de las matemáticas, y más concretamente del álgebra, cómo funcionan los diferentes modelos de computación cuántica, tanto el de puertas como el adiabático. Tomando este lenguaje como base, explicamos los principales algoritmos cuánticos que se han ido desarrollando en los últimos treinta años: Deutsch-Jozsa, Simon, factorización de Shor, búsqueda de Grover, y derivados. Por último, desarrollamos varios algoritmos cuánticos usando ambos modelos para los principales problemas relacionados con los semigrupos numéricos, que forman parte del resultado principal de esta tesis doctoral. Explicamos un algoritmo de puertas para resolver los problemas de pertenencia a un semigrupo y del cálculo del denumerante de Sylvester, y un algoritmo adiabático que permite calcular el número de Frobenius a partir del conjunto de Apéry. Dentro de este capítulo, explicamos también una librería de funciones desarrollada en C++ que ayuda a evaluar los diferentes algoritmos dentro del modelo clásico de computación, y también comentamos nuestra experiencia resolviendo pequeñas instancias con el ordenador cuántico D-Wave de la University of Southern California.