Tutte Colloquium - Ashwin Nayak

Friday, February 5, 2016 3:30 pm - 3:30 pm EST (GMT -05:00)

Title: Sampling quantum states

Speaker: Ashwin Nayak
Affiliation: University of Waterloo
Room: MC 5501

Abstract: A classic result in information theory, the source coding theorem, shows how we may compress a sample from a random variable X, into essentially H(X) bits on average,  without any loss. (Here H(X) denotes the Shannon entropy of X.) We revisit the analogous problem in quantum communication, in the presence of shared entanglement. No characterization of the communication needed for lossless compression is known in this scenario. We study a natural protocol for such compression, quantum rejection sampling, and give bounds on its complexity. Event hough we do not have a precise characterization of the complexity, we show how it may be used to derive some consequences of lossless compression.

Joint work with Ala Shayeghi.