Quantum query complexity of entropy estimation

Опубликовано 2 мая 2017, 23:06

Estimation of Shannon and Renyi entropies of unknown discrete distributions is a fundamental problem in classical statistical property testing that has been intensively studied by the communities of both theoretical computer science and information theory. Tight bounds of the number of samples to estimate these entropies have been established in the classical setting, while little is known if one introduces quantum computation into the picture. In this paper, we systematically study the potential quantum speed-up in estimating alpha-Renyi entropies for general alpha (Shannon entropy is 1-Renyi entropy).

In particular, we demonstrate a quadratic quantum speed-up for Shannon entropy estimation and also a generic quantum speed-up for alpha-Renyi entropy estimation when 1/2=2. Our result for 1/2=2 is achieved by building a connection between the entropy estimation problem and the k-distinctness problem and then by utilizing the state-of-the-art quantum algorithm for k-distinctness by Belovs.

Finally, we complement our quantum upper bounds with quantum lower bounds of alpha-Renyi entropy estimation for all alpha greater than 0.

Joint work with Tongyang Li.

See more on this video at microsoft.com/en-us/research/v...