[Model] MixedEntanglementSeparability

[QingyunQian]

Motivation

Add the mixed-state entanglement separability decision problem, a central problem in quantum information and a canonical NP-hard weak-membership problem over a convex set.

Definition

Name: MixedEntanglementSeparability
Reference:

• Gurvits, L. (2003). Classical deterministic complexity of Edmonds' problem and Quantum Entanglement.
• Gharibian, S. (2009/2018). Strong NP-Hardness of the Quantum Separability Problem.

Let rho be a bipartite density matrix on C^M ⊗ C^N (rho >= 0, Tr(rho)=1).

rho is separable iff it can be written as:

rho = sum_t p_t (|a_t><a_t| ⊗ |b_t><b_t|),

where p_t >= 0, sum_t p_t = 1.

Because exact boundary membership is numerically ill-posed, we use the weak-membership promise version:

• YES: rho is at least beta inside the separable set
• NO: rho is at least beta outside the separable set

(beta > 0; points within the margin are promise-gap inputs.)

Variables

• Count: decomposition-size dependent, continuous (not fixed finite discrete variables)
• Per-variable domain: real probabilities and complex amplitudes (or equivalent real Bloch coordinates)
• Meaning: candidate separable decomposition parameters (p_t, a_t, b_t) or equivalent convex-combination coordinates
• Constraint: PSD/trace constraints for rho, and convex-combination constraints for decomposition

Schema (data type)

Type name: MixedEntanglementSeparability
Variants: subsystem dimensions (M, N) and real/complex representation

Field	Type	Description
rho	Vec<Vec<Complex64>> (or split real/imag parts as two Vec<Vec<f64>>)	Input density matrix on C^M ⊗ C^N
dim_a	usize	Subsystem dimension M
dim_b	usize	Subsystem dimension N
beta	f64	Weak-membership promise margin

Complexity

• Best known exact algorithm: no known polynomial-time exact algorithm for general instances
• Complexity class: NP-hard (weak membership formulation), strongly NP-hard for inverse-polynomial margin
• References:
  • Gurvits (2003): NP-hardness of weak membership near boundary with inverse-exponential margin (beta <= 1/exp(M,N))
  • Gharibian (2009/2018): strong NP-hardness with inverse-polynomial promise margin (beta <= 1/poly(M,N))

Extra Remark

• This problem is a geometric convex-membership problem over the separable set S_{M,N}.
• RSDF is an important intermediate source problem in hardness chains leading to this model.
• Practical solvers often rely on relaxations/certificates (e.g., PPT criterion, entanglement witnesses, SDP hierarchies), which are incomplete in general.

How to solve

• It can be solved by (existing) bruteforce.
• Other, refer to convex relaxation / SDP hierarchies / entanglement-witness methods.

Example Instance

Instance 1: Separable (YES)

M = N = 2
rho = 0.5 * (|00><00| + |11><11|)

This is explicitly separable as a convex combination of product pure states.

Instance 2: Entangled (NO, for sufficiently small beta)

M = N = 2
|Phi+> = (|00> + |11>) / sqrt(2)
rho = |Phi+><Phi+|

rho is a Bell state (entangled), hence not separable.

Note: these two examples are sanity-check instances. The NP-hard regime is reached for highly mixed states near the separable-set boundary (e.g., parameterized Werner/isotropic families or bound-entangled constructions).

Validation Method

• Cross-check small-dimensional cases with known criteria (PPT is necessary and sufficient for 2x2 and 2x3)
• Compare with SDP-based outer/inner approximations of the separable set
• Verify known benchmark states (Bell, isotropic, Werner families) at parameter values with known separability thresholds