Simple Algorithm
Quantum Computing · Rydberg State · 30 min

Separability, PPT & Entanglement Witnesses

Detecting entanglement in mixed states.

Is a given density matrix entangled? For a pure state one glance at the Schmidt rank decides. For mixed states the question is NP-hard in general, yet for two qubits a single eigenvalue settles it, and in the lab a few local measurements can certify entanglement without full tomography. Both facts come from the convex geometry of the separable set.

What you’ll learn

  • Define separability and explain why deciding it is hard in general.
  • Prove the Peres criterion, apply it to Werner states, and explain why PPT is also sufficient in dimensions 2×22\times2 and 2×32\times3.
  • Construct entanglement witnesses (from NPT eigenvectors, fidelities and local correlations) and relate them to positive maps via Hahn–Banach and the Choi–Jamiołkowski correspondence.
  • Build a bound entangled state from an unextendible product basis and explain why only non-decomposable witnesses can detect it.

The separability problem

A mixed state has infinitely many decompositions into pure states, and being entangled means that none of them is a mixture of products. Deciding membership in SEP\mathrm{SEP} is NP-hard (Gurvits, 2003), even to inverse-polynomial accuracy (Gharibian, 2010). In practice one therefore uses criteria, necessary conditions for separability whose violation proves entanglement, and witnesses, observables whose negative expectation value certifies it.

Partial transposition

Werner states. (∣Ψ−⟩ ⁣⟨Ψ−∣)Γ(\dyad{\Psi^-})^\Gamma is locally equivalent to Φ2Γ=F/2\Phi_2^\Gamma=\mathbb F/2, half the swap operator, with eigenvalues 12,12,12,−12\tfrac12,\tfrac12,\tfrac12,-\tfrac12. Hence ρp=p ∣Ψ−⟩ ⁣⟨Ψ−∣+(1−p)I4\rho_p=p\,\dyad{\Psi^-}+(1-p)\tfrac{\id}4 has ρpΓ\rho_p^\Gamma with eigenvalues 1+p4\tfrac{1+p}{4} (three times) and 1−3p4\tfrac{1-3p}{4}.

Predict before you look

Above which value of pp is the Werner state ρp\rho_p NPT, and hence entangled?

Show the answer

0.33

The eigenvalue 1−3p4\tfrac{1-3p}{4} turns negative for p>13p>\tfrac13. Since PPT is exact for two qubits (below), ρp\rho_p is separable for p≤13p\le\tfrac13 and entangled above. Compare CHSH, which needs p>1/2p>1/\sqrt2.

The transpose is one positive map; Peres's criterion tests just that one, and in low dimensions that is enough. Every positive map between 2×22\times2 matrix algebras (Størmer, 1963), and between 2×22\times2 and 3×33\times3 matrix algebras (Woronowicz, 1976), is decomposable: Λ=Λ1+Λ2∘T\Lambda=\Lambda_1+\Lambda_2\circ T with Λ1,Λ2\Lambda_1,\Lambda_2 completely positive. For a PPT state,

(id⊗Λ)(ρ)=(id⊗Λ1)(ρ)+(id⊗Λ2)(ρΓ)⪰0,(\mathrm{id}\otimes\Lambda)(\rho)=(\mathrm{id}\otimes\Lambda_1)(\rho)+(\mathrm{id}\otimes\Lambda_2)(\rho^\Gamma)\succeq0,

so it passes every positive-map test and is separable.

Entanglement witnesses

DerivationThree ways to build a witness
  1. ρΓ∣v⟩=λ∣v⟩, λ<0 ⇒ W=(∣v⟩ ⁣⟨v∣)Γ\rho^\Gamma\ket v=\lambda\ket v,\ \lambda<0\ \Rightarrow\ W=\big(\dyad v\big)^\Gamma

    From an NPT eigenvector. Tr⁡(Wρ)=Tr⁡(∣v⟩ ⁣⟨v∣ ρΓ)=λ<0\Tr(W\rho)=\Tr(\dyad v\,\rho^\Gamma)=\lambda<0, while for separable σ\sigma, Tr⁡(Wσ)=⟨v|σΓ|v⟩≥0\Tr(W\sigma)=\mel{v}{\sigma^\Gamma}{v}\ge0 by the Peres criterion.

  2. Wψ=λmax⁡(ψ) I−∣ψ⟩ ⁣⟨ψ∣W_\psi=\lambda_{\max}(\psi)\,\id-\dyad\psi

    Fidelity witness. The largest overlap of a product state with ∣ψ⟩\ket\psi is its largest Schmidt coefficient λmax⁡\lambda_{\max}. For ∣Φ+⟩\ket{\Phi^+}, W=12I−∣Φ+⟩ ⁣⟨Φ+∣W=\tfrac12\id-\dyad{\Phi^+} detects every state with fidelity F>12F>\tfrac12.

  3. W=I−X⊗X−Z⊗ZW=\id-X\otimes X-Z\otimes Z

    Few local settings. For a product state with Bloch vectors a⃗,b⃗\vec a,\vec b, ⟨X⊗X⟩+⟨Z⊗Z⟩=axbx+azbz≤∣a⃗∣ ∣b⃗∣≤1\expval{X\otimes X}+\expval{Z\otimes Z}=a_xb_x+a_zb_z\le\abs{\vec a}\,\abs{\vec b}\le1, and convexity extends this to all of SEP\mathrm{SEP}. For ∣Φ+⟩\ket{\Phi^+}, ⟨W⟩=1−1−1=−1\expval{W}=1-1-1=-1.

