[QIP-Sem] QIP seminar, Fri 2/17, 10:00 AM, 2-132, Fernando Brandao

[Peter Shor]

MIT Quantum Information Processing seminar
Friday 2/17 at 10:00 AM in 2-132
-------------------------------------------------

Fernando Brandao ()

The Complexity of Quantum Entanglement

Abstract:

Quantum mechanics predicts the existence of correlations among two or more quantum systems that cannot be described merely by shared randomness. Such correlations, termed entanglement, have been analyzed from a foundation perspective since the beginning of quantum theory and, more recently, as a resource for quantum information-theoretic tasks.  A fundamental problem in entanglement theory is the following: given the description of a quantum system of two or more parties as a density matrix (a positive semidefinite matrix of unit trace), how can we decide if the state is entangled?  In this talk I will discuss the fastest known algorithm for solving this question, based on a natural Lasserre hierarchy relaxation of the problem introduced by Doherty, Parrilo, and Spedalieri in 2001, and show how it converges in quasi-polynomial time to the true solution. 

  The proof of correctness of the algorithm is based on a number of new tools in quantum information theory that may be of independent interest. These include a new bound on how much quantum correlations are non-shareable, a feature known as monogamy of entanglement, and an approach to the quantification of entanglement based on ideas of hypothesis testing. 

  I will also discuss applications of the techniques developed to quantum complexity theory and other (non-quantum) optimization problems, and give evidence that the algorithm presented might be optimal. No background on quantum information theory will be assumed.

-------------------------------------------------
http://qis.mit.edu
http://mailman.mit.edu/mailman/listinfo/qip-sem