Bulletin of the American Physical Society
APS March Meeting 2013
Volume 58, Number 1
Monday–Friday, March 18–22, 2013; Baltimore, Maryland
Session T27: Focus Session: Superselection and Quantum Reference Frames
8:00 AM–11:00 AM,
Thursday, March 21, 2013
Sponsoring Unit: GQI
Chair: Ian Durham, Saint Anselm College
Abstract ID: BAPS.2013.MAR.T27.5
Abstract: T27.00005 : How hard is it to decide if a quantum state is separable or entangled?
9:36 AM–9:48 AM
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.
To cite this abstract, use the following reference: http://meetings.aps.org/link/BAPS.2013.MAR.T27.5
The American Physical Society (APS) is a non-profit membership organization working to advance the knowledge of physics.
1 Physics Ellipse, College Park, MD 20740-3844
Editorial Office 1 Research Road, Ridge, NY 11961-2701 (631) 591-4000
Office of Public Affairs 529 14th St NW, Suite 1050, Washington, D.C. 20045-2001 (202) 662-8700