CONTACTS
 Coordinator
Diego Dalvit

Quantum Lunch Location:
TDivision Conference Room, TA3,
Building 123, Room 121

Quantum Institute: Visitor Schedule
The Quantum Lunch is regularly held on Thursdays in the Theoretical Division Conference Room, TA3, Building 123, Room 121. For more information, contact Diego Dalvit.
August 3 , 2006
12:30 PM
Vadim Smelyanskiy,
NASA Ames Research Center
Quantum Annealing and Quantum Phase Transition in Satisfiability Problem
Abstract
We describe a Quantum Annealing for finding a ground state of a classical spin system. A system is subject to a transverse magnetic field É° that is slowly varying from a very large to zero value. If the system evolution is adiabatic then Quantum Annealing continuously connects the trivial initial ground state to a ground state at zero transverse field corresponding to the solution of the optimization problem at hand that can be retrieved by measurements. We will describe experimental and theoretical studies of Quantum Annealing in large spin systems. We then introduce a socalled random Satisfiability problem with 3 bits in a clause corresponding to a dilute longrange spin glass model defined on a random graph. We show that when Quantum Annealing is used to solve this problem the system passes through the vicinity of a first order quantum phase transition. We analyze the phase diagram É_{ì} vs É° where É_{ì} is a number clauses per spin in the Satisfiability problem. We present a closed form solution assuming replica symmetry and neglecting time correlations at small values of the transverse field É°. We analyze the structure of lowlying eigenstates and demonstrate the qualitative similarity between a classical and a quantum annealing. Finally, we discuss the connection of a "computational power" of Quantum Annealing for the Satisfiability problem to the onset of the quantum phase transition and propose a scheme for its experimental observation by mapping the longrange model onto a realistic Ising spin model with nearestneighbor interactions.
