Quantum álgorithms for the combinatorial invariants of numerical semigroups

Abstract

It was back in spring 2014 when the author of this doctoral dissertation was finishing its master thesis, whose main objective was the understanding of Peter W. Shor’s most praised result, a quantum algorithm capable of factoring integers in polynomial time. During the development of this master thesis, me and my yet-tobe doctoral advisor studied the main aspects of quantum computing from a purely algebraic perspective. This research eventually evolved into a sufficiently thorough canvas capable of explaining the main aspects and features of the mentioned algorithm from within an undergraduate context. Just after its conclusion, we seated down and elaborated a research plan for a future Ph.D. thesis, which would expectantly involve quantum computing but also a branch of algebra whose apparently innocent definitions hide some really hard problems from a computational perspective: the theory of numerical semigroups. As will be seen later, the definition of numerical semigroup does not involve sophisticated knowledge from any somewhat obscure and distant branch of the tree of mathematics. Nonetheless, a number of combinatorial problems associated with these numerical semigroups are extremely hard to solve, even when the size of the input is relatively small. Some examples of these problems are the calculations of the Frobenius number, the Apéry set, and the Sylvester denumerant, all of them bearing the name of legendary mathematicians. This thesis is the result of our multiple attempts to tackle those combinatorial problems with the help of a hypothetical quantum computer. First, Chapter 2 is devoted to numerical semigroups and computational complexity theory, and is divided into three sections. In Section 2.1, we give the formal definition of a numerical semigroup, along with a description of the main problems involved with them. In Section 2.2, we sketch the fundamental concepts of complexity theory, in order to understand the true significance within the inherent hardness concealed in the resolution of those problems. Finally, in Section 2.3 we prove the computational complexity of the problems we aim to solve. Chapter 3 is the result of our outline of the theory of quantum computing. We give the basic definitions and concepts needed for understanding the particular place that quantum computers occupy in the world of Turing machines, and also the main elements that compose this particular model of computation: quantum bits and quantum entanglement. We also explain the two most common models of quantum computation, namely quantum circuits and adiabatic quantum computers. For all of them we give mathematical definitions, but always having in mind the physical experiments from which they stemmed. Chapter 4 is also about quantum computing, but from an algorithmical perspective. We present the most important quantum algorithms to date in a standardized way, explaining their context, their impact and consequences, while giving a mathematical proof of their correctness and worked-out examples. We begin with the early algorithms of Deutsch, Deutsch-Jozsa, and Simon, and then proceed to explain their importance in the dawn of quantum computation. Then, we describe the major landmarks: Shor’s factoring, Grover’s search, and quantum counting. Chapter 5 is the culmination of all previously explained concepts, as it includes the description of various quantum algorithms capable of solving the main problems inside the branch of numerical semigrops. We present quantum circuit algorithms for the Sylvester denumerant and the numerical semigroup membership, and adiabatic quantum algorithms for the Ap´ery Set and the Frobenius problem. We also describe a C++ library called numsem, specially developed within the context of this doctoral thesis and which helps us to study the computational hardness of all previously explained problems from a classical perspective. This thesis is intended to be autoconclusive at least in the main branches of mathematics in which it is supported; that is to say numerical semigroups, computational complexity theory, and quantum computation. Nevertheless, for the majority of concepts explained here we give references for the interested reader that wants to delve more into them.