  We present two algorithms, one quantum and one classical, for estimating
partition functions of quantum spin Hamiltonians. The former is a DQC1
(Deterministic quantum computation with one clean qubit) algorithm, and the
first such for complex temperatures. The latter, for real temperatures,
achieves performance comparable to a state-of-the-art DQC1 algorithm [Chowdhury
et al. Phys. Rev. A 103, 032422 (2021)]. Both our algorithms take as input the
Hamiltonian decomposed as a linear combination Pauli operators. We show this
decomposition to be DQC1-hard for a given Hamiltonian, providing new insight
into the hardness of estimating partition functions.
