Skip navigation
Please use this identifier to cite or link to this item:
Title: Phase Transitions And Classical-Quantum Mixing in the Satisfiability Problem
Authors: Potirniche, Ionut-Dragos
Advisors: Sondhi, Shivaji
Contributors: Huse, David
Department: Physics
Class Year: 2014
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.
Extent: 93 pages
Type of Material: Princeton University Senior Theses
Language: en_US
Appears in Collections:Physics, 1936-2016

Files in This Item:
File SizeFormat 
Potirniche_Dragos.pdf1.02 MBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.