Preparing thermal (Gibbs) states is a common task in physics and computer science. The mixing time denotes the time needed for a Gibbs sampler to approximate a target Gibbs state. Lower bounding the mixing time in quantum systems is more challenging than in classical systems due to the lack of established tools. I will present a method based on a quantum bottleneck lemma that generalizes classical techniques, focusing on quantum analogs of distance, such as Bohr spectrum jumps and operator locality. Using this lemma, we can establish exponential lower bounds on mixing times for Gibbs samplers across several Hamiltonian families. Examples include random K-SAT, spin glasses, stabilizer codes, and models with transverse fields, such as the ferromagnetic 2D transverse field Ising model.
Back to Long Programs
Copyright. All Rights Reserved.