Short depth algorithm for high temperature Gibbs state sampling

Sampling from Gibbs states on a quantum computer is a notoriously hard problem. Even problems that are classically tractable can require large

overhead in resources or calibration. We propose a method based on sampling from a quasi-distribution consisting of products of mixed state on local clusters. We also employ a trick to reduce the 1-norm of the coefficients in the quasi-distribution, which drastically reduces the sampling overhead. The exact error bias of the procedure can be captured in a thermodynamic perturbation series.  By benchmarking the performance on a variety of local spin models we demonstrate the utility of this algorithm in the high-temperature/short correlation-length regime. Our algorithm also has the advantage of being employed to jump start known quantum imaginary time or virtual distillation algorithms to reach lower temperatures.