[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

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	Incompatible with Problem trait; no solver path; orphan node
Non-trivial	✅ Pass	Genuinely distinct from all existing problems
Correctness	⚠️ Warn	References real but imprecise; no concrete complexity bound
Well-written	❌ Fail	Continuous domain, no discretization, trivial examples

Overall: 1 passed, 1 warning, 2 failed

---

Usefulness — FAIL

Critical architectural incompatibility. The Problem trait requires dims() -> Vec<usize> (finite discrete configuration space) and evaluate(&self, config: &[usize]) -> Metric. The issue explicitly states the domain is "decomposition-size dependent, continuous (not fixed finite discrete variables)" with "real probabilities and complex amplitudes." This fundamentally cannot implement the Problem trait without a discretization scheme, which the issue does not propose.

No brute-force solver path. The "How to solve" section unchecks brute-force and only mentions convex relaxation / SDP hierarchies. Without BruteForce::find_satisfying(), reduction rules cannot be verified via closed-loop testing.

Orphan node. No concrete reduction rules to/from existing problems are identified. Without at least one planned reduction, this would be an isolated node in the reduction graph.

Non-trivial

Genuinely distinct — involves density matrices, tensor product structure, and convex membership testing over the separable set. None of this overlaps with any existing problem.

Correctness

Reference	Status	Notes
Gurvits (2003), STOC	✅ Verified	"Classical deterministic complexity of Edmonds' problem and Quantum Entanglement", doi:10.1145/780542.780545. Proves NP-hardness of weak membership for the separable set.
Gharibian (2010), QIC Vol. 10	✅ Verified	arXiv:0810.4507. Strengthens to inverse-polynomial promise margin. Issue says "(2009/2018)" but the paper was submitted 2008, published 2010.

Missing: No concrete best-known algorithm time bound is provided. The declare_variants! macro requires a complexity string (e.g., "2^(dim_a * dim_b)").

Well-written — FAIL

• Variables section describes continuous domain incompatible with codebase — no discretization proposed
• Complexity section lacks a concrete algorithm time bound required for implementation
• Examples are trivial edge cases:
  • Example 1 (classical mixture) is trivially separable
  • Example 2 (Bell state) is trivially detected by PPT criterion
  • Neither exercises the NP-hard regime (highly mixed states near separability boundary)
  • Neither provides a quantitative β value for the weak-membership formulation
• Distance metric unspecified — the weak-membership formulation needs to state which norm defines "distance" from the separable set (trace distance is standard)

Required fixes

1. Propose a discretization scheme mapping the continuous domain to dims() / evaluate()
2. Add a concrete worst-case complexity bound for declare_variants!
3. Identify a brute-force solver approach (e.g., SDP hierarchy truncation at fixed level)
4. Provide a non-trivial example near the separability boundary (e.g., Werner state at critical parameter)
5. Specify the distance metric (trace norm) for weak membership
6. Plan at least one reduction rule connecting to existing problems

[zazabap]

@QingyunQian This is somehow considered orphan node. However, it might be quite unique for the physicist and people working on quantum entanglement. Temporarily add Useless issue but in fact it is carefully considered.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	Continuous problem incompatible with discrete Problem trait; no planned reductions
Non-trivial	✅ Pass	Genuinely distinct from all 24 existing problems
Correctness	✅ Pass	Both references verified on arxiv; complexity claims accurate
Well-written	❌ Fail	Missing complexity string, incompatible variable domain, incomplete template sections

Overall: 2 passed, 0 warnings, 2 failed

---

Usefulness

This problem cannot be implemented in the current framework. The core Problem trait requires:

• dims() -> Vec<usize> — a finite discrete configuration space where each variable has a fixed cardinality
• evaluate(&self, config: &[usize]) -> Metric — evaluation over integer-indexed configurations

The Mixed Entanglement Separability problem has continuous variables (probabilities, complex amplitudes, Bloch coordinates) with an unbounded decomposition size. The issue explicitly states: "Count: decomposition-size dependent, continuous (not fixed finite discrete variables)." This is fundamentally incompatible with the Problem trait.

Additionally, no reduction rules to or from existing problems are proposed. The issue mentions "RSDF is an important intermediate source problem" but RSDF is not in the codebase either, meaning this would be an orphan node in the reduction graph with no connections to any existing problem.

Non-trivial

Pass. This is a genuinely distinct problem — a convex membership decision problem over the set of separable quantum states. It has no mathematical equivalence to any of the 24 existing problems in the codebase (which are all combinatorial/discrete optimization or satisfaction problems).

Correctness

Pass. Both cited references are verified:

1. Gurvits (2003) — "Classical deterministic complexity of Edmonds' problem and Quantum Entanglement" (arxiv:quant-ph/0303055). Published at STOC 2003. The paper establishes the connection between Edmonds' problem and quantum entanglement, showing NP-hardness of the weak membership problem for the separable set with inverse-exponential margin. The issue's claim is accurate.

2. Gharibian (2009/2018) — "Strong NP-Hardness of the Quantum Separability Problem" (arxiv:0810.4507). Published in Quantum Information & Computation. The paper strengthens Gurvits' result to inverse-polynomial margin (strong NP-hardness). The issue's claim is accurate.

The complexity classification as NP-hard (weak membership formulation) is correctly stated.

Well-written

Multiple template deficiencies:

1. Variables section is incompatible: The issue honestly states the variables are "continuous (not fixed finite discrete variables)" — but this means the problem cannot implement dims() or evaluate(). This is not a writing issue per se, but a fundamental mismatch with the project's requirements.

2. Missing complexity string: The Complexity section says "no known polynomial-time exact algorithm for general instances" but does not provide a concrete worst-case time bound (e.g., "2^(M*N)" or similar) as required by declare_variants!. Without a concrete complexity expression, the problem cannot be registered in the reduction graph.

3. No brute-force solver path: The "How to solve" section has brute-force unchecked and only references SDP hierarchies / entanglement witnesses, which are approximate methods. Every problem in the codebase needs at least brute-force solvability for testing closed-loop reductions.

4. Schema incomplete: The schema uses Complex64 and Vec<Vec<...>> but the codebase does not have complex number support. No size_fields or getter methods are defined (needed for overhead expressions).

5. Example quality: The two examples are either trivially separable or trivially entangled (Bell state). As the issue itself notes, "the NP-hard regime is reached for highly mixed states near the separable-set boundary." The examples do not exercise the weak-membership promise gap (beta parameter) at all — they are sanity checks, not reduction-testable instances.

6. Missing "Name" conventions check: The name MixedEntanglementSeparability does not follow the project's naming pattern. Satisfaction problems in the codebase use names like Satisfiability, KSatisfiability. A decision problem about separability might be better named simply Separability or QuantumSeparability, but this is minor compared to the fundamental compatibility issues.

Recommendations

• This problem is better suited to a continuous optimization or SDP-based framework rather than a discrete combinatorial reduction library.
• If the goal is to connect quantum information problems to the reduction graph, consider instead a discretized or decision variant that can be encoded with finite binary variables (e.g., a matrix completion / constraint satisfaction encoding).
• Alternatively, if a future version of the library supports continuous problems, this issue could be revisited.