We investigate the computational hardness of estimating the quantum $\alpha$-R\'enyi entropy ${ \rm S}^{ \tt R}_{ \alpha}(\rho) = \frac{ \ln { \rm Tr}(\rho^\alpha)}{ 1-\alpha}$ and the quantum $q$-Tsallis entropy ${ \rm S}^{ \tt T}_q(\rho) = \frac{ 1-{ \rm Tr}(\rho^q)}{ q-1}$, both converging to the von Neumann entropy as the order approaches $1$. The promise problems Quantum $\alpha$-R\'enyi Entropy Approximation (R\'enyiQEA$_\alpha$) and Quantum $q$-Tsallis Entropy Approximation (TsallisQEA$_q$) ask whether $ { \rm S}^ { \tt R}_{ \alpha}(\rho)$ or ${ \rm S}^{ \tt T}_q(\rho)$, respectively, is at least $\tau_{ \tt Y}$ or at most $\tau_{ \tt N}$, where $\tau_{ \tt Y} - \tau_{ \tt N}$ is typically a positive constant. Previous hardness results cover only the von Neumann entropy (order $1$) and some cases of the quantum $q$-Tsallis entropy, while existing approaches do not readily extend to other orders. We establish that for all positive real orders, the rank-$2$ variants Rank2R\'enyiQEA$_\alpha$ and Rank2TsallisQEA$_q$ are ${ \sf BQP}$-hard. Combined with prior (rank-dependent) quantum query algorithms in Wang, Guan, Liu, Zhang, and Ying (TIT 2024), Wang, Zhang, and Li (TIT 2024), and Liu and Wang (SODA 2025), our results imply: - For all real orders $\alpha > 0$ and $0 < q \leq 1$, LowRankR\'enyiQEA$_\alpha$ and LowRankTsallisQEA$_q$ are ${ \sf BQP}$-complete, where both are restricted versions of R\'enyiQEA$_\alpha$ and TsallisQEA$_q$ with $\rho$ of polynomial rank. - For all real order $q>1$, TsallisQEA$_q$ is ${ \sf BQP}$-complete. Our hardness results stem from reductions based on new inequalities relating the $\alpha$-R\'{ e}nyi or $q$-Tsallis binary entropies of different orders, where the reductions differ substantially from previous approaches, and the inequalities are also of independent interest.
Categories: quant-ph cs.CC cs.IT math.IT