{"id":"arxiv/2609.40250","url":"https://arxiv.org/abs/2609.40250","tags":["quant-ph"],"score":0,"title":"An (almost) efficient classical algorithm for sampling from typical Gibbs states","domain":"quant-ph","source":"arxiv","authors":["Saleh Naghdi","Eric R. Anschuetz"],"reviews":0,"subject":"quant-ph","summary":"Gibbs state preparation has emerged as a potential avenue for quantum advantage in the study of physical systems. Although there is known advantage for computing local properties of worst-case Gibbs states, recent results suggest a different picture for average-case local systems: at temperatures where their Gibbs states can be efficiently prepared quantumly, quasi-polynomial time classical algorithms can also compute local expectation values. Yet this leaves open the possibility of an advantage under a stronger notion of simulation: sampling. Gibbs sampling underlies Boltzmann machine-based…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}