Skip to content
Preprint

Improved Quantum Algorithms for R\'enyi Entropies Estimation

Oct 2026 · 0 citations · 29 references
Physics

Abstract

Entropy estimation of discrete probability distributions is a fundamental problem in statistical inference and quantum property estimation. In this paper, we study the problem of estimating R\'enyi entropy $H_\alpha(\mathbf{p})$ for any distribution $\mathbf{p} = (p_i)_{i=1}^n$ given its purified quantum query-access. For non-integer $\alpha>1$, our algorithm estimates $H_\alpha(\mathbf{p})$ to within additive error $\epsilon$ using only $\widetilde{\mathcal{O}}\big(n^{\max\{1/2,1-1/\alpha\}}/\epsilon\big)$ queries, which improves the best known upper bound for dependence on both $n$ and $1/\epsilon$. For $0<\alpha<1$, our algorithm has query complexity $\widetilde{\mathcal{O}}\big(n^{1/(2\alpha)}/\epsilon^{\max\{1,1/(2\alpha)\}}\big)$, which improves the dependence on $1/\epsilon$ of the current best upper bound without incresing its $n$ dependence. Our approach adapts the multi-level estimation framework to relative approximation of the power sums and leverage binary search to remove the requirement of prior knowledge of them. We also strengthen the precision-dependent lower bound to $\Omega\big(1/\epsilon^{\max\{1,1/(2\alpha)\}}\big)$ for $0<\alpha<1$, which identifies the optimal precision dependence of our algorithm.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.