Quantum query complexity of entropy estimation

Abstract

Estimation of Shannon and Rényi 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 $\alpha$-Rényi 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 $\alpha$-Rényi entropy estimation for all $\alpha \ge 0$, including a tight bound for the collision-entropy (2-Rényi 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 $\alpha =0$) and the min-entropy case (i.e., $\alpha =+\infty$), as well as the Kullback-Leibler divergence between two distributions. Moreover, we complement our results with quantum lower bounds on $\alpha$-Rényi entropy estimation for all $\alpha \ge 0$.

43 pages, 1 figure

References in corpus (10)

• Auto-Encoding Variational Bayes
• Direct Measurement of Auger Electrons Emitted from a Semiconductor Light-Emitting Diode under Electrical Injection: Identification of the Dominant Mechanism for Efficiency Droop
• Unraveling the "Green Gap" problem: The role of random alloy fluctuations in InGaN/GaN light emitting diodes
• Quantum speedup of Monte Carlo methods
• Negative weights make adversaries stronger
• A Survey of Quantum Property Testing
• Quantum algorithms for testing properties of distributions
• Chebyshev polynomials, moment matching, and optimal estimation of the unseen
• Minimax Rate-Optimal Estimation of Divergences between Discrete Distributions
• Estimation of KL Divergence: Optimal Minimax Rate

Cited by in corpus (1)

• Entanglement theory with limited computational resources