A quantum algorithm for estimating the determinant

We present a quantum algorithm for estimating the matrix determinant based on quantum spectral sampling. The algorithm estimates the logarithm of the determinant of an $n\times n$ positive sparse matrix to an accuracy $\epsilon$ in time $\mathcal{O}(\log n\mathrm{/}{\epsilon }^3)$, exponentially faster than previously existing classical or quantum algorithms that scale linearly in $n$. The quantum spectral sampling algorithm generalizes to estimating any quantity ${\sum }_{j}f({\lambda }_j)$, where ${\lambda }_j$ are the matrix eigenvalues. For example, the algorithm allows the efficient estimation of the partition function $Z(\beta )={\sum }_j{e}^{-\beta E_j}$ of a Hamiltonian system with energy eigenvalues $E_j$, and of the entropy $S=-{\sum }_j{p}_j\log p_j$ of a density matrix with eigenvalues $p_j$.