We investigate the computational complexity of estimating the trace of quantum state powers tr(ρq) for an n qubit mixed quantum state ρ, given its state-preparation circuit of size poly (n). This quantity is closely related to and often interchangeable with the Tsallis entropy Sq(ρ) = 1 - tr(ρq)/q - 1, where q = 1 corresponds to the von Neumann entropy. For any non-integer q≥ 1 + Ω(1), we provide a quantum estimator for Sq(ρ) with time complexity 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)| Wang, Zhang, and Li (TIT 2024), and Wang and Zhang (TIT 2025). 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 Sq(ρ0)-Sq (ρ1) is at least 0.001 or at most -0.001: • For any 1 + Ω (1) ≤ q ≤ 2, TsallisQED q is BQP-complete, which implies that Purity Estimation is also BQP-complete. • For any 1≤q≤1+1/n - 1, TsallisQED q is QSZK-hard, leading to hardness of approximating the von Neumann entropy because Sq(ρ) ≤ S (ρ), as long as BQPQSZK. The hardness results are derived from reductions based on new inequalities for the quantum q-Jensen-(Shannon-)Tsallis divergence with 1 ≤ q ≤ 2, which are of independent interest.