[Model] RSDF

[QingyunQian]

Motivation

Add Robust Semidefinite Feasibility (RSDF), a promise decision problem that is a standard bridge in hardness proofs for quantum separability and weak-membership problems over separable states.

Definition

Name: RobustSemidefiniteFeasibility (RSDF)
Reference:

• Gharibian, S. (2009/2018). "Strong NP-Hardness of the Quantum Separability Problem."
• [Gurvits, L. & Ioannou, L. M. (as cited in Gharibian, Theorem 2): CLIQUE <=m RSDF.]

Given:

• k rational symmetric matrices B_1, ..., B_k in Q^(l x l),
• rational thresholds zeta, eta >= 0,

define

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

Promise decision version:

• output YES if g(B_1,...,B_k) >= zeta + eta
• output NO if g(B_1,...,B_k) <= zeta - eta

Inputs in the gap zeta - eta < g < zeta + eta are outside the promise (either output is acceptable).

Variables

• Count: l real variables (one per coordinate of x)
• Per-variable domain: real numbers, with global constraint ||x||_2 = 1
• Meaning: config[i] = x_i, where x is the unit vector maximizing the quartic objective
• Constraint: unit-sphere feasibility (sum_i x_i^2 = 1)

Schema (data type)

Type name: RobustSemidefiniteFeasibility
Variants: real-valued matrices (f64) and rational-like encoded inputs

Field	Type	Description
matrices	Vec<Vec<Vec<f64>>>	The k symmetric matrices B_i of size l x l
zeta	f64	Center threshold zeta in promise condition
eta	f64	Promise gap half-width eta >= 0

Complexity

• Best known exact algorithm: global optimization of a quartic form on the sphere; exhaustive epsilon-net search takes (1/epsilon)^O(l) evaluations (exponential in dimension l)
• Complexity class: NP-hard as a promise problem (via many-one reduction from CLIQUE to RSDF)
• Reference detail: Gharibian (Theorem 2) states CLIQUE <=m RSDF with k = n(n-1)/2, l = n, and inverse-polynomial promise gap

Extra Remark

• RSDF is a natural algebraic optimization/decision model over symmetric matrices, closely related to polynomial optimization on the unit sphere.
• In quantum complexity reductions, RSDF is used as an intermediate problem in chains such as:
  • CLIQUE <=m RSDF <=m WOPT(S_{M,N}) <=T WMEM(S_{M,N}).
• This makes RSDF useful as a reusable source problem for future reduction rules in this repository.

How to solve

• It can be solved by bruteforce.

Example Instance

YES instance

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

For x = (x1, x2) with x1^2 + x2^2 = 1:

g = max (x^T B_1 x)^2 + (x^T B_2 x)^2
  = max x1^4 + x2^4
  = 1

Since 1 >= zeta + eta = 0.97, output is YES.

NO instance

l = 2, k = 1
B_1 = [[0, 0],
       [0, 0]]
zeta = 0.3, eta = 0.1

Here g = 0, and 0 <= zeta - eta = 0.2, so output is NO.