Quantum Query Complexity of Entropy Estimation

DOI10.1109/TIT.2018.2883306MaRDI QIDQ5223977zbMATH OpenOpenAlexWikidataFDO

Authors Tongyang Li, Xiaodi Wu

Publication date 19 July 2019

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

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)

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$.

Cited in

(4)

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

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)