# Quantum query complexity of entropy estimation

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Oct 2017.

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

- [Near-Optimal Quantum Algorithms for Multivariate Mean Estimation](https://mlsanity.com/paper/2111.09787/) (2021)
- [Quantum Sub-Gaussian Mean Estimator](https://mlsanity.com/paper/2108.12172/) (2021)
- [Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret](https://mlsanity.com/paper/2302.10796/) (2023)
- [Quantum Neural Estimation of Entropies](https://mlsanity.com/paper/2307.01171/) (2023)
- [Computationally Efficient Approximations for Matrix-based Renyi's Entropy](https://mlsanity.com/paper/2112.13720/) (2021)
- [F-Divergences and Cost Function Locality in Generative Modelling with Quantum Circuits](https://mlsanity.com/paper/2110.04253/) (2021)
- [Wavefunction Flows: Efficient Quantum Simulation of Continuous Flow Models](https://mlsanity.com/paper/2510.08462/) (2025)
- [Performance Guarantees for Quantum Neural Estimation of Entropies](https://mlsanity.com/paper/2511.19289/) (2025)
- [Information Geometry and Classical Cram'er-Rao Type Inequalities](https://mlsanity.com/paper/2104.01061/) (2021)
- [Information Geometry for the Working Information Theorist](https://mlsanity.com/paper/2310.03884/) (2023)
- [A Quantum/Classical Example Oracle Separation for Making Things Up](https://mlsanity.com/paper/2608.11648/) (2026)

## Abstract (arXiv)

Estimation of Shannon and R'enyi entropies of unknown discrete distributions is a fundamental problem in statistical property testing and an active research topic in both theoretical computer science and information theory. Tight bounds on the number of samples to estimate these entropies have been established in the classical setting, while little is known about their quantum counterparts. In this paper, we give the first quantum algorithms for estimating α-R'enyi entropies (Shannon entropy being 1-Renyi entropy). In particular, we demonstrate a quadratic quantum speedup for Shannon entropy estimation and a generic quantum speedup for α-R'enyi entropy estimation for all α≥ 0, including a tight bound for the collision-entropy (2-R'enyi entropy). We also provide quantum upper bounds for extreme cases such as the Hartley entropy (i.e., the logarithm of the support size of a distribution, corresponding to α=0) and the min-entropy case (i.e., α=+∞), as well as the Kullback-Leibler divergence between two distributions. Moreover, we complement our results with quantum lower bounds on α-R'enyi entropy estimation for all α≥ 0.