Quantum Query Complexity of Entropy Estimation
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
Estimation of Shannon and Rényi entropies of unknown discrete distributions is a fundamental problem in statistical property testing. In this paper, we give the first quantum algorithms for estimating <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>-Rényi entropies (Shannon entropy being 1-Rényi entropy). In particular, we demonstrate a quadratic quantum speedup for Shannon entropy estimation and a generic quantum speedup for <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>-Rényi entropy estimation for all <inline-formula> <tex-math notation="LaTeX">$\alpha \geq 0$ </tex-math></inline-formula> values, including tight bounds for the Shannon entropy, the Hartley entropy (<inline-formula> <tex-math notation="LaTeX">$\alpha =0$ </tex-math></inline-formula>), and the collision entropy (<inline-formula> <tex-math notation="LaTeX">$\alpha =2$ </tex-math></inline-formula>). We also provide quantum upper bounds for estimating min-entropy (<inline-formula> <tex-math notation="LaTeX">$\alpha =+\infty $ </tex-math></inline-formula>) as well as the Kullback–Leibler divergence. We complement our results with quantum lower bounds on <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>-Rényi entropy estimation for all <inline-formula> <tex-math notation="LaTeX">$\alpha \geq 0$ </tex-math></inline-formula> values. Our approach is inspired by the pioneering work of Bravyi, Harrow, and Hassidim (BHH); however, with many new technical ingredients: 1) we improve the error dependence of the BHH framework by a fine-tuned error analysis together with Montanaro’s approach to estimating the expected output of quantum subroutines for <inline-formula> <tex-math notation="LaTeX">$\alpha =0,1$ </tex-math></inline-formula>; 2) we develop a procedure, similar to cooling schedules in simulated annealing, for general <inline-formula> <tex-math notation="LaTeX">$\alpha \geq 0$ </tex-math></inline-formula>, and 3) in the cases of integer <inline-formula> <tex-math notation="LaTeX">$\alpha \geq 2$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$\alpha =+\infty $ </tex-math></inline-formula>, we reduce the entropy estimation problem to the <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>-distinctness and <inline-formula> <tex-math notation="LaTeX">$\lceil \log n\rceil $ </tex-math></inline-formula>-distinctness problems, respectively.