The power of adiabatic quantum computation with no sign problem
MATHEMATICAL PICTURE LANGUAGE
Matthew Hastings - Microsoft (Station Q and Redmond)
Interference is an essential part of quantum mechanics. However, an important class of Hamiltonians considered are those with "no sign problem", where all off-diagonal matrix elements of the Hamiltonian are non-negative. This means that the ground state wave function can be chosen to have all amplitudes real and positive. In a sense, no destructive interference is possible for these Hamiltonians so that they are "almost classical", and there are several simulation algorithms which work well in practice on classical computers today. In this talk, I'll discuss what happens when one considers adiabatic evolution of such Hamiltonians, and show that they still have some power that cannot be efficiently simulated on a classical computer; to be precise and formal, I'll show this "relative to an oracle", which I will explain. I'll discuss implications for simulation of these problems and open questions.