EUCLIDEAN CORRELATIONS IN COMBINATORIAL OPTIMIZATION PROBLEMS: A STATISTICAL PHYSICS APPROACH

In this thesis I discuss combinatorial optimization problems, from the statistical physics perspective. The starting point are the motivations which brought physicists together with computer scientists and mathematicians to work on this beautiful and deep topic. I give some elements of complexity theory, and I motivate why the point of view of statistical physics, although different from the one adopted in standard complexity theory, leads to many interesting results, as well as new questions. I discuss the connection between combinatorial optimization problems and spin glasses. Finally, I briefly review some topics of large deviation theory, as a way to go beyond average quantities. As a concrete example of this, I show how the replica method can be used to explore the large deviations of a well-known toy model of spin glasses, the p-spin spherical model. In the second chapter I specialize in Euclidean combinatorial optimization problems. In particular, I explain why these problems, when embedded in a finite dimensional Euclidean space, are difficult to deal with. I analyze several problems (the matching and assignment problems, the traveling salesman problem, and the 2-factor problem) in one dimension to explain a quite general technique to deal with one dimensional Euclidean combinatorial optimization problems. Whenever possible, and in a detailed way for the traveling-salesman problem case, I also discuss how to proceed in two (and also more) dimensions. In the last chapter I outline a promising approach to tackle hard combinatorial optimization problems: quantum computing. After giving a quick overview of the paradigm of quantum computation (and its differences with respect to the classical one), I discuss in detail the application of the so-called quantum annealing algorithm to a specific case of the matching problem, also by providing a comparison between the performance of a recent quantum annealer machine (the D-Wave 2000Q) and a classical super-computer equipped with an heuristic algorithm (an implementation of parallel tempering). Finally, I draw the conclusions of my work and I suggest some interesting directions for future studies.