Phase Transitions And Classical-Quantum Mixing in the Satisfiability Problem

Abstract

During the last few decades, intrigued by the resemblance between some hard combinatorial optimization problems and the physics of glassy systems, physicists have tried to understand why and how these sort of problems (known as NP-complete in the computer science jargon) are hard. To this end, they have employed a plethora of tools from classical statistical mechanics and, among other things, have proven that the random k-satis ability has a phase transition between a "solvable" and "unsolvable" phase which is intrinsically related to an easy-hard-easy transition: instances are easy to decide well within the satis able or unsatisfiable regimes, but are exponentially hard to determine near the critical point. In this thesis, we focus both on classical and quantum complexity theory. After presenting some of the most important results from these fields such as the existence of "hard" problems for classical and quantum computers, we embark on the study of random ensembles of the satis ability problem. We show how these are related to the study of graph theoretical questions and why there exists a phase transition for the random k-SAT and k-QSAT. Motivated by the fact that the "UNSAT-ness" of the latter problem is a purely graph geometric property, we study the classical-quantum mixing in random satis- ability in order to see how this peculiarity emerges. Specifically, we define a new problem which we call (N;M;K)-k-SAT and for k = 2: we implement an exact algorithm proposed by Bravyi and ll in some minor gaps in its construction; we obtain a complete numerical phase diagram; conjecture an analytic expression for the phase boundary in the thermodynamic limit; show that the SAT-UNSAT transition corresponds to an easy-hard-easy transition in the resolution time pattern; and outline a finite size scaling analysis. Finally, to tackle (N;M;K)-k-SAT for k > 2, we present a formalism based on degenerate perturbation theory and report some hints of clustering.