Abstract
We study the sample complexity of estimating the von Neumann entropy of an unknown d-dimensional quantum state. All previously known estimators require Ω(d²) samples, and plug-in estimators are known to face a quadratic barrier. We give the first subquadratic-sample estimator: for additive error ε, our estimator uses O(d² log²(log(d)) log(1/ε)/ε² log²(d) + log²(d/ε)/ε²) samples. In particular, for constant ε, the complexity is O_ε(d²log²(log(d))/log²(d))=o(d²). Our analysis introduces a new pinching inequality that bounds the entropy loss under a space direct-sum decomposition, together with a bias-corrected estimator for large eigenvalues and a new bounded-coefficient polynomial estimator for small eigenvalues.