Intrinsic sign problems and ground state sampling complexity

The equilibrium states of quantum systems without a sign problem can in many cases be efficiently sampled using classical Markov chain Monte Carlo algorithms.   These classical algorithms challenge the possibility of obtaining quantum speedups using transverse-field quantum annealing, and this has motivated efforts to design next-generation quantum annealing architectures with a sign problem that cannot be removed by any change of the local basis.  In this talk I'll explain how to detect and certify the presence of such intrinsic sign problems, which can be used to generate ground state probability distributions that defy efficient classical simulations.