A complete family of separability criteria

I. INTRODUCTION

• Mixed-state separability lacks a single practical procedure guaranteed to detect every entangled state, although deciding separability is NP-hard.Existing criteria detect only some states or apply only in restricted dimensions.Source: §I · p. 1
• The PPT criterion is efficient and complete in 2 ⊗ 2 and 2 ⊗ 3, but higher dimensions contain PPT bound-entangled states.Other criteria, including range, reduction, and majorization tests, do not provide a complete characterization.Source: §I · pp. 1–2

II. PPT SYMMETRIC EXTENSIONS AND NEW SEPARABILITY CRITERIA

• The paper tests whether a state has an extension to additional copies of one subsystem that is symmetric, reduces to the original state, and remains positive under all partial transposes.Separable states have such extensions; failure to find one proves entanglement.Source: §II · pp. 3–4
• Extensions form a hierarchy beginning with PPT, where each higher test is at least as powerful as the preceding one and every entangled state fails at some finite level.The hierarchy can be generalized to multipartite systems.Source: §II · p. 4
• Each test is a semidefinite program whose dual constructs an explicit entanglement witness for an infeasible extension.The framework also connects witnesses with positive maps and characterizes the interior of the entanglement-witness cone.Source: §I · pp. 2–3, §II · p. 4

A. Semidefinite programs

• An SDP optimizes a linear function subject to a linear matrix inequality, with feasibility reducing to finding variables that make a matrix positive semidefinite.Convexity enables reliable analytical and numerical solution methods.Source: A. Semidefinite programs · p. 4
• Dual SDP feasibility provides bounds on the primal objective, and under strict feasibility strong duality gives equal optimal values and complementary slackness.These properties connect primal extension searches with dual certificates.Source: A. Semidefinite programs · pp. 4–5

B. Separability tests as semidefinite programs

• When the extension SDP is infeasible, a dual feasible matrix certifies infeasibility and, for this hierarchy, yields an entanglement witness.The analytical SDP form is retained because its dual is especially transparent for witness construction.Source: A. Semidefinite programs · p. 5, B. Separability tests as semidefinite… · p. 6
• For extension testing, fixed components enforce the marginal and symmetry constraints, while the remaining extension coefficients serve as SDP variables.The positivity constraints become linear matrix inequalities.Source: B. Separability tests as semidefinite… · p. 5
• The two-copy test combines positivity of the extension and its independent partial transposes into the block-diagonal constraint F = ρ̃ ⊕ ρ̃^TA ⊕ ρ̃^TB ≥ 0.The zero objective makes this an SDP feasibility problem.Source: B. Separability tests as semidefinite… · p. 6

C. Resources needed to implement the tests

• For fixed k, checking the hierarchy scales polynomially with the system dimensions, with the stated worst-case computation scaling no worse than O(d_A^13k/2).The SDP matrix has block structure, and numerical solvers use least-squares subproblems.Source: C. Resources needed to implement the… · p. 6
• For fixed subsystem dimensions, exploiting swapping symmetry reduces resource growth with the number of copies from exponential to polynomial.The unoptimized matrix size grows exponentially in k.Source: C. Resources needed to implement the… · p. 6
• No finite hierarchy level detects all entangled states for all subsystem dimensions, consistent with the NP-hardness of the general separability problem.The required level must increase as dimensions vary.Source: C. Resources needed to implement the… · p. 6

IV. EXPLOITING THE SYMMETRY

• Symmetric extensions restrict the search to the symmetric subspace of the copies of subsystem A, replacing exponential growth with polynomial scaling.The extension obeys ˜ρ=π˜ρπ for two copies, with analogous restrictions for k copies.Source: §IV · pp. 6–7
• For fixed d_A, exploiting symmetric-subspace support makes the hierarchy scale polynomially as O(k^(6d_A−4)) in the number of copies.The resulting SDP has polynomial variable and matrix-size scaling after block diagonalization.Source: §IV · p. 7

V. COMPLETENESS OF THE HIERARCHY OF TESTS

• A bipartite mixed state has symmetric extensions to every number of copies of A if and only if it is separable.The proof constructs separable states from the extensions using the Quantum de Finetti Theorem.Source: §V · pp. 7, 9
• Therefore, the PPT-extension hierarchy is complete, while searching for symmetric extensions without PPT constraints is also complete and requires fewer resources.The PPT requirement strengthens the finite-level tests and is described as a practical trade-off between power and resources.Source: §V · p. 9

VI. CONSTRUCTION OF ENTANGLEMENT WITNESSES

