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.
In this paper, we propose a sequence of tests which give a definitive test for checking 2\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\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. 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 as the Hermitian, generally non-positive operator (ρ⊗1)⋆JE. Characterizing the convex cone 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: for output systems of the form B=A′R with A′ a copy of the input, there is an explicit witness W0∈Q∗ and an explicit injective linear map L with σ∈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 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. Independently of this complexity assumption, Fawzi's theorem implies that Q(A:A′R) admits no finite semidefinite representation when d=dimA≥2, r=dimR≥2, and d+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 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 [1, 2, 3]; and the entanglement-witness search (via interior-point algorithms and global optimization) [4, 5]. These two algorithms have the lowest complexity, with the latter being the best under advice of asymptotically optimal point-coverings of the sphere.
Let K, K' be convex cones residing in finite-dimensional real vector spaces E, E'. An element in the tensor product E \otimes E' is K \otimes K'-separable if it can be represented as finite sum \sum_l x_l \otimes x'_l with x_l \in K and x_l' \in K' for all l. Let S(n), H(n), Q(n) be the spaces of n x n real symmetric, complex hermitian and quaternionic hermitian matrices, respectively. Let further S_+(n), H_+(n), Q_+(n) be the cones of positive semidefinite matrices in these spaces. If a matrix in H(mn) = H(m) \otimes H(n) is H_+(m) \otimes H_+(n)-separable, then it fulfills also the so-called PPT condition, i.e. it is positive semidefinite and has a positive semidefinite partial transpose. The same implication holds for matrices in the spaces S(m) \otimes S(n), H(m) \otimes S(n), and for m < 3 in the space Q(m) \otimes S(n). We provide a complete enumeration of all pairs (n,m) when the inverse implication is also true for each of the above spaces, i.e. the PPT condition is sufficient for separability. We also show that a matrix in Q(n) \otimes S(2) is Q_+(n) \otimes S_+(2)-separable if and only if it is positive semidefinite.
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 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 the complexity classes NP, NP-complete, 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; and the entanglement-witness search (via interior-point algorithms and global optimization). These two algorithms have the lowest complexity, with the latter being the best under advice of asymptotically optimal point-coverings of the sphere.
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.