The Complexity of Quantum Entanglement


April 10, 2014


Fernando Brandao


University College London


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 show that one can use the Lasserre hierarchy of semidefinite programs to solve the above in quasi-polynomial time, giving the fastest known algorithm for it.

The proof of convergence is based on ideas of quantum information theory and gives a new way of understanding the Lasserre hierarchy in general. In particular I’ll also discuss applications of the framework to computing hypercontractive norms and estimating the expansion of small sets in graphs (a problem tightly related to the unique games conjecture).


Fernando Brandao

Fernando Brandao was born in 1983 in Belo Horizonte, Brazil. He obtained his PhD in Physics from Imperial College London in 2005. He is currently lecturer (assistant professor) in the computer science department of University College London. Previously he held positions at ETH Zurich, Universidade Federal de Minas Gerais, and Imperial College London. His main research interests are quantum information theory and quantum computation. He is also interested in connections of the area with other disciplines, such as optimization theory, many-body quantum physics, computational complexity, information theory, and thermodynamics.