Improved Quantum Algorithms for R\'enyi Entropies Estimation
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.