pipette
ESEspañol

Improved Quantum Algorithms for R\'enyi Entropies Estimation

Zongxing Xiong, Chengshen Gao, Lvzhou Li

Preprint

In the authors' words

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 for any distribution given its purified quantum query-access. For non-integer , our algorithm estimates to within additive error using only queries, which improves the best known upper bound for dependence on both and . For , our algorithm has query complexity , which improves the dependence on of the current best upper bound without incresing its 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 for , which identifies the optimal precision dependence of our algorithm.

Main resultThe abstract does not state a limitation.

Appeared: Thursday, October 15. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: Improved R\'enyi entropy estimator for integer $\alpha$ to be added