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

Abstract

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.

arXiv comment30 pages, 7 figures

References in corpus (6)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• The Entropy of the K-Satisfiability Problem
• Optimisation problems and replica symmetry breaking in finite connectivity spin-glasses
• Quantum Adiabatic Evolution Algorithms versus Simulated Annealing
• Adiabatic Quantum Computing in systems with constant inter-qubit couplings
• Percolation of frozen order in glassy combinatorial problems

Cited by in corpus (1)

• Quantum annealing: the fastest route to quantum computation?