A Quantum Algorithm Framework for Discrete Probability Distributions With Applications to Rényi 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ényi entropies as specific examples. In particular, given a quantum oracle that prepares an n -dimensional quantum state Σ n i=1 √ pi | i ⟩, for α > 1 and 0 < α < 1, our algorithm framework estimates α-Rényi entropy H α ( p ) to within additive error ϵ with probability at least 2/3 using Õ( n 1-1/2α /ϵ + √ n /ϵ 1+ 1/2α ) and Õ( n 1/2α /ϵ 1+ 1/2α ) 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.