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

arXiv: https://arxiv.org/abs/2212.01571 · HTML: https://mlsanity.com/paper/2212.01571/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Dec 2022.

## Built on by (most cited first, 2 of 2)

- [Performance Guarantees for Quantum Neural Estimation of Entropies](https://mlsanity.com/paper/2511.19289/) (2025)
- [Entropy Estimation in Multi-Qutrit Systems via Variational and Classical Neural Networks](https://mlsanity.com/paper/2606.20504/) (2026)

## Abstract (arXiv)

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.