Efficient classical algorithms for quantum Gibbs states up to phase transitions

Estimating thermal expectations of local observables is a natural target for quantum advantage. In this talk, I will discuss recent work which shows that a simple classical algorithm based on analytic continuation can estimate thermal expectations efficiently in quasi-polynomial time for many inherently quantum models. Notably, our results apply to the Sachdev-Ye-Kitaev (SYK) model at any constant temperature---including when the thermal state is highly entangled and satisfies polynomial quantum circuit lower bounds, a sign problem, and nontrivial instance-to-instance fluctuations. We also give a rigorous proof that the same classical algorithm succeeds beyond an entanglement transition in Gibbs states. Finally, we comment on the relevance of these results to other quantum problems such as estimating the out-of-time-order correlator (OTOC). This talk is based on joint work with Alexander Zlokapa.

*We strongly encourage attendees to use their full name (and if possible, their UMD credentials) to join the zoom session.*