Yupan Liu

We investigate the computational hardness of estimating the quantum α-Rényi entropy SˆR_α(ρ) = ln Tr(ρˆα)/(1−α) and the quantum q-Tsallis entropy SˆT_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 (TsallisQEA_q) ask whether SˆR_α(ρ) or SˆT_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 Rank2TsallisQEA_q 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 LowRankTsallisQEA_q are BQP-complete, where both are restricted versions of RényiQEA_α and TsallisQEA_q with ρ of polynomial rank. - For all real order q>1, TsallisQEA_q is BQP-complete. Our hardness results stem from reductions based on new inequalities relating the α-Rényi or q-Tsallis binary entropies at different orders, where the reductions differ substantially from previous approaches, and the inequalities are also of independent interest.

The complexity class Quantum Statistical Zero-Knowledge (𝖰𝖲𝖹𝖪), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper bound 𝖰𝖨𝖯(𝟤)∩co-𝖰𝖨𝖯(𝟤), which was simplified following the inclusion 𝖰𝖨𝖯(𝟤)⊆𝖯𝖲𝖯𝖠𝖢𝖤 established in Jain, Upadhyay, and Watrous (FOCS 2009). Here, 𝖰𝖨𝖯(𝟤) denotes the class of promise problems that admit two-message quantum interactive proof systems in which the honest prover is typically computationally unbounded, and co-𝖰𝖨𝖯(𝟤) denotes the complement of 𝖰𝖨𝖯(𝟤). We slightly improve this upper bound to 𝖰𝖨𝖯(𝟤)∩co-𝖰𝖨𝖯(𝟤) with a quantum linear-space honest prover. A similar improvement also applies to the upper bound for the non-interactive variant 𝖭𝖨𝖰𝖲𝖹𝖪. Our main techniques are an algorithmic version of the Holevo-Helstrom measurement and the Uhlmann transform, both implementable in quantum linear space, implying polynomial-time complexity in the state dimension, using the recent space-efficient quantum singular value transformation of Le Gall, Liu, and Wang (CC, to appear).