Breaking the Quadratic Barrier for von Neumann Entropy Estimation
2026-08-11 • Information Theory
Information Theory
AI summaryⓘ
The authors study how many samples are needed to estimate the von Neumann entropy, a measure of uncertainty for quantum states, in a system with dimension d. Previously, all known methods required at least about d squared samples, but the authors develop a new method that uses fewer samples than that, especially as d grows large. Their approach combines new mathematical tools, like a special inequality and improved estimators for different parts of the quantum state's spectrum. This results in better efficiency for estimating entropy with less data.
von Neumann entropyquantum statesample complexityestimatoreigenvaluesbias correctionpinching inequalitydirect-sum decompositionpolynomial estimatoradditive error
Authors
Minbo Gao, Qisheng Wang
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^2)$ samples, and plug-in estimators are known to face a quadratic barrier. We give the first subquadratic-sample estimator: for additive error $\varepsilon$, 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 $\varepsilon$, the complexity is $O_\varepsilon(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.