Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1)-Local Hamiltonians

Quantum 10, 1981 (2026).

https://doi.org/10.22331/q-2026-01-22-1981

Sampling from Gibbs states – states corresponding to system in thermal equilibrium – has recently been shown to be a task for which quantum computers are expected to achieve super-polynomial speed-up compared to classical computers, provided the locality of the Hamiltonian increases with the system size [1]. We extend these results to show that this quantum advantage still occurs for Gibbs states of Hamiltonians with O(1)-local interactions at constant temperature by showing classical hardness-of-sampling and demonstrating such Gibbs states can be prepared efficiently using a quantum computer. In particular, we show hardness-of-sampling is maintained even for 5-local Hamiltonians on a 3D lattice. We additionally show that the hardness-of-sampling is robust when we are only able to make imperfect measurements.