We investigate the computational complexity of estimating the trace of quantum state powers $\text{tr}(\rho^q)$ for an $n$-qubit mixed quantum state $\rho$, given its state-preparation circuit of size $\text{poly}(n)$. This quantity is closely related to and often interchangeable with the Tsallis entropy $\text{S}_q(\rho) = \frac{1-\text{tr}(\rho^q)}{q-1}$, where $q = 1$ corresponds to the von Neumann entropy. For any non-integer $q \geq 1 + \Omega(1)$, we provide a quantum estimator for $\text{S}_q(\rho)$ with time complexity $\text{poly}(n)$, exponentially improving the prior best results of $\exp(n)$ due to Acharya, Issa, Shende, and Wagner (ISIT 2019), Wang, Guan, Liu, Zhang, and Ying (TIT 2024), and Wang, Zhang, and Li (TIT 2024), and Wang and Zhang (ESA 2024). Our speedup is achieved by introducing efficiently computable uniform approximations of positive power functions into quantum singular value transformation.

Our quantum algorithm reveals a sharp phase transition between the case of $q=1$ and constant $q>1$ in the computational complexity of the Quantum $q$-Tsallis Entropy Difference Problem (TsallisQED$_q$), particularly deciding whether the difference $\text{S}_q(\rho_0) - \text{S}_q(\rho_1)$ is at least $0.001$ or at most $-0.001$:

- For any $1+\Omega(1) \leq q \leq 2$, TsallisQED$_q$ is BQP-complete, which implies that Purity Estimation is also BQP-complete.

- For any $1 \leq q \leq 1 + \frac{1}{n-1}$, TsallisQED$_q$ is QSZK-hard, leading to hardness of approximating von Neumann entropy because $\text{S}_q(\rho) \leq \text{S}(\rho)$ unless $\text{BQP} = \text{QSZK}$.

The hardness results are derived from reductions based on new inequalities for the quantum $q$-Jensen-(Shannon-)Tsallis divergence with $1\leq q \leq 2$, which are of independent interest.