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é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 $\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.

arXiv:2610.19936 [quant-ph]

(or arXiv:2610.19936v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2610.19936 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.