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

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 \cite{bergamaschi2024sample}. 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…

• NS
  National Science Foundation

  Awards: 2120757, OMA-2120757, 1840340
• UD
  U.S. Department of Energy

  Award: OMA-2120757
• OO
  Office of Science
• AS
  Advanced Scientific Computing Research
• NS
  National Science Foundation Graduate Research Fellowship Program

  Award: DGE1840340