John Wright: Quantum Spectrum Testing

Thursday, November 13, 2014 - 2:00pm to 3:00pm

Location:

32-G575

Speaker:

John Wright

Biography:

CMU

Seminar group:

Algorithms and Complexity Seminar

In recent years, the area of property testing of probability distributions has produced a wide variety of interesting results. Here one is given sample access to an unknown distribution and asked whether it satisfies some property, e.g. is it the uniform distribution, does it have small entropy, and so forth. In this work, we study the natural quantum analogue of this problem, in which one is given many copies of an unknown mixed state (the quantum version of a probability distribution) and asked whether it satisfies a given property. We focus on properties which depend only on the mixed state's spectrum (hence the name Quantum Spectrum Testing).

Our paper gives several optimal algorithms for testing specific properties of mixed states, e.g. the property of being the maximally mixed state. This can be viewed as the quantum analogue of a result of Paninski. In addition, we show a nearly-tight lower bound for the well-known "empirical Young diagram algorithm" which learns an unknown mixed state's spectrum.

Our main tool is Schur-Weyl duality, which leads us to studying a particular algorithm called weak Schur sampling. This algorithm is based on the representation theory of the symmetric group, and to analyze it we use various tools in this area, including Kerov's algebra of observables and a limiting theorem of Biane.

No background in quantum computing or representation theory is assumed.

This is joint work with Ryan O'Donnell.