Computing partition functions in the one clean qubit model*

In this talk we will present a method to approximate partition functions of quantum systems using mixed-state quantum computation. For non-negative Hamiltonians, our method runs on average in time almost linear in (M/(ε_relZ))², where M is the dimension of the quantum system, Z is the partition function, and ε_rel is the relative precision. It is based on approximations of the exponential operator as linear combinations of certain operations related to block-encoding of Hamiltonians or Hamiltonian evolutions. The trace of each operation is estimated using a standard algorithm in the one clean qubit model. For large values of Z, our method may run faster than exact classical methods, whose complexities are polynomial in M. Using this method we will demonstrate that a version of the partition function estimation problem within additive error is complete for the so-called DQC1 complexity class, suggesting that our method provides an exponential speedup.