The Complexity of Quantum Entanglement

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).