Roman Edenhofer

In this work, we present 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 $\varepsilon$-relative accuracy in time polylogarithmic in the dimension~$N$, specifically in time~$\mathrm{poly}(\mathrm{log}(N), s, \kappa, 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, at the cost of worse scaling in the sparsity, condition number, and accuracy. Our classical algorithm runs in time~$\mathrm{poly}\mathrm{log}(N)\cdot s^{O(\sqrt{\kappa}\log \kappa/\varepsilon)}$ which constitutes an exponential improvement over previous classical algorithms in certain parameter regimes. In addition, we prove $\mathsf{DQC}1$-completeness for estimating specific spectral sums such as the trace of the inverse and the trace of matrix powers with analogous parameter scalings as the quantum algorithms for the log-determinant in the case of log-local Hamiltonians. The latter solves a main open problem posed by Cade and Montanaro (TQC 2018) and is closely related to the complexity of Schatten $p$-norm estimation. It further shows that the parameter scalings of known quantum algorithms are not achievable classically, assuming~$\mathsf{BPP}\subsetneq\mathsf{DQC}1$. Further, we also consider a different input model where instead of a classical description of a sparse matrix, we are given a block-encoding of it and analyze the complexity of spectral sum estimation in this model. We obtain $\mathsf{DQC}1$-completeness of estimating $\mathrm{tr}[f(A)]$ in this model in a very general way, in particular whenever $f$ and $f^{-1}$ are Lipschitz continuous with bounded Lipschitz constants. We conclude our work with $\mathsf{BQP}$-hardness and $\mathsf{PP}$-completeness results on the estimation of the log-determinant.