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

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

Seminar author:Mark M. Wilde

Event date and time:04/23/2013 02:30:pm

Event location:

Event contact:

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. This is joint work with Patrick Hayden and Kevin Milner and is available at http://arxiv.org/abs/1211.6120 .