The Separability Problem and Entanglement Witnesses

Corresponds to Lectures 24–25. For pure states, product-vs-entangled was a clean dichotomy (an earlier note); for general mixed states, a state is separable if it can be written as a probabilistic mixture of product states, and the separable states form a convex set inside the set of all states. The separability problem — deciding membership in this set — is NP-hard in general, in sharp contrast to the pure-state case. Since the separable set is convex, the geometric fact that any point outside a convex set can be separated from it by a hyperplane gives a practical detection tool: an entanglement witness is a Hermitian operator $W$ with $\mathrm{Tr}(W\rho)\ge0$ for every separable $\rho$ but $\mathrm{Tr}(W\rho)<0$ for some entangled state — a single measurable quantity that certifies entanglement when negative, even though no single witness detects every entangled state.

Outline (TODO — flesh out each)

• The separability problem — definition and hardness
• The convex set of separable states
• Entanglement witnesses — construction from convex separation
• Limitations — no single witness detects all entangled states