Computing partition functions in the one clean qubit model

Anirban N. Chowdhury, Rolando D. Somma, Yigit Subasi

Published 2019-10-25Version 1

We 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/(\epsilon_{\text{rel}} \mathcal Z ))^2$, where $M$ is the dimension of the quantum system, $\mathcal Z$ is the partition function, and $\epsilon_{\text{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 $\mathcal Z$, our method may run faster than exact classical methods, whose complexities are polynomial in $M$. We also prove 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. To attain the desired relative precision, we develop a procedure based on a sequence of approximations within predetermined additive errors that may be of independent interest.