Improved Quantum Algorithms for R\'enyi Entropies Estimation
En palabras de los autores
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.
Apareció: jueves, 15 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: Improved R\'enyi entropy estimator for integer $\alpha$ to be added