Improved Quantum Algorithms for R'enyi Entropies Estimation

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ényi entropy H α(p) for any distribution p = (p i) i=1 n given its purified quantum query-access. For non-integer α> 1, our algorithm estimates H α(p) to within additive error ε using only (n 1/2,1-1/α/ε) queries, which improves the best known upper bound for dependence on both n and 1/ε. For 0<α<1, our algorithm has query complexity (n 1/(2α)/ε 1,1/(2α)), which improves the dependence on 1/ε 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 Ω (1/ε 1,1/(2α)) for 0<α<1, which identifies the optimal precision dependence of our algorithm.