Quantum Lunch Location:
T-Division Conference Room, TA-3,
Building 123, Room 121
Quantum Institute: Visitor Schedule
The Quantum Lunch is regularly held on Thursdays in the Theoretical Division Conference Room, TA-3, Building 123, Room 121.
For more information, contact Diego Dalvit.
August 3 , 2006
NASA Ames Research Center
Quantum Annealing and Quantum Phase Transition in Satisfiability Problem
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 so-called random Satisfiability problem with 3 bits in a clause corresponding to a dilute long-range 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 low-lying 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 long-range model onto a realistic Ising spin model with nearest-neighbor interactions.