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
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 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.