Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0301058 · Physical Review A

Checking 2×M quantum separability via semidefinite programming

Hugo J. Woerdeman

Published Jan 30, 2003• 10 citations
arXivHTMLPDF

Abstract

In this paper, we propose a sequence of tests which give a definitive test for checking $2\ifmmode\times\else\texttimes\fi{}M$ separability. The test is definitive in the sense that each test corresponds to checking membership in a cone, and that the closure of the union of all these cones consists exactly of all $2\ifmmode\times\else\texttimes\fi{}M$ separable states. Membership in each single cone may be checked via semidefinite programming, and is thus a tractable problem. This sequential test comes about by considering the dual problem, the characterization of all positive maps acting ${C}^{2\ifmmode\times\else\texttimes\fi{}2}\ensuremath{\rightarrow}{C}^{M\ifmmode\times\else\texttimes\fi{}M}.$ The latter in turn is solved by characterizing all positive quadratic matrix polynomials in a complex variable.

DOI
10.1103/physreva.67.010303

Related papers

Entanglement witnesses and semidefinite programming

Pablo A. Parrilo, Andrew C. Doherty, Federico M. Spedalieri

We study the application of sums of squares decompositions and semidefinite programming in the formulation of computational criteria for distinguishing entangled from separable quantum states. A hierarchy of tests is obtained, the simplest of which corresponds to the well-known positive partial transpose (PPT) sufficient criterion, with the more complicated tests being strictly stronger. The duality structure of the problem allows us to provide an explicit construction of the entanglement witnesses corresponding to our tests.

IEEE Conference on Decision and Control (CDC)•Jan 23, 2004•2 citations

Membership in the cone of quantum states over time is NP-hard

Matt Hoogsteder-Riera