• An entanglement witness separates an entangled state from the convex set of separable states by having nonnegative expectation on separable states and negative expectation on the target state.This geometric interpretation follows from convexity and the Hahn–Banach theorem.Source: §VI · p. 9
• Verifying witness positivity on all separable states is equivalent to checking positivity of an associated bihermitian form, an NP-hard task in general.This computational difficulty explains why constructing witnesses is not generally easy.Source: §VI · p. 9
• When the primal extension SDP is infeasible, its dual supplies an entanglement witness certifying the state’s entanglement.The same reasoning applies across all hierarchy levels, not only the second test.Source: §VI · pp. 9–10

A. Algebraic properties of the entanglement witnesses

• Witnesses from the second test become sums of squares after multiplication by a strictly positive SOS factor, and this generalizes to every hierarchy level.A witness from the (k+1)th test has an associated form that becomes SOS after multiplication by a suitable power of ⟨x|x⟩.Source: A. Algebraic properties of the… · p. 11
• A k-SOS witness is also l-SOS for every l≥k; 0-SOS witnesses are decomposable, whereas k-SOS witnesses with k≥1 are indecomposable.The hierarchy’s SOS classes are nested.Source: A. Algebraic properties of the… · p. 11
• The PPT and non-PPT families differ in their allowed SOS terms, and the non-PPT family generally needs a higher multiplying power.PPT-family decompositions may involve conjugate variables, while non-PPT decompositions use only the variables (x_i,y_j).Source: A. Algebraic properties of the… · p. 12
• The k-SOS cones approximate the full witness cone from inside and completely characterize its interior.Interior witnesses are k-SOS for some finite k.Source: A. Algebraic properties of the… · p. 12
• Boundary witnesses may fail to be k-SOS for every k; these include optimal witnesses whose hyperplanes touch the separable-state set.The result does not claim that every witness is k-SOS.Source: A. Algebraic properties of the… · p. 12
• The extension-based criteria and dual witness construction generalize to multipartite systems, where a separate complete sequence of tests can be constructed.The multipartite results are stated as work to be reported elsewhere.Source: A. Algebraic properties of the… · pp. 12–13

VII. EXAMPLES

• For the state ρα, numerical entanglement witnesses can be constructed from an SDP solution when 3+ε<α≤4 or 1≤α<2−ε, with ε≥10^-8.A witness for α>3 can be extracted by inspection, and the Choi form can be recovered from this entanglement witness.Source: A. 3 ⊗3 state · p. 13
• For the 3×3 example, the witness certifies entanglement for all α>3, while the non-PPT hierarchy fails up to approximately α≲3.84 even at its sixth test.This demonstrates that the non-PPT hierarchy can be considerably weaker than the PPT hierarchy in this example.Source: A. 3 ⊗3 state · p. 13
• The PPT criterion proves entanglement only for states with α < 2√2 ≈ 2.82843, whereas the new criteria show that the state is entangled for all nonnegative α.Only the second level of the hierarchy is needed, and the approach provides an explicit entanglement witness and its decomposition.Source: B. 4 ⊗4 state · pp. 13–14
• The second hierarchy test sufficed for all examined bound-entangled states up to dimensions 6×6, producing numerical and sometimes analytical witnesses.The authors note that some entangled states must nevertheless pass the second test.Source: §VII · p. 13, B. 4 ⊗4 state · p. 14

• For each k, states passing the kth test are exactly those with PPT symmetric extensions to k copies of party A.Source: §VIII · p. 14
• These nested sets all contain the separable states and converge to the set of separable states by the completeness theorem.Source: §VIII · p. 14
• Each set is convex and compact, motivating questions about nonemptiness, hierarchy depth, entangled-state volume, and LOCC invariance.Source: §VIII · p. 14

• A PPT-entangled state detected by the second test yields, after scaling, witnesses whose SOS properties force a critical γ∗ > 0.Source: A. Constructing entangled states with… · pp. 14–15
• The scaled state ργ remains entangled for every γ > 0, while the scaled witness Zγ is constructed through an invertible local transformation.Source: A. Constructing entangled states with… · pp. 14–15
• The argument applies whenever a PPT-entangled state is detected by the second test, independently of subsystem dimensionality.Source: A. Constructing entangled states with… · p. 15
• Convex-cone duality implies that a strict separation between witness cones produces an entangled state passing the second test but detected at a later level.Source: A. Constructing entangled states with… · p. 15
• For the Choi state with α = 3.0001, numerical testing found γ∗ ≃ 0.4901 such that every γ < γ∗ gives an entangled state undetected by the second test.Source: A. Constructing entangled states with… · p. 15

