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 ${\mathrm{H}}_q^{\mathrm{T}\mathrm{s}\mathrm{a}}(P)=\frac{{\sum }_{i=1}^n{p}_i^q-1}{1-q}$ when $0<q<1$, given purified quantum query access to a distribution $P$ on $[n]$. When $0<q\le \frac{1}{2}$, we provide a quantum algorithm with query complexity $\tilde{O}\text{rbra}{\left(\frac{n}{\epsilon }\right)}^{\frac{1}{2q}}$, which is optimal up to polylogarithmic factors. When $\frac{1}{2}<q<1$, we introduce a two-stage simultaneous probability estimation procedure, yielding a quantum algorithm with query complexity $\tilde{O}(\frac{n^{\frac{1}{2}+\frac{1}{2q}}}{{\epsilon }^{\frac{1}{2q}}}+\frac{n^{1-q}}{\epsilon })$, which improves the result given by Chen et al. (ICALP 2026) when $\epsilon =O\text{rbra}{n}^{1-2q}$.