Witnesses and maps. By the Choi–Jamiołkowski correspondence, WW is a witness iff it is, up to normalization, the Choi matrix (id⊗Λ)(∣Φd⟩ ⁣⟨Φd∣)(\mathrm{id}\otimes\Lambda)(\dyad{\Phi_d}) of a map Λ\Lambda that is positive but not completely positive. A witness is decomposable if W=P+QΓW=P+Q^\Gamma with P,Q⪰0P,Q\succeq0. For a PPT state,

Tr⁡[(P+QΓ)ρ]=Tr⁡(Pρ)+Tr⁡(QρΓ)≥0,\Tr\big[(P+Q^\Gamma)\rho\big]=\Tr(P\rho)+\Tr(Q\rho^\Gamma)\ge0,

so decomposable witnesses never detect PPT entanglement.

Check your understanding

A witness has the form W=P+QΓW=P+Q^\Gamma with P,Q⪰0P,Q\succeq0. Can it detect a PPT entangled state?

  1. Yes, if the local dimensions are large enough
  2. Only if P=0P=0
  3. Never: Tr⁡(Wρ)=Tr⁡(Pρ)+Tr⁡(QρΓ)≥0\Tr(W\rho)=\Tr(P\rho)+\Tr(Q\rho^\Gamma)\ge0 whenever ρΓ⪰0\rho^\Gamma\succeq0
  4. Yes, if ρ\rho has full rank
Show the answer

C. Never: Tr⁡(Wρ)=Tr⁡(Pρ)+Tr⁡(QρΓ)≥0\Tr(W\rho)=\Tr(P\rho)+\Tr(Q\rho^\Gamma)\ge0 whenever ρΓ⪰0\rho^\Gamma\succeq0

Both terms are non-negative for a PPT state: Tr⁡(Pρ)≥0\Tr(P\rho)\ge0 since ρ⪰0\rho\succeq0, and Tr⁡(QρΓ)≥0\Tr(Q\rho^\Gamma)\ge0 since ρΓ⪰0\rho^\Gamma\succeq0. Detecting bound entanglement requires non-decomposable witnesses, which correspond to non-decomposable positive maps.

Bound entanglement and beyond PPT

To find PPT entangled states, look for a state whose range contains no product vector at all. Unextendible product bases provide exactly that.

DerivationA PPT entangled state from a UPB
  1. ρ=14(I9−∑i=04∣ψi⟩ ⁣⟨ψi∣)\rho=\frac14\Big(\id_9-\sum_{i=0}^{4}\dyad{\psi_i}\Big)

    The normalized projector onto the 4-dimensional complement of the UPB {∣ψi⟩}\{\ket{\psi_i}\}.

  2. ρΓ=ρ⪰0\rho^\Gamma=\rho\succeq0

    Every ∣ψi⟩\ket{\psi_i} is a product of real vectors, so partial transposition maps each projector ∣ψi⟩ ⁣⟨ψi∣\dyad{\psi_i} to itself: ρ\rho is PPT.

  3. If ρ\rho were separable, ρ=∑jqj∣ajbj⟩ ⁣⟨ajbj∣\rho=\sum_jq_j\dyad{a_jb_j}, each product vector ∣ajbj⟩\ket{a_jb_j} would lie in the range of ρ\rho, hence be orthogonal to all five ∣ψi⟩\ket{\psi_i}, contradicting unextendibility. So ρ\rho is entangled and PPT: bound entangled (Bennett, DiVincenzo, Mor, Shor, Smolin & Terhal, 1999).

Detecting such states needs tools beyond PPT. The realignment (CCNR) criterion states that every separable ρ\rho has ∥R(ρ)∥1≤1\norm{R(\rho)}_1\le1, where RR rearranges matrix elements as R(ρ)(ij),(kl)=ρ(ik),(jl)R(\rho)_{(ij),(kl)}=\rho_{(ik),(jl)}; for the Tiles state ∥R(ρ)∥1≈1.087\norm{R(\rho)}_1\approx1.087, which certifies its entanglement. Alternatively one needs non-decomposable witnesses, for example built from Choi's positive map on 3×33\times3 matrices.

