Computational Hardness of Estimating Quantum Entropies via Binary Entropy Bounds

We investigate the computational hardness of estimating the quantum c-Rényi entropy SαR(ρ) (Equation Present) and the quantum q-Tsallis entropy SqT(ρ) (Equation Present), 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 SRα(ρ) or STq(ρ), 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 < q ≤ 1, LowRankRényiQEAα and LowRankTsallisQEAq are BQP-complete, where both are restricted versions of RényiQEAα and TsallisQEAq with ρ of polynomial rank. For all real order q > 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.