David Gosset: Small gaps, localization, and the quantum adiabatic algorithm

Tuesday, October 18, 2011 12:00 pm - 1:00 pm EDT (GMT -04:00)

Abstract

Stoquastic Hamiltonians are the class of Hamiltonians that can be studied numerically using standard Quantum Monte Carlo methods--these are the Hamiltonians which do not suffer from the sign problem. These Hamiltonians can also be easier to study analytically because of their connection to nonnegative matrices. In the first part of this talk I will review the arsenal of analytic and numerical tools pertaining to stoquastic Hamiltonians. I will then discuss a variational lower bound for the ground state energy of these Hamiltonians. I will show how this lower bound can be used to solve exactly for the ground state energy per spin for a transverse field quantum spin system. This model exhibits a "delocalized" to "localized" first order phase transition associated with a minimum eigenvalue gap that is exponentially small as a function of the system size. I will discuss the relevance of these results to the quantum adiabatic algorithm. Based on joint work with Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Peter Shor.