Matthew Hastings, Microsoft

The Power of Adiabatic Quantum Computation With No Sign Problem

Abstract:
Hamiltonians with "no sign problem" are very important because they can often be efficiently studied on classical computers using algorithms such as path integral Monte Carlo. This leads to the question: how computationally difficult are these Hamiltonians? Can we always efficiently simulate them? One obstacle to simulating them can occur due to glassy physics, and problems with equilibration are well-known. However, I'll discuss other topological obstructions that can make them difficult to simulate even in the case that we consider adiabatic evolution of these Hamiltonians. To be precise and formal, I'll show that this problem is hard "relative to an oracle" which I will explain. This is based on [2005.03791] The Power of Adiabatic Quantum Computation with No Sign Problem (arxiv.org), and [2011.09495] (Sub)Exponential advantage of adiabatic quantum computation with no sign problem (arxiv.org) is a follow-up by Gilyen and Vazirani tightening the result and simplifying the construction.