Computational hardness of estimating quantum entropies via binary entropy bounds

Yupan Liu (Jan 08 2026).

Abstract: We investigate the computational hardness of estimating the quantum $\alpha$-Rényi 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ényi Entropy Approximation (RényiQEA$_\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ényiQEA$_\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ényiQEA$_\alpha$ and LowRankTsallisQEA$_q$ are ${\sf BQP}$-complete, where both are restricted versions of RényiQEA$_\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é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.

Arxiv: https://arxiv.org/abs/2601.03734