Quantum Tsallis Entropy Estimation: Near-Optimal Bounds and High-Precision Improvements
In the authors' words
Estimating statistical properties of probability distributions is a fundamental problem in statistics and theoretical computer science. We develop quantum algorithms for estimating the -Tsallis entropy when , given purified quantum query access to a distribution on . When , we provide a quantum algorithm with query complexity , which is optimal up to polylogarithmic factors. When , we introduce a two-stage simultaneous probability estimation procedure, yielding a quantum algorithm with query complexity , which improves the result given by Chen et al. (ICALP 2026) when .
Main resultLimitation the authors admit
Appeared: Monday, October 19. arXiv. Preprint, not yet peer-reviewed.