View PDF HTML (experimental)

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 $\varepsilon$-relative accuracy in time polylogarithmic in the dimension $N$, specifically in time $\poly(\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. Our classical algorithm for the log-determinant runs in time $\polylog(N)\cdot s^{O(\sqrt{\kappa}\log(\kappa/\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.

Submission history

From: Roman Edenhofer [view email]
[v1] Wed, 24 Sep 2025 14:44:53 UTC (42 KB)
[v2] Mon, 10 Aug 2026 16:58:02 UTC (37 KB)