Breaking the Multiplicative Overhead in Quantum Entropy Estimation
In the authors' words
The von Neumann, Tsallis, and R\'enyi entropies are fundamental measures of quantum information. A common estimation strategy multiplies the worst-case costs of spectral transformation and statistical readout, leaving gaps to query lower bounds. We reduce this overhead with multi-level algorithms that use local normalization and precision allocation, while variable-time estimation accounts for the probability of reaching expensive spectral tests. With controlled purified access and its inverse, we obtain bounds for additive error , rank upper bound , and fixed order . Tsallis entropy estimation has near-optimal rank-independent query complexity for , when the allowed dimension and rank accommodate the lower-bound instances, and for , where suppresses logarithmic factors. The first saves a factor ; the second extends known integer-order scaling to noninteger orders. We also improve the von Neumann entropy bound from to and obtain for noninteger R\'enyi orders , with further bounds at other orders. Our functional-estimation theorem replaces the global product by a sum of local costs weighted by function magnitudes and spectral masses. We further estimate fixed logarithmic moments and entropy variance using queries, providing efficient access to fluctuation parameters that enter finite-blocklength quantum compression and pure-state entanglement conversion. More broadly, our framework extends beyond entropy to a broad class of density-matrix functionals, offering a systematic approach toward optimal query complexity in quantum spectral estimation.
Appeared: Thursday, October 1. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: Main text: 28 pages, 2 figures, 5 tables; appendices: 38 pages, 1 table. Total: 66 pages, 2 figures, 6 tables