log in  |  register  |  feedback?  |  help  |  web accessibility
Communication, Control and Signal Processing Seminar: Xiaodi Wu, "Quantum query complexity of entropy estimation"
Xiaodi Wu - Assistant Professor, Department of Computer Science
Thursday, November 7, 2019, 5:00-6:30 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)

Communication, Control and Signal Processing Seminar

Quantum query complexity of entropy estimation

Xiaodi Wu
Assistant Professor
Department of Computer Science
University of Maryland

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.


This talk is organized by Rebecca Copeland