Quantum Multi-Level Estimation of Functionals of Discrete Distributions

Abstract

We propose a quantum multi-level estimation framework for a functional ${\sum }_{i=1}^{n}f(p_i)$ of a discrete distribution $(p_i{)}_{i=1}^n$. We partition the values $p_i$ into logarithmically many intervals whose length decays exponentially. For each interval, we perform non-destructive singular value discrimination to isolate the relevant $p_i$, enabling adaptive estimation of the partial sum over this interval. Unlike previous variable-time approaches, our method avoids high control overhead and requires only constant extra ancilla qubits. As an application, we present efficient quantum estimators for the $q$-Tsallis entropy of discrete distributions. Specifically: (i) For $q>1$, we obtain a near-optimal quantum algorithm with query complexity $\tilde{\hat{I}}˜(1/{\epsilon }^{\max \{1/(2(q-1)),1\}})$, improving the prior best $O(1/{\epsilon }^{1+1/(q-1)})$ due to Liu and Wang (SODA 2025; IEEE Trans. Inf. Theory 2026). (ii) For $0<q<1$, we obtain a quantum algorithm with query complexity $\tilde{O}(n^{1/q-1/2}/{\epsilon }^{1/q})$, exhibiting a quantum speedup over the near-optimal classical estimators due to Jiao, Venkat, Han, and Weissman (IEEE Trans. Inf. Theory 2017). Our results achieve, to our knowledge, the first near-optimal quantum estimators for parameterized $q$-entropy for non-integer $q$.

32 pages