Slow mixing from quantum bottlenecks

In classical algorithms, tools such as the overlap gap property and free energy barrier are used to provide lower bounds for algorithms that are local, stable, or low-degree. In this talk, we review quantum algorithms for Gibbs sampling and show that they face analogous obstructions due to a general quantum bottleneck lemma. When applied to Metropolis-like algorithms and classical Hamiltonians, our result reproduces classical slow mixing arguments. Unlike previous techniques to bound mixing times of quantum Gibbs samplers, however, our bottleneck lemma provides bounds for non-commuting Hamiltonians. We apply it to systems such as random classical CSPs, quantum code Hamiltonians, and the transverse field Ising model. Key to our work are two notions of distance, which we use to measure the locality of quantum samplers and to construct the bottleneck.