Effective separability criteria

Deciding whether a bipartite mixed state is separable is fundamental but hard. PPT is necessary and sufficient for arbitrary states only in $2\times2$ and $2\times3$; higher dimensions admit PPT entanglement.

What is known: Appropriate weak-membership promise versions of separability are NP-hard; the norm, gap and input encoding matter. The Doherty–Parrilo–Spedalieri symmetric-extension hierarchy converges to the separable set, with SDP cost increasing with dimension and level. Realignment, covariance-matrix criteria and witnesses provide useful one-sided tests. Low-rank and symmetric families admit stronger results. For Gaussian states, PPT is sufficient in one-mode-versus-many-mode and certain symmetric settings, but not in arbitrary bipartite mode configurations: Gaussian bound-entangled states exist.

Preprint progress (July 2026): Malavolta claims a randomized polynomial-time algorithm distinguishing separable density matrices from those at least a fixed constant $\eta>0$ from the separable set in Euclidean norm. The theorem's promise is essential: it does not give exact membership, vanishing-gap or arbitrary trace-distance tractability.

The incremental target is a quantitative map of specified tractable families and certified hierarchy levels as functions of dimension and requested accuracy, rather than an undefined “maximal tractable class”.

Source disclosures

Malavolta attributes the main idea to himself with Michael Walter's feedback, and reports ChatGPT 5.5/5.6 assistance on technical reduction proofs. He states that he wrote the final manuscript and takes responsibility. Source

Source catalogue review: 4 September 2026. Improved indicates partial progress, including qualified preprint claims.

preprint: Randomized polynomial-time separability testing with a fixed constant Euclidean-distance promise gap; not exact or arbitrary-norm membership. Evidence