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