Quantum Institute Seminar: Fernando Brandao

  • Date: 07/20/2011
Fernando Brandao

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)