Calendar

An experiment produces an unknown mixed state, and you would like to learn some property of this state.  How do you do this?  The standard approach is to rerun the experiment multiple times and perform some measurement on the copies produced.  The goal is then to learn or test the property using the smallest number of copies possible.  In some cases, such as performing tomography on rank one pure states, researchers have designed algorithms which are optimal in their copy complexity.  However, for many basic properties, including things as basic as estimating a mixed state's spectrum, this remains an open problem.

In this talk, we consider learning and testing properties which depend only on the mixed state's spectrum.  Natural problems in this space include learning its spectrum, estimating its von Neumann entropy, or testing whether it is low rank.  Our results include (i) a new upper bound for learning a mixed state's spectrum and (ii) an optimal algorithm for testing whether a mixed state is equal to the maximally mixed state.  We use techniques from the asymptotic theory of the symmetric group; in particular, we rely on Kerov's algebra of observables to help us study the moments of random Young diagrams.

Joint work with Ryan O'Donnell.