Classical and quantum statistical analysis of a constraint satisfaction problem

Peschina, Markus

Master Thesis

Classical and quantum statistical analysis of a constraint satisfaction problem

Peschina, M. (Corresponding author)FZJ*

2010
Forschungszentrum Jülich GmbH Zentralbibliothek, Verlag Jülich

Jülich : Forschungszentrum Jülich GmbH Zentralbibliothek, Verlag, Berichte des Forschungszentrums Jülich 4334, IV, 80 p. (2010) = Mainz, Univ., Masterarbeit, 2010

Please use a persistent id in citations: http://hdl.handle.net/2128/4328

Report No.: Juel-4334

Abstract: The 3-SAT problem for the case of special USA (unique satisfying assignment) realizations has been studied in a classical and in a quantum mechanical way. For the classical simulations Wang-Landau and Multicanonical sampling is utilized to estimate the density of states (DOS) of an ensemble of 4000 realizations for different N and r values. Using the DOS and other output of the sampling algorithms, many thermodynamic functions and distributions are obtained. Energy, specific heat and microcanonical and canonical distributions for USA realizations are discussed. Wang-Landau sampling is also employed in the ground-state overlap direction, rather than in the energy direction, and the canonical distribution is measured. A static property of our realizations, denoted as barrier B$_{0}$, which is a probability ratio in the canonical distribution, can be linear related to the logarithm of the ground state search time $\tau$ of the Multicanonic sampling in energy direction for high r > 7. For all values of r considered in this work, the typical search time for the unique ground state scales exponentially with the number of spins. In the second part of this work, the quantum adiabatic (QA) algorithm is considered for solving the 3-SAT problem. For small systems, the Lanczos algorithm and the [...]

Classification: