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

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

2006-02-10

arxiv.org/abs/cond-mat/0602257v1

Physics

Condensed Matter

Disordered Systems and Neural Networks

30 pages, 7 figures

Scientific paper

In 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 $\Gamma$. 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 $\gamma=\gamma(\Gamma)$ where $\gamma$ 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 $\Gamma$. In the limit of $\Gamma=0$ the value of $\gamma(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.

Affiliated with

Also associated with

No associations

Rating

Quantum Adiabatic Evolution Algorithm and Quantum Phase Transition in 3-Satisfiability Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Adiabatic Evolution Algorithm and Quantum Phase Transition in 3-Satisfiability Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Adiabatic Evolution Algorithm and Quantum Phase Transition in 3-Satisfiability Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-599914