[Rule] RSDF to MixedEntanglementSeparability

[QingyunQian]

Source: RobustSemidefiniteFeasibility (RSDF)
Target: MixedEntanglementSeparability (Weak Membership over separable states)
Motivation: This is the key bridge from matrix quartic optimization to quantum separability; it is the reduction step used in modern strong NP-hardness chains for separability.
Reference:

• Gharibian, S. (2009/2018). Strong NP-Hardness of the Quantum Separability Problem. (Eq. (3), Def. 2-4, Lemma 4)
• Gurvits, L. (2003). Classical deterministic complexity of Edmonds' problem and Quantum Entanglement. (RSDF used as intermediate source for separability hardness)

Reduction Algorithm

Notation:

• Source RSDF instance: (k, l, B_1, ..., B_k, zeta, eta) with

g(B_1,...,B_k) = max_{x in R^l, ||x||_2=1} sum_{i=1}^k (x^T B_i x)^2.

Promise:

• YES if g >= zeta + eta

• NO if g <= zeta - eta

• Target separability set: S_{M,N} (Bloch-vector representation of separable bipartite states)

• Target decision oracle: weak-membership WMEM_beta(S_{M,N})

Reduction structure (literature chain):

1. Many-one mapping (RSDF -> WOPT over separable set):
   Construct (c, gamma, epsilon) and dimensions (M, N) from the RSDF instance in polynomial time such that:

RSDF YES  => WOPT_epsilon(S_{M,N}) YES
RSDF NO   => WOPT_epsilon(S_{M,N}) NO.

1. Polynomial-time Turing reduction (WOPT -> WMEM):
   Use the standard convex-optimization oracle reduction to obtain a polynomial number of calls to WMEM_beta(S_{M,N}):

WOPT_epsilon(S_{M,N}) <=T WMEM_beta(S_{M,N}).

1. Composition:
   Combining (1) and (2):

RSDF <=m WOPT_epsilon(S_{M,N}) <=T WMEM_beta(S_{M,N}).

This yields a valid polynomial-time reduction from RSDF to MixedEntanglementSeparability (weak-membership form).

Key parameter relationships (from cited construction):

• M = k + 1
• N = l(l - 1)/2 + 1
  (Note: each A_i in the block matrix C is an N × N symmetric matrix whose upper-left l × l subblock is set to B_i, with all other entries zero. The embedding dimension N is larger than the original matrix dimension l.)
• Error parameters are chosen inverse-polynomially in input size, preserving promise separation.

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
dim_a (M)	k + 1
dim_b (N)	l(l - 1)/2 + 1
num_oracle_calls to WMEM_beta	polynomial in RSDF input size
bit_size of mapped parameters	polynomial in lk + sum_i <B_i> + <zeta> + <eta>

Validation Method

• For small RSDF instances, numerically estimate g and verify YES/NO promise side
• Build mapped (c, gamma, epsilon) and check consistency with WOPT-side inequalities
• Use a separability oracle/relaxation (e.g., PPT + SDP hierarchy on small dimensions) as a sanity proxy for WMEM behavior
• Verify that mapped parameters satisfy inverse-polynomial error bounds required by the reduction

Example

Source RSDF instance (toy):

l = 2, k = 2
B_1 = [[1, 0], [0, 0]]
B_2 = [[0, 0], [0, 1]]
zeta = 0.95, eta = 0.02

Here g = 1, so this is a YES-side RSDF instance (1 >= 0.97).

Mapped target dimensions (from the reduction formulas):

M = k + 1 = 3
N = l(l - 1)/2 + 1 = 2

Then the many-one mapping outputs (c, gamma, epsilon) for WOPT_epsilon(S_{3,2}), and the Turing layer queries WMEM_beta(S_{3,2}), which is equivalent to MixedEntanglementSeparability(YES).