skip to content

Separable states, the unique games conjecture and monogamy of entanglement

Presented by: 
A Harrow Massachusetts Institute of Technology
Monday 2nd September 2013 - 15:30 to 16:30
INI Seminar Room 1
Co-authors: Boaz Barak (MSR), Fernando Brandao (UCL), Jon Kelner (MIT), Ashley Montanaro (Bristol), David Steurer (Cornell), Yuan Zhou (CMU)

The quantum separability problem---determining when a density matrix is entangled or when it is separable---is an old problem in quantum information theory. Although solving this problem to accuracy inverse-polynomial in dimension is NP-hard, only loose bounds are known on the complexity of the constant-error case. In this talk, I will describe some surprising connections between the quantum separability problem and a major open problem in classical computer science known as the unique games conjecture. Remarkably, even the proposed solutions to both problems turn out to be essentially the same, so that bounds on the monogamy of entanglement (aka de Finetti theorems) can be used to analyze the performance of classical algorithms. I will also describe conjectured monogamy bounds that are an alternate route to resolving the unique games conjecture.

Based on 1001.0017, 1205.4484 and 1210.6367.

Related Links • - Testing product states, quantum Merlin-Arthur games and tensor optimisation • - Hypercontractivity, Sum-of-Squares Proofs, and their Applications • - Quantum de Finetti Theorems under Local Measurements with Applications

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons