Quantum Query Complexity of Entropy Estimation

DOI10.1109/TIT.2018.2883306zbMATH Open1427.68089arXiv1710.06025OpenAlexW2766006549WikidataQ128875611 ScholiaQ128875611MaRDI QIDQ5223977FDOQ5223977

Authors: Tongyang Li, Xiaodi Wu 

Publication date: 19 July 2019

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: 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 $alpha$-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 $alpha$-R'enyi entropy estimation for all $alphageq0$, 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 $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'enyi entropy estimation for all $alphageq0$.

Full work available at URL: https://arxiv.org/abs/1710.06025

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Quantum algorithms and complexity in the theory of computing (68Q12)

Cited In (4)

• Estimation of average differential entropy for a stationary ergodic space-time random field on a bounded area
• Entropy lower bounds for quantum decision tree complexity
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• Quantum Algorithms for Classical Probability Distributions

This page was built for publication: Quantum Query Complexity of Entropy Estimation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5223977)