CENTER FOR COMPUTATION & TECHNOLOGY

Suppose that a physical process, described as a sequence of local two-body 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.

Free coffee and donuts provided.