[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).

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Both source and target problems are missing from the codebase
Non-trivial	⚠️ Warn	Reduction is non-trivial in principle, but algorithm is a literature sketch, not an implementable procedure
Correctness	⚠️ Warn	Primary reference (Gharibian 2010) is verified and supports the claims; secondary reference (Gurvits 2003) attribution is slightly inaccurate
Well-written	❌ Fail	Multiple template deficiencies: vague overhead entries, incomplete algorithm, notation issues, weak example

Overall: 0 passed, 3 warnings, 1 failed

---

Usefulness

Neither RobustSemidefiniteFeasibility nor MixedEntanglementSeparability exist in the codebase. Running pred show on both returns "Unknown problem." This means two new [Model] issues must be filed and implemented before this reduction rule can be added. Since there is no existing path (both endpoints are missing), the reduction is novel in principle, but its practical usefulness cannot be evaluated until the models exist.

Warning: Both source and target models must be implemented first. Please file [Model] issues for both RobustSemidefiniteFeasibility and MixedEntanglementSeparability before this rule can proceed.

Non-trivial

The reduction involves genuine structural transformation: constructing a block matrix C from the RSDF matrices B_i, mapping the quartic optimization problem to a weak optimization over the set of separable states, and then using a convex-body oracle reduction (WOPT to WMEM). This is a multi-step construction with non-trivial parameter relationships (M = k + 1, N = l(l-1)/2 + 1), so it is not a trivial relabeling or subtype coercion.

However, the algorithm as written is a literature-level sketch rather than a step-by-step implementable procedure (see Well-written section below).

Correctness

Reference 1: Gharibian (2010) — VERIFIED

• Paper: "Strong NP-Hardness of the Quantum Separability Problem" (arXiv:0810.4507, published in Quantum Information & Computation 10(3):343-360, 2010)
• The paper does define RSDF in Definition 2, and Eq. (3) presents the reduction chain CLIQUE ≤_m RSDF ≤_m WOPT_ε(S_{M,N}) ≤_T WMEM_β(S_{M,N}).
• Lemma 4 establishes the many-one reduction from RSDF to WOPT with dimensions M = k+1, N = l(l-1)/2 + 1. This matches the issue's claims.
• Definitions 3 and 4 define WOPT and WMEM respectively. All cross-references check out.

Reference 2: Gurvits (2003) — PARTIALLY CORRECT

