Skip to content
Preprint

Semidefinite extension complexity of the separable set, with applications to approximate disentanglers

Sep 2026 · 0 citations · 30 references
Physics

Abstract

We prove quantitative lower bounds on the semidefinite extension complexity of the set of separable quantum states on $\mathbb{C}^d\otimes\mathbb{C}^d$. We consider semidefinite programs (SDPs) that approximate the maximum acceptance probability of a measurement over separable states, the optimization problem underlying QMA(2). In the extended-formulation model of Harrow, Natarajan, and Wu (HNW), all measurements share a common feasible region and an objective-independent embedding of product states that exactly reproduces their acceptance probabilities. For every $0<\theta<2/7$, there are constants $c_\theta,a_\theta>0$ such that, for sufficiently large $d$, any such SDP with uniform additive error $0<a\le a_\theta$ has size at least $d^{c_\theta\min\{a^{-1/3},d^\theta\}}$. The bound applies at sufficiently small constant error, is superpolynomial in $d$ whenever $a=o(1)$, and becomes $d^{\Omega(d^\theta)}$ when $a\le d^{-3\theta}$, improving HNW's quasipolynomial bound at inverse- square error. The same bound holds for any SDP-representable convex set of states that contains all separable states and lies within trace distance $a$ of them, giving a quantitative counterpart to Fawzi's theorem that the separable set has no exact semidefinite representation. Our proof combines the quantitative pseudo-density theorem of Lee, Raghavendra, and Steurer with explicit block-positive operators and Chebyshev amplification. Our main results are supported by Lean proofs.

View source

Similar papers

On the SoS Certifiability of Log-Concave Distributions

We prove that for every isotropic log-concave distribution $P$ on $\mathbb{R}^d$ and every even $m\ge2$, the polynomial $(Cm)^m\|v\|_2^m - \mathbb{E}_{X\sim P}\langle X,v\rangle^m$ is a sum of squares, where $C>0$ is a universal constant. This improves on the Poincar\'e-dependent bounds (Kothari and Steinhardt, 2017),...

A. Storozhenko · 1 citation
Preprint Sep 2026

Relative entropy representations via tracial joint spectral measures

We show that for positive semidefinite $A$ and $B$ the relative entropy can be written as $D(A\|B)=2\int a\log(a/b)\,\mathrm{d}\mu_{A,B}(a,b)$, where $\mu_{A,B}$ denotes Hein\"avaara's tracial joint spectral measure. This allows us to obtain a unified derivation of several known integral representations of relative ent...

Lukas Schmitt · 0 citations
Preprint Sep 2026

SparseStack Is an Optimal Oblivious Subspace Embedding

It is proved that fully independent SparseStack achieves the oblivious subspace embedding parameters conjectured by Nelson and Nguyen (FOCS 2013) and the main theorem has been formally verified in Lean 4.

Diar Heidary · 1 citation
Preprint Aug 2026

An independent proof of the even-dimensional S-matrix inequality

Harwit and Sloane conjectured that every nonsingular entrywise-nonnegative matrix $A\in\mathbb R^{n\times n}$ satisfies $\|A^{-1}\|_F\ge 2n(n+1)^{-1}\|A\|_{\max}^{-1}$, with equality precisely for positive multiples of $S$-matrices. Zhang has given a complete proof of this conjecture by a centered pseudoinverse and spe...

Yin-Jie Li · 0 citations
Preprint Aug 2026

Optimal Condition Numbers in Low-Rank Positive Semidefinite Matrix Sensing

In this paper we focus on the stability of positive semidefinite matrix sensing maps $\Phi_{\mathcal{A}}(X)=(\langle A_i,X\rangle)_{i=1}^m$ where $A_i\succeq 0$, $X\succeq0$ and $\operatorname{rank}(X)\le r$. We introduce the bi-Lipschitz constants of $\Phi_{\mathcal{A}}(X)$ and define the global condition numbers as t...

Mingxuan Sun, Zhi-Qiang Xu · 0 citations
#machine learning Preprint Oct 2026

Geometry-Dependent Approximation for Non-Monotone $k$-Submodular Maximization

We study nonnegative, non-monotone $k$-submodular maximization with $k\ge2$ labels under support constraints, and show how the certified approximation coefficient improves as the support region permits more uniform selection. For a compact convex down-closed support region $P\subseteq[0,1]^n$, the diagonal level $\zeta...

Vaneet Aggarwal · 3 citations · ⚡1

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.