A Caltech Library Service

Complete family of separability criteria

Doherty, Andrew C. and Parrilo, Pablo A. and Spedalieri, Federico M. (2004) Complete family of separability criteria. Physical Review A, 69 (2). Art. No. 022308. ISSN 1050-2947. doi:10.1103/PhysRevA.69.022308.

See Usage Policy.


Use this Persistent URL to link to this item:


We introduce a family of separability criteria that are based on the existence of extensions of a bipartite quantum state rho to a larger number of parties satisfying certain symmetry properties. It can be easily shown that all separable states have the required extensions, so the nonexistence of such an extension for a particular state implies that the state is entangled. One of the main advantages of this approach is that searching for the extension can be cast as a convex optimization problem known as a semidefinite program. Whenever an extension does not exist, the dual optimization constructs an explicit entanglement witness for the particular state. These separability tests can be ordered in a hierarchical structure whose first step corresponds to the well-known positive partial transpose (Peres-Horodecki) criterion, and each test in the hierarchy is at least as powerful as the preceding one. This hierarchy is complete, in the sense that any entangled state is guaranteed to fail a test at some finite point in the hierarchy, thus showing it is entangled. The entanglement witnesses corresponding to each step of the hierarchy have well-defined and very interesting algebraic properties that, in turn, allow for a characterization of the interior of the set of positive maps. Coupled with some recent results on the computational complexity of the separability problem, which has been shown to be NP hard, this hierarchy of tests gives a complete and also computationally and theoretically appealing characterization of mixed bipartite entangled states.

Item Type:Article
Related URLs:
URLURL TypeDescription
Parrilo, Pablo A.0000-0003-1132-8477
Additional Information:©2004 The American Physical Society (Received 22 August 2003; published 18 February 2004) It is a pleasure to acknowledge stimulating conversations with Hideo Mabuchi, John Doyle, John Preskill, and Ben Schumacher. Thanks to Patrick Hayden for suggesting an improvement in an earlier proof of theorem 1, and to Nicolas Gisin for providing us with the PPT entangled state in Sec. VII B. A.C.D. gratefully acknowledges conversations with Barbara Terhal. F.M.S. thanks Oscar Bruno for many clarifying discussions regarding the completeness theorem. P.A.P. acknowledges interesting conversations with Bruce Reznick. This work was supported by the National Science Foundation as part of the Institute for Quantum Information under Grant No. EIA-0086083, the Caltech MURI Center for Quantum Networks (Grant No. DAAD19-00-1-0374), and the Caltech MURI Center for Uncertainty Management for Complex Systems.
Subject Keywords:quantum entanglement; quantum computing; computational complexity; optimisation
Issue or Number:2
Record Number:CaltechAUTHORS:DOHpra04
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:2029
Deposited By: Archive Administrator
Deposited On:02 Mar 2006
Last Modified:08 Nov 2021 19:44

Repository Staff Only: item control page