Quantum Institute Seminar: Fernando Brandao

Quantum mechanics predicts the existence of correlations between two quantum systems which cannot be described merely by shared randomness. Such correlations, termed entanglement, have been analysed from a fundamental perspective since the beginning of quantum theory and, more recently, as a resource for quantum information-theoretic tasks, such as quantum key distribution and teleportation. A fundamental problem in entanglement theory is the following: given the description of a quantum system of two parties as a density matrix, how can we decide if the state is entangled or separable? In this talk I will discuss the fastest known algorithm for solving this problem. The algorithm works by considering a sequence of SDP (semidefinite programming) relaxations to the problem, which are shown to converge quickly to the true solution. Finally I will discuss a few other applications of the techniques developed to quantum information theory and quantum complexity theory. The talk is based on joint work with Matthias Christandl and Jon Yard (STOC 2011 and Commun. Math. Phys. '11)