Trace Estimation of Quantum State Powers: Sample Complexity and Computational Hardness

As often emerges in various basic quantum properties such as Rényi and Tsallis entropies, the trace of quantum state powers $\text{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$, $\text{tr}(ρ^q)$ can be estimated to within additive error $ε$ using a dimension-independent (and also rank-independent) sample complexity of $\widetilde O(1/ε^{3+\frac2{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 ${\sf 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 ${\sf BQP}={\sf 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 $\widetildeΘ(1/ε^2)$. - For $1<q<2$, we obtain an upper bound of $\widetilde O(1/ε^{\frac2{q-1}})$, with a lower bound of $Ω(1/ε^{\max\{\frac1{q-1},2\}})$ for dimension-independent (in fact, rank-independent) estimators. - For $0<q<1$, we obtain an upper bound of $O((d/ε)^{\frac2{q}})$, with a lower bound of $Ω((d/ε)^{\frac1{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 ${\sf 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.