Abstract
As often emerges in various basic quantum properties such as R\'enyi and Tsallis entropies, the trace of quantum state powers tr(ρ^q) has attracted a lot of attention. The recent work of Liu and Wang (SODA 2025) showed that, even for (possibly) non-integer q>1, tr(ρ^q) can be estimated to within additive error ε using a dimension-independent (and also rank-independent) sample complexity of O(1/ε^3+2/q-1), together with a lower bound of Ω(1/ε). In addition, combining this result with subsequent work of Liu (STACS 2026) shows that the corresponding promise problem is BQP-complete. In this paper, we significantly improve and extend the sample complexity bounds for this problem. Furthermore, we show that for 0<q<1, the problem does not admit an efficient estimator unless BQP= NIQSZK, which is considered highly unlikely. In particular, we have the following results. - For q>2, we settle the sample complexity with matching upper and lower bounds Θ(1/ε²). - For 1<q<2, we obtain an upper bound of O(1/ε^2/q-1), with a lower bound of Ω(1/ε^max{1/q-1,2}) for dimension-independent (in fact, rank-independent) estimators. - For 0<q<1, we obtain an upper bound of O((d/ε)^2/q), with a lower bound of Ω((d/ε)^1/q) for d-dimensional states (in fact, both bounds can be naturally refined to depend on the rank rather than the dimension). Accordingly, the corresponding promise problem is NIQSZK-hard, which is in sharp contrast to the case of q>1. Technically, our upper bounds are obtained by (non-plug-in) quantum estimators based on weak Schur sampling, in sharp contrast to the prior approach based on quantum singular value transformation and samplizer.