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

arXiv:2610.22983v1 Announce Type: new Abstract: 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{Tsa}}(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\leq \frac{1}{2}$, we provide a quantum algorithm with query complexity $\widetilde{O}\rbra{\left(\frac{n}{\varepsilon}\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 $\widetilde{O}\left(\frac{n^{\frac12+\frac{1}{2q}}}{\varepsilon^{\frac{1}{2q}}}+\frac{n^{1-q}}{\varepsilon}\right)$, which improves the result given by Chen et al. (ICALP 2026) when $\varepsilon=O\rbra{n^{1-2q}}$.