Aram Harrow, University of Washington
Abstract
This talk will begin by justifying the first part of the title, by explaining a method to test whether a given multipartite pure state is product or far from product, given only two copies of the state. Next, I'll explain how this test has implications for the computational hardness of a large number of optimization problems.
Some of these implications are positive: for example, finding the mean-field ground state of a k-body Hamiltonian has approximately the same difficulty for large k as it does when k=2. Other implications are negative, including the second part of the title: given a plausible complexity-theoretic assumption, there is no way to determine in poly(d) time whether a d-by-d density matrix is approximately separable.