Improved Quantum Algorithms for Rényi 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ényi 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 $\tilde{\mathcal{O}}(n^{\max \{1/2,1-1/\alpha \}}/\epsilon )$ 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 $\tilde{\mathcal{O}}(n^{1/(2\alpha )}/{\epsilon }^{\max \{1,1/(2\alpha )\}})$, 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 (1/{\epsilon }^{\max \{1,1/(2\alpha )\}})$ for $0<\alpha <1$, which identifies the optimal precision dependence of our algorithm.

Improved Rényi entropy estimator for integer $\alpha$ to be added