Spring 2014

Monogamy of Non-signaling Correlations

Thursday, February 27th, 2014 10:00 am10:45 am

Add to Calendar

Monogamy relations and de Finetti theorems have broad application, including to quantum key distribution, Hamiltonian complexity, analyzing non-local games and even classical optimization algorithms. One limitation of most work in this space is that the number of systems needs to grow like a power of the dimension of each system. Brandao, Christandl and Yard achieved a major breakthrough by making use of information theory to reduce the number of systems needed to scale only like the logarithm of the local dimension. I will describe a further improvement of their theorem which has a simpler proof and generalizes to multipartite states and non-signaling distributions. Next I'll describe several applications to non-local games, quantum complexity theory, and other topics. Finally, I'll explain how conjectured improvements of these results could resolve several major open problems in classical and quantum complexity theory.