Communication, Control and Signal Processing Seminar

Quantum query complexity of entropy estimation

Xiaodi Wu
Assistant Professor
Department of Computer Science
University of Maryland

Abstract
Estimation of Shannon and R{'e}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 of 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 talk, I will show quantum algorithms for estimating $\alpha$-R{'e}nyi entropies (Shannon entropy being 1-Renyi entropy). In particular, I will demonstrate a quadratic quantum speedup for Shannon entropy estimation and a generic quantum speedup for $\alpha$-R{'e}nyi entropy estimation for all $\alpha$>0, including a tight bound for the collision-entropy (2-R{'e}nyi entropy) and also an analysis for the min-entropy case (i.e., $\alpha$ = +infinity). This talk is based on joint work with Tongyang Li.