• The fixed-multiplier SOS approach is unstable under linear transformations, and allowing a variable multiplier may prevent formulation as an SDP.Source: B. Properties of the hierarchy · p. 15
• SLOCC can transform states between being detected and undetected by the second test, so the second and higher hierarchy classes are not LOCC-invariant.Source: B. Properties of the hierarchy · p. 15
• For any fixed k, scaling shows that a PPT-entangled state implies an entangled state ρk undetected by the kth test.Source: B. Properties of the hierarchy · pp. 15–16
• In dimensions with dA × dB > 6, entangled states can pass the first k tests for every fixed k, so the hierarchy does not collapse finitely except in 2 ⊗ 2 and 2 ⊗ 3.Source: B. Properties of the hierarchy · p. 16
• Whenever consecutive extension sets differ, the states passing level k−1 but failing level k include a nonempty ball and therefore have nonzero measure.Source: B. Properties of the hierarchy · p. 16

• An SDP can test witness decomposability; when a witness is indecomposable, its dual constructs a bound entangled state detected by that witness.Source: §IX · p. 16
• The primal SDP minimizes the witness expectation over normalized positive PPT states, using ρ ≥ 0 and ρ^TA ≥ 0 as constraints.Source: §IX · p. 16
• Strict feasibility and complementary slackness provide optimal matrices whose ranges satisfy orthogonality relations with the optimal state and its partial transpose.Source: §IX · pp. 16–17
• When the optimum is sufficiently negative, the optimizer ρopt is entangled while remaining PPT, hence it is bound entangled and the witness is indecomposable.Source: §IX · p. 17
• Optimality further shows that ρopt is an edge PPT entangled state, and the SDP yields the canonical decomposition of the indecomposable witness.Source: §IX · p. 17

• Entanglement witnesses correspond one-to-one with positive non-completely-positive maps, allowing the hierarchy’s witness characterization to be transferred to positive maps.Source: §X · p. 17
• The interior of the entanglement-witness cone maps to positive maps that send every nonzero positive semidefinite operator to a positive definite operator.Source: §X · p. 17
• For a strictly positive map, a finite hierarchy level yields a completely positive lifted map; conversely, complete positivity at a hierarchy level implies positivity of the original map.Source: §X · p. 18
• The lifted map is tested by tensoring with identity maps, projecting onto the symmetric subspace, and checking whether the resulting operator is positive semidefinite.Source: §X · p. 18
• For the numerical example, convergence toward α = 1 is consistent with lim_k→∞ α_k = 1 but appears relatively slow, of order 1/k.Source: §X · p. 18
• The map-based positivity tests reduce checking positivity to a sequence of matrix-positivity tests, which can certify many instances efficiently but do not succeed uniformly for all maps.Source: §X · p. 19

• The hierarchy tests whether a state has a symmetric, partially-transpose-positive extension; failure proves entanglement, while feasibility is inconclusive.Source: §XI · p. 19
• Each successive test is at least as powerful as the preceding one, and the first test is the Peres-Horodecki PPT criterion.Source: §XI · p. 19
• The hierarchy is complete: every entangled state fails some finite test, while each test is an efficiently solvable semidefinite program that can produce an explicit entanglement witness through its dual.Source: §XI · p. 19
• The dual hierarchy characterizes the interior of the entanglement-witness cone through a sum-of-squares algebraic property.Source: §XI · p. 19
• For fixed test level, computational resources scale polynomially with state dimensions and, for fixed state size, with the number of added copies; however, some states require arbitrarily high levels.Source: §XI · p. 19
• Its primal formulation approximates the separable-state cone from the outside and applies to arbitrary subsystem dimensions, unlike the cited inside approximation restricted to one dimension-2 subsystem.Source: §XI · p. 19
• The hierarchy partitions entangled states by the largest number of PPT symmetric extensions they possess, with infinitely many classes except in 2 ⊗ 2 and 2 ⊗ 3, where PPT suffices.Source: §XI · p. 19

APPENDIX A: IMPROVED SDP FOR IMPLEMENTING THE TESTS

• The improved SDP detects entanglement by minimizing t: a nonpositive minimum corresponds to feasibility, whereas a strictly positive minimum proves infeasibility.Source: Appendix A · p. 20
• The reformulated SDP is always feasible, improving numerical behavior for the interior-point solver used to apply the tests.Source: Appendix A · p. 20

APPENDIX B: STRONG DUALITY AND SDP INFEASIBILITY

• An infeasibility witness follows by separating F0 from range F plus the positive semidefinite cone when that sum is closed.Source: Appendix B · p. 20
• The sum of two closed sets need not be closed in SDP, so infeasible problems can lack a witness of the desired positive-semidefinite form.Source: Appendix B · p. 20
• A Slater condition guarantees the needed closedness and witness existence by requiring a positive-definite matrix orthogonal to all constraint matrices.Source: Appendix B · p. 20