Breaking the Multiplicative Overhead in Quantum Entropy Estimation

Abstract

The von Neumann, Tsallis, and Rényi 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 $\epsilon$, rank upper bound $R$, and fixed order $\alpha$. Tsallis entropy estimation has near-optimal rank-independent query complexity $\tilde{O}({\epsilon }^{-1/(\alpha -1)})$ for $1<\alpha <2$, when the allowed dimension and rank accommodate the lower-bound instances, and $\tilde{O}(1/\epsilon )$ for $\alpha \ge 2$, where $\tilde{O}$ suppresses logarithmic factors. The first saves a factor $1/\epsilon$; the second extends known integer-order scaling to noninteger orders. We also improve the von Neumann entropy bound from $\tilde{O}(R/{\epsilon }^2)$ to $\tilde{O}(R/\epsilon )$ and obtain $\tilde{O}(R/\epsilon )$ for noninteger Rényi orders $1<\alpha <3$, 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 $\tilde{O}(R/\epsilon )$ 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.

arXiv commentMain text: 28 pages, 2 figures, 5 tables; appendices: 38 pages, 1 table. Total: 66 pages, 2 figures, 6 tables