A quantum algorithm for estimating the determinant

Abstract

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 $\hat{I}\mu$ in time $\mathcal{O}(\log n/\hat{I}{\mu }^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(\hat{I}{»}_j)$, where $\hat{I}{»}_j$ are the matrix eigenvalues. For example, the algorithm allows the efficient estimation of the partition function $Z({\hat{I}}^2)={\sum }_j{e}^{-{\hat{I}}^2{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$.

3 pages + Appendices. Bibliography updated to cite a similar algorithm