  Preparing quantum thermal states on a quantum computer is in general a
difficult task. We provide a procedure to prepare a thermal state on a quantum
computer with a logarithmic depth circuit of local quantum channels assuming
that the thermal state correlations satisfy the following two properties: (i)
the correlations between two regions are exponentially decaying in the distance
between the regions, and (ii) the thermal state is an approximate Markov state
for shielded regions. We require both properties to hold for the thermal state
of the Hamiltonian on any induced subgraph of the original lattice. Assumption
(ii) is satisfied for all commuting Gibbs states, while assumption (i) is
satisfied for every model above a critical temperature. Both assumptions are
satisfied in one spatial dimension. Moreover, both assumptions are expected to
hold above the thermal phase transition for models without any topological
order at finite temperature. As a building block, we show that exponential
decay of correlation (for thermal states of Hamiltonians on all induced
subgraph) is sufficient to efficiently estimate the expectation value of a
local observable. Our proof uses quantum belief propagation, a recent
strengthening of strong sub-additivity, and naturally breaks down for states
with topological order.
