Quantum Tsallis Entropy Estimation: Near-Optimal Bounds and High-Precision Improvements

Estimating statistical properties of probability distributions is a fundamental problem in statistics and theoretical computer science. We develop quantum algorithms for estimating the q-Tsallis entropy H q Tsa(P) = sum i=1 n p i q-1 over 1-q when 0<q<1, given purified quantum query access to a distribution P on [n]. When 0<q at most 1 over 2, we provide a quantum algorithm with query complexity, which is optimal up to polylogarithmic factors. When 1 over 2<q<1, we introduce a two-stage simultaneous probability estimation procedure, yielding a quantum algorithm with query complexity (n 12+ 1 over 2q over epsilon 1 over 2q+ n 1-q over epsilon), which improves the result given by Chen et al. (ICALP 2026) when epsilon=O.