Separable states, the unique games conjecture and monogamy of entanglement
Seminar Room 1, Newton Institute
AbstractCo-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 •http://arxiv.org/abs/1001.0017 - Testing product states, quantum Merlin-Arthur games and tensor optimisation •http://arxiv.org/abs/1205.4484 - Hypercontractivity, Sum-of-Squares Proofs, and their Applications •http://arxiv.org/abs/1210.6367 - Quantum de Finetti Theorems under Local Measurements with Applications
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.