论文标题
组合优化问题中的欧几里得相关性：统计物理方法
Euclidean correlations in combinatorial optimization problems: a statistical physics approach
论文作者
论文摘要
在本文中，我从统计物理学的角度讨论了组合优化问题。起点是使物理学家与计算机科学家和数学家一起致力于这个美丽而深刻的话题的动机。我给出了复杂性理论的一些要素，并激发了为什么统计物理学的观点导致许多有趣的结果以及新问题。我讨论组合优化问题与自旋玻璃之间的联系。最后，我简要回顾了一些大偏差理论的主题，以此超出平均数量的方式。作为一个具体的例子，我展示了如何使用副本方法来探索著名的自旋玻璃（P-Spin Spherical模型）的大偏差。在第二章中，我专门研究欧几里得组合优化问题。特别是，我解释了为什么当这些问题嵌入有限的欧几里得空间中时，很难处理。我在一个维度中分析了几个特定问题，以解释一种相当通用的技术来处理一个维度的欧几里得组合优化问题。尽可能，并以详细的方式为旅行 - 萨尔斯曼 - 问题案例，我还讨论了如何以两个（以及更多）维度进行。在最后一章中，我概述了解决硬组合优化问题的有希望的方法：量子计算。在快速概述了量子计算范式之后，我详细讨论了所谓的量子退火算法的应用到匹配问题的特定情况下，还通过提供了最近的量子退火机的性能与配备透明度算法的经典超级计算机之间的性能。最后，我得出了工作的结论，并为将来的研究提出了一些有趣的方向。
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 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 specific problems 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, 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 and a classical super-computer equipped with an heuristic algorithm. Finally, I draw the conclusions of my work and I suggest some interesting directions for future studies.
