Dequantization and Hardness of Spectral Sum Estimation

Abstract

We give new dequantization and hardness results for estimating spectral sums of matrices, such as the log-determinant. Recent quantum algorithms have demonstrated that the logarithm of the determinant of sparse, well-conditioned, positive matrices can be approximated to $\epsilon$-relative accuracy in time polylogarithmic in the dimension $N$, specifically in time $\poly(\log(N), s, κ, 1/\varepsilon)$, where $s$ is the sparsity and $\kappa$ the condition number of the input matrix. We provide a simple dequantization of these techniques that preserves the polylogarithmic dependence on the dimension. Our classical algorithm for the log-determinant runs in time $\polylog(N)\cdot s^{O(\sqrtκ\log(κ/\varepsilon))}$ which constitutes an exponential improvement over previous classical algorithms in certain parameter regimes. We complement our classical upper bounds with complexity-theoretic limitations. We prove that estimating normalized traces of polynomial powers and inverses of log-local Hamiltonians to inverse-polynomial additive accuracy is DQC1-complete, resolving an open problem of Cade and Montanaro (TQC 2018) concerning the complexity of Schatten-$p$ norm estimation. Finally, we prove a general PP-completeness result for unnormalized spectral sums: under mild polynomial-approximability and nondegeneracy assumptions on $f$, estimating $\mathrm{tr}[f(A)]$ to constant additive accuracy is PP-complete.

We added an author contribution statement