How hard is it to decide if a quantum state is separable or entangled?

Suppose that a physical process, described as a sequence of local interactions that can be executed in a reasonable amount of time, generates a quantum state shared between two parties. We might then wonder, does this physical process produce a quantum state that is separable or entangled? Here, we give evidence that it is computationally hard to decide the answer to this question, even if one has access to the power of quantum computation. In order to address this question, we begin by demonstrating a two-message quantum interactive proof system that can decide the answer to a promise version of this problem. We then prove that this promise problem is hard for the class ``quantum statistical zero knowledge'' (QSZK) by demonstrating a polynomial-time reduction from the QSZK-complete promise problem ``quantum state distinguishability'' to our quantum separability problem. Finally, we consider a variant of this question, in which a given physical process accepts a quantum state as input, and the question is to decide if there is an input to this process which makes its output separable across some bipartite cut. We prove that this latter problem is a complete promise problem for the class QIP of problems admitting quantum interactive proof systems.