RSS icon
Twitter icon
Facebook icon
Vimeo icon
YouTube icon

The power of adiabatic quantum computation with no sign problem

July 22, 2020 - 11:00am
Matthew Hastings
Microsoft Research

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