Optimal von Neumann Entropy Estimation

Abstract

We show that the von Neumann entropy of an unknown $d$-dimensional quantum state $\rho$ can be estimated to within additive error $\epsilon$ using \[ Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)(1+\varepsilon\log^2(d))} + \frac{\log^2(d)}{\varepsilon^2}\right) \] samples of $\rho$, matching the lower bound due to Wang (2026). Our estimator is based on a high-degree approximation polynomial and the main technical challenge is bounding its variance despite the large polynomial degree. We overcome this using a quantum Hoeffding decomposition, which preserves cancellations between different polynomial terms and reduces the analysis to derivative bounds for the approximation polynomial.

arXiv comment22 pages, 1 table, 1 algorithm. Improved the sample complexity to optimal