Complete hierarchies. ρAB\rho_{AB} is separable iff, for every kk, it has a symmetric extension to AB1⋯BkAB_1\cdots B_k: a state invariant under permutations of the BiB_i whose AB1AB_1 marginal is ρAB\rho_{AB} (one may also demand PPT). Each level is a semidefinite program: the Doherty–Parrilo–Spedalieri hierarchy (2002, 2004). Quantum de Finetti theorems bound the distance of a kk-extendible state from SEP\mathrm{SEP} by a quantity of order dB2/kd_B^2/k. Consistent with NP-hardness, the cost of reaching a fixed accuracy grows exponentially with the local dimension.

Key takeaways

  • SEP\mathrm{SEP} is convex and compact; deciding membership is NP-hard, so we use criteria (necessary conditions) and witnesses (certificates).
  • Peres–Horodecki: separable ⇒ρΓ⪰0\Rightarrow\rho^\Gamma\succeq0, and in 2×22\times2 and 2×32\times3 the converse holds (decomposability of positive maps); the Werner state is entangled iff p>13p>\tfrac13.
  • Every entangled state is detected by some witness (Hahn–Banach). Witnesses correspond to positive, non-CP maps and can be built from NPT eigenvectors, fidelities or a few local correlations.
  • PPT entangled (bound entangled) states exist beyond 2×32\times3, for example from unextendible product bases; detecting them needs non-decomposable witnesses or criteria such as realignment.
  • Symmetric-extension (DPS) hierarchies give complete SDP tests whose cost grows quickly, consistent with NP-hardness.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

For which bipartite dimensions is the PPT criterion necessary and sufficient for separability?

  1. All finite dimensions
  2. 2×22\times2 only
  3. 2×n2\times n for every nn
  4. 2×22\times2 and 2×32\times3 only
Show the answer

D. 2×22\times2 and 2×32\times3 only

Positive maps are decomposable exactly in these low dimensions (Størmer, Woronowicz), so PPT states pass every positive-map test. In 2×42\times4 and 3×33\times3 there are PPT entangled states.

Question 2

A two-qubit state has fidelity F=⟨Φ+|ρ|Φ+⟩=0.7F=\mel{\Phi^+}{\rho}{\Phi^+}=0.7. With the witness W=12I−∣Φ+⟩ ⁣⟨Φ+∣W=\tfrac12\id-\dyad{\Phi^+}, what do you measure and conclude?

  1. ⟨W⟩=−0.2\expval{W}=-0.2: the state is entangled
  2. ⟨W⟩=0.2\expval{W}=0.2: the state is separable
  3. ⟨W⟩=−0.2\expval{W}=-0.2: the state violates CHSH
  4. ⟨W⟩=−0.7\expval{W}=-0.7: the state is entangled
Show the answer

A. ⟨W⟩=−0.2\expval{W}=-0.2: the state is entangled

⟨W⟩=12−F=−0.2<0\expval{W}=\tfrac12-F=-0.2<0, which certifies entanglement. A witness never certifies nonlocality: the Bell-diagonal state with weights (0.7,0,0.2,0.1)(0.7,0,0.2,0.1) has F=0.7F=0.7 yet no CHSH violation.

Question 3

Why is the Tiles state ρ=14(I−∑i∣ψi⟩ ⁣⟨ψi∣)\rho=\tfrac14\big(\id-\sum_i\dyad{\psi_i}\big) entangled?

  1. It is NPT
  2. Its reduced states are pure
  3. Its range contains no product vector, so it cannot be a mixture of product states
  4. It violates the CHSH inequality
Show the answer

C. Its range contains no product vector, so it cannot be a mixture of product states

Any separable decomposition would use product vectors from the range of ρ\rho, but every vector in the range is orthogonal to the UPB, and by unextendibility no such vector is a product.

Question 4

Which statement about entanglement witnesses is correct?

  1. A single well-chosen witness detects all entangled states of a given dimension
  2. For every entangled state some witness detects it, but no single witness detects them all
  3. A non-negative witness value proves that the state is separable
  4. Measuring a witness requires full state tomography
Show the answer

B. For every entangled state some witness detects it, but no single witness detects them all

Hahn–Banach separation gives a witness for each entangled state, but the entangled set is not convex, so no single hyperplane cuts it off entirely from SEP\mathrm{SEP}.

Further reading

  • A. Peres, "Separability criterion for density matrices", Phys. Rev. Lett. 77, 1413 (1996).
  • M. Horodecki, P. Horodecki & R. Horodecki, "Separability of mixed states: necessary and sufficient conditions", Phys. Lett. A 223, 1 (1996).
  • P. Horodecki, "Separability criterion and inseparable mixed states with positive partial transposition", Phys. Lett. A 232, 333 (1997).
  • A. C. Doherty, P. A. Parrilo & F. M. Spedalieri, "Distinguishing separable and entangled states", Phys. Rev. Lett. 88, 187904 (2002).
  • O. Gühne & G. Tóth, "Entanglement detection", Physics Reports 474, 1 (2009).