• Paper: "Classical deterministic complexity of Edmonds' problem and Quantum Entanglement" (arXiv:quant-ph/0303055, STOC 2003)
• The paper proves NP-hardness of the weak membership problem for separable states, but at inverse-exponential distance (not inverse-polynomial).
• The issue states Gurvits uses "RSDF as intermediate source for separability hardness" — this is inaccurate. Gurvits did not define or use RSDF. It was Gharibian who introduced RSDF as the intermediate problem to strengthen Gurvits's result to inverse-polynomial distance.
• The citation is not wrong per se (Gurvits's work is foundational to this line), but the parenthetical description is misleading.

Well-written

4a: Information Completeness — Issues found:

Section	Status	Issue
Source	Present	OK
Target	Present	OK
Motivation	Present but thin	Only says "key bridge" — does not explain why this path matters for this codebase or what downstream reductions it enables
Reference	Present	OK (2 citations)
Reduction Algorithm	Present but incomplete	Literature sketch, not step-by-step implementable (see 4b)
Size Overhead	Present but vague	Two entries say "polynomial in ..." without concrete formulas (see below)
Validation Method	Present	OK
Example	Present but weak	Insufficiently worked (see 4d)

4b: Algorithm Completeness — FAIL

The reduction algorithm describes the structure of the reduction chain (RSDF → WOPT → WMEM) but does not provide a step-by-step procedure a programmer could implement:

1. Step 1 says "Construct (c, gamma, epsilon) and dimensions (M, N) from the RSDF instance in polynomial time" but never specifies how to construct c, gamma, or epsilon. These are the core of the reduction.
2. Step 2 says "Use the standard convex-optimization oracle reduction" without specifying which algorithm (e.g., the ellipsoid method, a specific cutting-plane method) or its parameters.
3. The "Key parameter relationships" section gives M and N but omits the construction of the actual objective vector c and error parameters.

A programmer reading this cannot implement the reduction without going back to the original paper and reverse-engineering the construction.

4c: Symbol and Notation Consistency — Issues found:

• The overhead table uses dim_a and dim_b as code metric names, but these are not established as getter methods on any existing target problem (since MixedEntanglementSeparability does not exist yet). This cannot be validated.
• num_oracle_calls and bit_size in the overhead table are described as "polynomial in RSDF input size" and "polynomial in lk + sum_i <B_i> + <zeta> + <eta>" — these are not concrete formulas. Overhead expressions must be symbolic expressions using source problem getter methods (e.g., "k + 1", "l * (l - 1) / 2 + 1"), not prose descriptions.
• The notation <B_i> (presumably bit-size of B_i) is used without definition.

4d: Example Quality — FAIL

The example is too thin:

• It provides source dimensions and matrices, which is good.
• However, the "mapped target" section just says "the many-one mapping outputs (c, gamma, epsilon) for WOPT_epsilon(S_{3,2})" — it does not actually show what c, gamma, and epsilon are. This makes the example impossible to verify by hand.
• There is no explicit target instance that could be fed to pred solve or verified independently.
• The example should show the full constructed target problem, not just the dimensions.

Recommendations

• File [Model] issues for both RobustSemidefiniteFeasibility and MixedEntanglementSeparability first, defining their schemas, getter methods, and Problem trait implementations. The overhead table metric names must match the target model's actual getters.
• Expand the reduction algorithm with the explicit construction of c from the block matrix C (as described in Gharibian's Lemma 4), and specify the error parameter choices.
• Replace the vague "polynomial in ..." overhead entries with concrete symbolic expressions, or remove them if they cannot be expressed symbolically.
• Fully work the example: show the constructed block matrix C, the objective vector c, and the resulting WOPT/WMEM instance with explicit numeric values.
• Correct the Gurvits (2003) citation description: Gurvits proved NP-hardness at inverse-exponential distance; it was Gharibian who introduced RSDF and strengthened the result.
• Note: The Turing reduction step (WOPT → WMEM) may be difficult to implement as a pure ReduceTo trait implementation, since it requires multiple oracle calls rather than a single problem transformation. Consider whether this reduction fits the codebase's ReduceTo pattern, or if only the many-one part (RSDF → WOPT) should be implemented.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Both source and target problems do not exist in the codebase
Non-trivial	✅ Pass	Genuine structural transformation with gadget construction
Correctness	⚠️ Warn	References verified, but one citation is slightly misleading
Well-written	❌ Fail	Multiple template sections incomplete or vague; algorithm not implementable

Overall: 1 passed, 2 warnings, 1 failed

---

Usefulness

Neither RobustSemidefiniteFeasibility nor MixedEntanglementSeparability exists in the reduction graph. Running pred show on both names returns no results. This means the rule cannot be implemented until both model issues are resolved first. As a novel reduction with no existing path, this passes on novelty but earns a warning because both endpoint problems are missing — this rule is currently unimplementable.

Non-trivial

Pass. The reduction involves genuine structural transformation:

• Constructing block matrices A_i from RSDF matrices B_i with specific embedding into higher-dimensional space
• Mapping promise gap parameters (zeta, eta) to weak optimization error parameters (gamma, epsilon)
• A Turing reduction layer converting weak optimization to weak membership via convex optimization oracle reduction
• Non-trivial dimension calculations: M = k + 1, N = l(l-1)/2 + 1

This is not a variable substitution, subtype coercion, or identity mapping.

Correctness

References verified with caveats:

1. Gharibian (2009/2018), arxiv:0810.4507 — Confirmed. The paper is titled "Strong NP-Hardness of the Quantum Separability Problem" by Sevag Gharibian, published in Quantum Information & Computation (2010). The paper:

   • Defines RSDF in Definition 2 with the exact g(B_1,...,B_k) formula cited in the issue
   • Lemma 4 provides the many-one reduction RSDF → WOPT with dimensions M = k+1, N = l(l-1)/2 + 1 — matching the issue
   • Equation (3) shows the full chain: CLIQUE ≤_m RSDF ≤_m WOPT ≤_T WMEM — matching the issue's structure
   • Definitions 3 and 4 define WOPT and WMEM respectively

2. Gurvits (2003), arxiv:quant-ph/0303055 — Confirmed as a real paper: "Classical deterministic complexity of Edmonds' problem and Quantum Entanglement" by Leonid Gurvits, STOC 2003. However, the issue's citation claim is slightly misleading: the issue says "RSDF used as intermediate source for separability hardness" citing Gurvits. The RSDF formulation with that specific name and the g(B_1,...,B_k) definition comes from Gharibian's paper (Def. 2), not Gurvits. Gurvits established the original (weaker) NP-hardness of separability testing. This is not incorrect enough to fail, but the attribution should be clarified.

No contradictions found with the project knowledge base or references.md.

Well-written

Fail. Several significant issues:

4a: Information Completeness

The issue is missing key sections or has incomplete content:

• Size Overhead table: Two rows use vague "polynomial in ..." descriptions instead of concrete formulas. The num_oracle_calls row says "polynomial in RSDF input size" and bit_size says "polynomial in lk + ...". These are not implementable overhead expressions — the codebase requires concrete symbolic expressions for the #[reduction(overhead = {...})] macro.

4b: Algorithm Completeness

The reduction algorithm is a high-level sketch, not an implementable procedure:

• Step 1 says "Construct (c, gamma, epsilon) and dimensions (M, N) from the RSDF instance in polynomial time" but does NOT specify how to construct c, gamma, or epsilon. What are the actual formulas?
• Step 2 references "the standard convex-optimization oracle reduction" without specifying which algorithm (ellipsoid method? Grotschel-Lovasz-Schrijver?). A programmer cannot implement "use the standard reduction."
• The note about A_i matrices mentions "upper-left l x l subblock is set to B_i" but does not give the complete construction of the block matrix C.
• The reduction is described as a Turing reduction (multiple oracle calls), which is fundamentally different from the many-one reductions this codebase implements via ReduceTo<T>. The trait requires a single reduce_to() call returning one target instance, but this reduction requires polynomially many calls to a WMEM oracle. This is a structural mismatch with the codebase's reduction framework.

4c: Symbol and Notation Consistency

• The symbol c appears in "Construct (c, gamma, epsilon)" but is never defined — what is c?
• The overhead table uses dim_a and dim_b as code metric names, but these are assumed target getter method names without verification (no target problem exists yet to confirm)
• <B_i> notation in the bit_size formula uses angle brackets that could mean "size of" or "encoding length" — ambiguous

4d: Example Quality

• The example is minimal (l=2, k=2) which is acceptable for size, but it only shows the source instance and the mapped dimensions — it does NOT show the actual constructed target instance (the values of c, gamma, epsilon, or the density matrix). The example says "the many-one mapping outputs (c, gamma, epsilon) for WOPT" without computing them. This is not a fully worked example.

Additional Concern: Turing vs Many-One

The reduction chain includes a Turing reduction step (WOPT ≤_T WMEM), meaning the overall reduction is a Turing reduction, not a many-one reduction. The codebase's ReduceTo<T> trait implements many-one reductions (one source instance maps to one target instance). A Turing reduction (multiple oracle queries) cannot be directly expressed with this trait. This is a fundamental design concern that should be addressed in the issue.

Recommendations

• Specify the complete construction of c, gamma, epsilon from Lemma 4 of Gharibian's paper
• Clarify the Gurvits citation — attribute RSDF to Gharibian, not Gurvits
• Address the Turing reduction concern: either reformulate as a many-one reduction (RSDF → WOPT only) or explain how the oracle reduction layer would be handled
• Provide concrete overhead formulas, not "polynomial in ..."
• Complete the worked example with actual computed values

[GiggleLiu]

Closing as part of batch cleanup.