Entanglement map · Established

Deciding separability is NP-hard

Proved, with a source.

Gurvits proved hardness for states within an inverse exponential distance of the separable set. Gharibian extended it to an inverse polynomial distance. So no efficient general test is expected unless P = NP, which is consistent with the hierarchy above having no fixed cut-off level.

Connections

• Part of: Detection
• See also: A hierarchy of semidefinite tests detects every entangled state
• See also: How powerful are two unentangled quantum proofs?

Sources

• Classical deterministic complexity of Edmonds' problem and quantum entanglement. L. Gurvits, 2003.
• Strong NP-hardness of the quantum separability problem. S. Gharibian, 2008.

Checked 2026-10-30.