Computational Hardness of Estimating Quantum Entropies via Binary Entropy Bounds

We investigate the computational hardness of estimating the quantum α-Rényi entropy S^𝚁_α (ρ) = (ln Tr (ρ^α) ) / (1-α) and the quantum q-Tsallis entropy S^𝚃q (ρ) = (1-Tr (ρq) ) / (q-1), both converging to the von Neumann entropy as the order approaches 1. The promise problems Quantum α-Rényi Entropy Approximation (RényiQEA_α) and Quantum q-Tsallis Entropy Approximation (TsallisQEAq) ask whether S^𝚁_α (ρ) or S^𝚃q (ρ), respectively, is at least τY or at most τN, where τY - τ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ényiQEA_α and Rank2TsallisQEAq are 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 order α > 0 and 0 1, TsallisQEAq is BQP-complete. Our hardness results stem from reductions based on new inequalities relating the α-Ré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.