Quantum Adiabatic Evolution Algorithm and Quantum Phase Transition in 3-Satisfiability Problem

Simple item page
dc.creatorKnysh, S.
dc.creatorSmelyanskiy, V. N.
dc.date2006-02-10
dc.date.accessioned2026-07-07T07:01:38Z
dc.date.available2026-07-07T07:01:38Z
dc.descriptionIn this paper we show that the performance of the quantum adiabatic algorithm is determined by phase transitions in underlying problem in the presence of transverse magnetic field $Γ$. We show that the quantum version of random Satisfiability problem with 3 bits in a clause (3-SAT) has a first-order quantum phase transition. We analyze the phase diagram $γ=γ(Γ)$ where $γ$ is an average number of clauses per binary variable in 3-SAT. The results are obtained in a closed form assuming replica symmetry and neglecting time correlations at small values of the transverse field $Γ$. In the limit of $Γ=0$ the value of $γ(0)\approx$ 5.18 corresponds to that given by the replica symmetric treatment of a classical random 3-SAT problem. We demonstrate the qualitative similarity between classical and quantum versions of this problem.
dc.description30 pages, 7 figures
dc.identifierhttps://arxiv.org/abs/cond-mat/0602257
dc.identifierhttp://arxiv.org/abs/cond-mat/0602257
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/108338
dc.subjectDisordered Systems and Neural Networks
dc.subjectStatistical Mechanics
dc.subjectQuantum Physics
dc.titleQuantum Adiabatic Evolution Algorithm and Quantum Phase Transition in 3-Satisfiability Problem
dc.typetext

Files

Collections

arXiv