Breaking the Quadratic Barrier for von Neumann Entropy Estimation

Abstract

We study the sample complexity of estimating the von Neumann entropy of an unknown $d$-dimensional quantum state. All previously known estimators require $\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\!\left(\frac{d^2 \log^2(\log(d)) \log(1/\varepsilon)}{\varepsilon^2 \log^2(d)} + \frac{\log^2(d/\varepsilon)}{\varepsilon^2}\right) \] samples. In particular, for constant $\epsilon$, the complexity is $O_{\epsilon }(d^2{\log }^2(\log (d))/{\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.

33 pages, 1 table, 1 algorithm