## Quantum Institute Seminar: Fernando Brandao

- Date: 07/20/2011

University of Calgary

Is it entangled? A quasi-polynomial time algorithm for the quantum separability problem.

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)