The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

MQI

Seminar

Separable states, the unique games conjecture and monogamy of entanglement

Harrow, A (Massachusetts Institute of Technology)
Monday 02 September 2013, 15:30-16:30

Seminar Room 1, Newton Institute

Abstract

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 •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

Presentation

[pptx]

Video

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.

Back to top ∧