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

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\le \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 $\tilde{O}\left(\frac{n^{\frac{1}{2}+\frac{1}{2q}}}{{\epsilon }^{\frac{1}{2q}}}+\frac{n^{1-q}}{\epsilon }\right)$, which improves the result given by Chen et al. (ICALP 2026) when $\varepsilon=O\rbra{n^{1-2q}}$.