Yigit Subasi

We present algorithms to evaluate partition functions of quantum Hamiltonians using mixed-state quantum computation, specifically the DQC1 model of computation which requires only one pure qubit. Our algorithm provides an additive-error estimate to the normalized partition function in time that is polynomial in the number of qubits, for a large class of Hamiltonians. This implies that a variant of the partition function problem, that was previously shown to be hard for the complexity class DQC1 by Brandao, is in fact DQC1-complete. Our algorithm is based on approximations of the exponential operator as linear combinations of unitaries, which are related to block-encoding of Hamiltonians or Hamiltonian evolutions. We then extend our results to give an algorithm that estimates the partition function within a desired relative error. Towards this end, we develop a procedure based on a sequence of approximations within predetermined additive errors that may be of independent interest.