A Quantum Algorithm Framework for Discrete Probability Distributions With Applications to Rényi Entropy Estimation

Abstract

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 <inline-formula> <tex-math notation="LaTeX">$\sum _{i=1}^{n}\sqrt {p_{i}}|i \rangle $ </tex-math></inline-formula>, for <inline-formula> <tex-math notation="LaTeX">$\alpha >1$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$0 < \alpha < 1$ </tex-math></inline-formula>, our algorithm framework estimates <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>-Rényi entropy <inline-formula> <tex-math notation="LaTeX">$H_{\alpha }(p)$ </tex-math></inline-formula> to within additive error <inline-formula> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline-formula> with probability at least 2/3 using <inline-formula> <tex-math notation="LaTeX">$\widetilde {\mathcal {O}}\left({n^{1-\frac {1}{2\alpha }}/\epsilon + \sqrt {n}/\epsilon ^{1+\frac {1}{2\alpha }}}\right)$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$\widetilde {\mathcal {O}}\left({n^{\frac {1}{2\alpha }}/\epsilon ^{1+\frac {1}{2\alpha }}}\right)$ </tex-math></inline-formula> queries, respectively. This improves the best known dependence in <inline-formula> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline-formula> as well as the joint dependence between n and <inline-formula> <tex-math notation="LaTeX">$1/\epsilon $ </tex-math></inline-formula>. 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.