  The partition function is an essential quantity in statistical mechanics, and
its accurate computation is a key component of any statistical analysis of
quantum system and phenomenon. However, for interacting many-body quantum
systems, its calculation generally involves summing over an exponential number
of terms and can thus quickly grow to be intractable. Accurately and
efficiently estimating the partition function of its corresponding system
Hamiltonian then becomes the key in solving quantum many-body problems. In this
paper we develop a hybrid quantum-classical algorithm to estimate the partition
function, utilising a novel Clifford sampling technique. Note that previous
works on quantum estimation of partition functions require
$\mathcal{O}(1/\epsilon\sqrt{\Delta})$-depth quantum
circuits~\cite{Arunachalam2020Gibbs, Ashley2015Gibbs}, where $\Delta$ is the
minimum spectral gap of stochastic matrices and $\epsilon$ is the
multiplicative error. Our algorithm requires only a shallow
$\mathcal{O}(1)$-depth quantum circuit, repeated $\mathcal{O}(1/\epsilon^2)$
times, to provide a comparable $\epsilon$ approximation. Shallow-depth quantum
circuits are considered vitally important for currently available NISQ (Noisy
Intermediate-Scale Quantum) devices.
