A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to R'enyi Entropy Estimation

Estimating statistical properties is fundamental in statistics and computer science. In this paper, we propose a unified quantum algorithm framework for estimating properties of discrete probability distributions, with estimating R'enyi entropies as specific examples. In particular, given a quantum oracle that prepares an n-dimensional quantum state sumi=1n√pi|irangle, for α>1 and 0<α<1, our algorithm framework estimates α-R'enyi entropy Hα(p) to within additive error ε with probability at least 2/3 using widetildeO(n^1-frac12α/ε + √n/ε^1+frac12α) and widetildeO(n^frac12α/ε^1+frac12α) queries, respectively. This improves the best known dependence in ε as well as the joint dependence between n and 1/ε. Technically, our quantum algorithms combine quantum singular value transformation, quantum annealing, and variable-time amplitude estimation. We believe that our algorithm framework is of general interest and has wide applications.