Breaking the Quadratic Barrier for von Neumann Entropy Estimation

We study the sample complexity of estimating the von Neumann entropy of an unknown $d$-dimensional quantum state. All previously known estimators require $\mathrm{\Omega }(d^2)$ samples, and plug-in estimators are known to face a quadratic barrier. We give the first subquadratic-sample estimator: for additive error $\epsilon$, our estimator uses $$O\text{\hspace{0.17em}⁣}(\frac{d^2{\log }^2(\log (d))\log (1\mathrm{/}\epsilon )}{{\epsilon }^2{\log }^2(d)}+\frac{{\log }^2(d\mathrm{/}\epsilon )}{{\epsilon }^2})$$ samples. In particular, for constant $\epsilon$, the complexity is $O_{\epsilon }(d^2{\log }^2(\log (d))\mathrm{/}{\log }^2(d))=o(d^2)$. 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.