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