  We present a quasipolynomial-time algorithm for solving the weak membership
problem for the convex set of separable, i.e. non-entangled, bipartite density
matrices. The algorithm decides whether a density matrix is separable or
whether it is eps-away from the set of the separable states in time
exp(O(eps^-2 log |A| log |B|)), where |A| and |B| are the local dimensions, and
the distance is measured with either the Euclidean norm, or with the so-called
LOCC norm. The latter is an operationally motivated norm giving the optimal
probability of distinguishing two bipartite quantum states, each shared by two
parties, using any protocol formed by quantum local operations and classical
communication (LOCC) between the parties. We also obtain improved algorithms
for optimizing over the set of separable states and for computing the
ground-state energy of mean-field Hamiltonians.
  The techniques we develop are also applied to quantum Merlin-Arthur games,
where we show that multiple provers are not more powerful than a single prover
when the verifier is restricted to LOCC protocols, or when the verification
procedure is formed by a measurement of small Euclidean norm. This answers a
question posed by Aaronson et al (Theory of Computing 5, 1, 2009) and provides
two new characterizations of the complexity class QMA, a quantum analog of NP.
Our algorithm uses semidefinite programming to search for a symmetric
extension, as first proposed by Doherty, Parrilo and Spedialieri (Phys. Rev. A,
69, 022308, 2004). The bound on the runtime follows from an improved de
Finetti-type bound quantifying the monogamy of quantum entanglement, proved in
(arXiv:1010.1750). This result, in turn, follows from a new lower bound on the
quantum conditional mutual information and the entanglement measure squashed
entanglement.
