Elizabeth Crosson, California Institute of Technology
The equilibrium states of Hamiltonians without a sign problem can in many cases be efficiently sampled using classical Markov chain Monte Carlo methods. These simulation algorithms present a challenge to the possibility of obtaining quantum speedups using transverse-field quantum annealing, and in this talk I'll describe rigorous results on the convergence of simulated quantum annealing to a class of problems that take exponential time to solve by local search. One way of restoring the prospect of a quantum speed up is to consider quantum annealing architectures with a sign problem that cannot be removed by any change of the local basis. I'll show that the presence of such an inevitable sign problem can be efficiently verified in terms of a graph theoretic condition, which supports the certification of next-generation quantum annealing devices that are expected to defy classical simulation methods.