Theory of Computing
-------------------
Title     : Quantum Interactive Proofs and the Complexity of Separability Testing
Authors   : Gus Gutoski, Patrick Hayden, Kevin Milner, and Mark M. Wilde
Volume    : 11
Number    : 3
Pages     : 59-103
URL       : https://theoryofcomputing.org/articles/v011a003

Abstract
--------

We identify a formal connection between physical problems related
to the detection of separable (unentangled) quantum states and
complexity classes in theoretical computer science. In particular,
we show that to nearly every quantum interactive proof complexity
class (including BQP, QMA, QMA(2), and QSZK), there corresponds a
natural separability testing problem that is complete for that
class. Of particular interest is the fact that the problem of
determining whether an isometry can be made to produce a separable
state is either QMA-complete or QMA(2)-complete, depending upon
whether the distance between quantum states is measured by the
one-way LOCC norm or the trace norm. We obtain strong hardness
results by employing prior work on entanglement purification
protocols to prove that for each  n-qubit maximally entangled
state there exists a fixed one-way LOCC measurement that
distinguishes it from any separable state with error probability
that decays exponentially in  n.