Distinguishing Separable and Entangled States

Andrew C. Doherty, Pablo A. Parrilo, Federico M. SpedalieriPhysical 2002 · DOI · arXiv

Abstract

We show how to design families of operational criteria that distinguish entangled from separable quantum states. The simplest of these tests corresponds to the well-known Peres-Horodecki positive partial transpose (PPT) criterion, and the more complicated tests are strictly stronger. The new criteria are tractable due to powerful computational and theoretical methods for the class of convex optimization problems known as semidefinite programs. We successfully applied the results to many low-dimensional states from the literature where the PPT test fails. As a by-product of the criteria, we provide an explicit construction of the corresponding entanglement witnesses.

Introduction

Entanglement is a fundamental resource in quantum information science, enabling advancements in quantum teleportation, dense coding, and secure cryptography. Despite its importance, a central challenge remains: given a quantum state represented by a density matrix $\rho$, how can we determine if it is entangled or separable? While a state is separable if it can be written as a convex combination of product states, verifying this property is computationally difficult (NP-hard in the general case).

The Limits of the PPT Criterion

For years, the primary tool for entanglement detection was the Peres-Horodecki criterion, or the Positive Partial Transpose (PPT) test. This method posits that if the partial transpose of a density matrix has any negative eigenvalues, the state is definitely entangled. While the PPT criterion is a necessary and sufficient condition for small systems (such as $2 \times 2$ and $2 \times 3$ dimensions), it is only a necessary condition in higher dimensions. There exist "bound entangled" states—states that are entangled yet possess a positive partial transpose—rendering the PPT test insufficient for a complete classification of quantum states.

A Hierarchy of Symmetric Extensions

To address this gap, this research introduces a hierarchy of operational criteria based on the concept of symmetric extensions. The core idea is that if a state is separable, it must be possible to "extend" it into a larger Hilbert space containing multiple symmetric copies of its subsystems. If no such extension exists that satisfies specific positivity requirements, the state must be entangled.

This approach creates a nested hierarchy of tests. By increasing the number of copies ($k$ and $l$) in the extension, the criteria become progressively more stringent. This transforms the qualitative question of entanglement into a quantitative sequence of optimization checks, where each level is strictly stronger than the last. Notably, the standard PPT test is recovered as the simplest level ($k=1, l=1$) of this broader framework.

Computational Implementation via SDP

The search for these symmetric extensions is formulated as a Semidefinite Program (SDP), a powerful class of convex optimization problems. Mapping entanglement detection to SDPs allows the problem to be solved efficiently using polynomial-time algorithms.

A significant theoretical insight of this work is the connection between entanglement detection and real algebraic geometry. The authors demonstrate that finding an "entanglement witness"—a physical observable that yields a negative expectation value only for entangled states—is equivalent to finding a Sum-of-Squares (SOS) decomposition of a polynomial. This links the physics of entanglement to Hilbert’s 17th problem, providing a robust mathematical foundation for the hierarchy.

Results and Performance

The effectiveness of the hierarchy was validated against several benchmark states known to be notoriously difficult to classify, including:

  • PPT Entangled States: Specific families of states from Horodecki, Bruss, and Peres where the standard PPT test fails.
  • Unextendible Product Bases (UPB): States constructed from specific geometric arrangements that are known to be entangled despite being PPT.
  • Randomized Testing: A sample of 4,000 examples from a seven-parameter family of PPT entangled states.

The results were striking: the very first step beyond the PPT test ($k=2, l=1$) successfully detected entanglement in all the PPT entangled states tested from the existing literature. Furthermore, the method proved computationally practical. Even on contemporary hardware (a 500 MHz desktop), a $2 \times 4$ system could be evaluated in less than a second, while a $3 \times 3$ system required approximately eight seconds.

Conclusion

This research provides a systematic and computationally tractable path toward solving the separability problem. By utilizing the duality inherent in SDPs, the method not only detects entanglement but also provides explicit, analytical entanglement witnesses when a state fails a test. While challenges remain regarding numerical precision near the separable-entangled boundary and the memory requirements for very large systems, the hierarchy offers a powerful tool for probing the boundaries of quantum correlation.

Summary updated

Abstract

We show how to design families of operational criteria that distinguish entangled from separable quantum states. The simplest of these tests corresponds to the well-known Peres-Horodecki positive partial transpose (PPT) criterion, and the more complicated tests are strictly stronger. The new criteria are tractable due to powerful computational and theoretical methods for the class of convex optimization problems known as semidefinite programs. We successfully applied the results to many low-dimensional states from the literature where the PPT test fails. As a by-product of the criteria, we provide an explicit construction of the corresponding entanglement witnesses.
BibTeX
@inproceedings{doherty2002distinguishing,
  author = {Andrew C. Doherty and Pablo A. Parrilo and Federico M. Spedalieri},
  title = {{Distinguishing Separable and Entangled States}},
  booktitle = {Physical},
  year = {2002},
  doi = {10.1103/physrevlett.88.187904},
}
Figure