Tutte Colloquium - Debbie Leung

Title: Incompressibility of classical distributions

Abstract:

We prove a general, robust, single-letter lower bound on the achievable rate for ensembles of classical states, which holds even when Alice and Bob share free entanglement and allow a constant local error.  We apply the bound to a specific ensemble of only two states and prove an arbitrarily large separation between the best achievable rate and the Holevo information. Since the states are classical, the observed incompressibility is not fundamentally quantum mechanical, and can be quantified in terms of limitations to clone a specimen from the ensemble or to distinguish the two classical states. 

Joint work with Anurag Anshu and Dave Touchette.