Classical and quantum query complexity of entropy estimation
Given an unknown discrete distribution, classical algorithms for estimating its Shannon and Renyi entropies have been intensively developed and tight bounds of queries to the distribution have been established. However, the quantum query complexity of entropy estimation is still open in general. We give quantum algorithms that give quadratic speed-up for Shannon entropy estimation compared to its classical lower bound and also speed-up for \alpha-Renyi entropy estimation when 1/2<\alpha<2.