A state over time (stote) pairs a state $ρ$ with a channel $\mathcal{E}$ as the Hermitian, generally non-positive operator $(ρ\otimes\mathbf{1})\star J_\mathcal{E}$. Characterizing the convex cone $\widehat{\mathcal{Q}}$ these operators generate was posed as an open problem in Hoogsteder-Riera, Calsamiglia and Winter (2026). We exhibit a linear copy of the bipartite separable cone as an exposed face of $\widehat{\mathcal{Q}}$: for output systems of the form $B = A'R$ with $A'$ a copy of the input, there is an explicit witness $W_0\in\widehat{\mathcal{Q}}^*$ and an explicit injective linear map $L$ with $σ\in \mathrm{SEP}_{+}(A{:}R)\iff L(σ)\in\widehat{\mathcal{Q}}(A{:}A'R)$. Composing with the NP-hardness of separability shows that exact membership, weak membership, and weak optimization are NP-hard for $\widehat{\mathcal{Q}}$ and its dual. A quantitative stability bound makes the weak-membership reduction valid at inverse-polynomial accuracy. Thus polynomial-time membership tests do not exist unless $\mathrm{P}=\mathrm{NP}$. Independently of this complexity assumption, Fawzi's theorem implies that $\widehat{\mathcal{Q}}(A{:}A'R)$ admits no finite semidefinite representation when $d=\dim A\ge2$, $r=\dim R\ge2$, and $d+r>5$.

quant-pharXiv:2610.34972•Oct 27, 2026•0 citations

Computational complexity of the quantum separability problem

Lawrence M. Ioannou

Ever since entanglement was identified as a computational and cryptographic resource, researchers have sought efficient ways to tell whether a given density matrix represents an unentangled, or \emph{separable}, state. This paper gives the first systematic and comprehensive treatment of this (bipartite) quantum separability problem, focusing on its deterministic (as opposed to randomized) computational complexity. First, I review the one-sided tests for separability, paying particular attention to the semidefinite programming methods. Then, I discuss various ways of formulating the quantum separability problem, from exact to approximate formulations, the latter of which are the paper's main focus. I then give a thorough treatment of the problem's relationship with NP, NP-completeness, and co-NP. I also discuss extensions of Gurvits' NP-hardness result to strong NP-hardness of certain related problems. A major open question is whether the NP-contained formulation (QSEP) of the quantum separability problem is Karp-NP-complete; QSEP may be the first natural example of a problem that is Turing-NP-complete but not Karp-NP-complete. Finally, I survey all the proposed (deterministic) algorithms for the quantum separability problem, including the bounded search for symmetric extensions (via semidefinite programming), based on the recent quantum de Finetti theorem \cite{DPS02,DPS04,qphCKMR06}; and the entanglement-witness search (via interior-point algorithms and global optimization) \cite{ITCE04,IT06}. These two algorithms have the lowest complexity, with the latter being the best under advice of asymptotically optimal point-coverings of the sphere.

arXiv:quant-ph/0603199•Quantum Information and Computation•May 1, 2007•111 citations

Distinguishing Separable and Entangled States

Andrew C. Doherty, Pablo A. Parrilo, Federico M. Spedalieri

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.

arXiv:quant-ph/0112007•Physical Review Letters•Apr 23, 2002•366 citations

DETERMINISTIC COMPUTATIONAL COMPLEXITY OF THE QUANTUM SEPARABILITY PROBLEM

Lawrence M. Ioannou

Ever since entanglement was identified as a computational and cryptographic resource, effort has been made to find an efficient way to tell whether a given density matrix represents an unentangled, or separable, state. Essentially, this is the quantum separability problem. In Section 1, I begin with a brief introduction to separability and entanglement, and a basic formal definition of the quantum separability problem. I conclude with a summary of one-sided tests for separability, including those involving semidefinite programming. In Section 2, I treat the separability problem as a computational decision problem and motivate its approximate formulations. After a review of basic complexity-theoretic notions, I discuss the computational complexity of the separability problem. In Section 3, I give a comprehensive survey of deterministic algorithmic solutions to the (approximate) quantum separability problem. Finally, Section 4 contains a comparison of the complexities of the algorithms surveyed in Section 3. I have attempted to give a comprehensive treatment of the deterministic quantum separability problem from a computational perspective and identify relevant open problems. Features and new results include:

•Mar 22, 2006•4 citations

Complete family of separability criteria

Andrew C. Doherty, Pablo A. Parrilo, Federico M. Spedalieri

We introduce a family of separability criteria that are based on the existence of extensions of a bipartite quantum state \ensuremath{\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.

arXiv:quant-ph/0308032•Physical Review A•Feb 18, 2004•467 citations
In this paper, we propose a sequence of tests which give a definitive test for checking 2\ifmmode×\else\texttimes\fiM2\ifmmode\times\else\texttimes\fi{}M2\ifmmode×\else\texttimes\fiM separability. The test is definitive in the sense that each test corresponds to checking membership in a cone, and that the closure of the union of all these cones consists exactly of all 2\ifmmode×\else\texttimes\fiM2\ifmmode\times\else\texttimes\fi{}M2\ifmmode×\else\texttimes\fiM separable states. Membership in each single cone may be checked via semidefinite programming, and is thus a tractable problem. This sequential test comes about by considering the dual problem, the characterization of all positive maps acting C2\ifmmode×\else\texttimes\fi2\ensuremath→CM\ifmmode×\else\texttimes\fiM.{C}^{2\ifmmode\times\else\texttimes\fi{}2}\ensuremath{\rightarrow}{C}^{M\ifmmode\times\else\texttimes\fi{}M}.C2\ifmmode×\else\texttimes\fi2\ensuremath→CM\ifmmode×\else\texttimes\fiM. The latter in turn is solved by characterizing all positive quadratic matrix polynomials in a complex variable.
We study the application of sums of squares decompositions and semidefinite programming in the formulation of computational criteria for distinguishing entangled from separable quantum states. A hierarchy of tests is obtained, the simplest of which corresponds to the well-known positive partial transpose (PPT) sufficient criterion, with the more complicated tests being strictly stronger. The duality structure of the problem allows us to provide an explicit construction of the entanglement witnesses corresponding to our tests.
A state over time (stote) pairs a state ρρρ with a channel E\mathcal{E}E as the Hermitian, generally non-positive operator (ρ⊗1)⋆JE(ρ\otimes\mathbf{1})\star J_\mathcal{E}(ρ⊗1)⋆JE​. Characterizing the convex cone Q^\widehat{\mathcal{Q}}Q​ these operators generate was posed as an open problem in Hoogsteder-Riera, Calsamiglia and Winter (2026). We exhibit a linear copy of the bipartite separable cone as an exposed face of Q^\widehat{\mathcal{Q}}Q​: for output systems of the form B=A′RB = A'RB=A′R with A′A'A′ a copy of the input, there is an explicit witness W0∈Q^∗W_0\in\widehat{\mathcal{Q}}^*W0​∈Q​∗ and an explicit injective linear map LLL with σ∈SEP+(A:R)  ⟺  L(σ)∈Q^(A:A′R)σ\in \mathrm{SEP}_{+}(A{:}R)\iff L(σ)\in\widehat{\mathcal{Q}}(A{:}A'R)σ∈SEP+​(A:R)⟺L(σ)∈Q​(A:A′R). Composing with the NP-hardness of separability shows that exact membership, weak membership, and weak optimization are NP-hard for Q^\widehat{\mathcal{Q}}Q​ and its dual. A quantitative stability bound makes the weak-membership reduction valid at inverse-polynomial accuracy. Thus polynomial-time membership tests do not exist unless P=NP\mathrm{P}=\mathrm{NP}P=NP. Independently of this complexity assumption, Fawzi's theorem implies that Q^(A:A′R)\widehat{\mathcal{Q}}(A{:}A'R)Q​(A:A′R) admits no finite semidefinite representation when d=dim⁡A≥2d=\dim A\ge2d=dimA≥2, r=dim⁡R≥2r=\dim R\ge2r=dimR≥2, and d+r>5d+r>5d+r>5.
Ever since entanglement was identified as a computational and cryptographic resource, researchers have sought efficient ways to tell whether a given density matrix represents an unentangled, or \emph{separable}, state. This paper gives the first systematic and comprehensive treatment of this (bipartite) quantum separability problem, focusing on its deterministic (as opposed to randomized) computational complexity. First, I review the one-sided tests for separability, paying particular attention to the semidefinite programming methods. Then, I discuss various ways of formulating the quantum separability problem, from exact to approximate formulations, the latter of which are the paper's main focus. I then give a thorough treatment of the problem's relationship with NP, NP-completeness, and co-NP. I also discuss extensions of Gurvits' NP-hardness result to strong NP-hardness of certain related problems. A major open question is whether the NP-contained formulation (QSEP) of the quantum separability problem is Karp-NP-complete; QSEP may be the first natural example of a problem that is Turing-NP-complete but not Karp-NP-complete. Finally, I survey all the proposed (deterministic) algorithms for the quantum separability problem, including the bounded search for symmetric extensions (via semidefinite programming), based on the recent quantum de Finetti theorem \cite{DPS02,DPS04,qphCKMR06}; and the entanglement-witness search (via interior-point algorithms and global optimization) \cite{ITCE04,IT06}. These two algorithms have the lowest complexity, with the latter being the best under advice of asymptotically optimal point-coverings of the sphere.
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.
Ever since entanglement was identified as a computational and cryptographic resource, effort has been made to find an efficient way to tell whether a given density matrix represents an unentangled, or separable, state. Essentially, this is the quantum separability problem. In Section 1, I begin with a brief introduction to separability and entanglement, and a basic formal definition of the quantum separability problem. I conclude with a summary of one-sided tests for separability, including those involving semidefinite programming. In Section 2, I treat the separability problem as a computational decision problem and motivate its approximate formulations. After a review of basic complexity-theoretic notions, I discuss the computational complexity of the separability problem. In Section 3, I give a comprehensive survey of deterministic algorithmic solutions to the (approximate) quantum separability problem. Finally, Section 4 contains a comparison of the complexities of the algorithms surveyed in Section 3. I have attempted to give a comprehensive treatment of the deterministic quantum separability problem from a computational perspective and identify relevant open problems. Features and new results include:
We introduce a family of separability criteria that are based on the existence of extensions of a bipartite quantum state \ensuremath{\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.