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

• URL: http://arxiv.org/abs/2609.09033v1
• Date: Tue, 08 Sep 2026 17:00:11 GMT
• Title: Semidefinite extension complexity of the separable set, with applications to approximate disentanglers
• Abstract summary: We consider semidefinite programs that approximate the maximum acceptance probability of a measurement over separable states.<n>Our proof combines the quantitative pseudo-density theorem of Lee, Raghavendra, and Steurer with explicit block-positive operators and Chebyshev amplification.
• Score: 0.6117371161379209
• License: http://creativecommons.org/licenses/by/4.0/
• 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<θ<2/7$, there are constants $c_θ,a_θ>0$ such that, for sufficiently large $d$, any such SDP with uniform additive error $0<a\le a_θ$ has size at least $d^{c_θ\min\{a^{-1/3},d^θ\}}$. The bound applies at sufficiently small constant error, is superpolynomial in $d$ whenever $a=o(1)$, and becomes $d^{Ω(d^θ)}$ when $a\le d^{-3θ}$, 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.

Related papers

• The I3322 quantum value is attained spatially but not in finite dimension [0.0]
  Let $S$ be the quantum supremum of the $I_3322$ Bell functional in the Collins-Gisin normalization (classical bound 0; two-qubit maximum exactly 1/4)<n>We prove: (i) no finite-dimensional quantum strategy attains $S$ -- any finite local dimensions, pure or mixed states, projective or POVM measurements -- proving Pal and Vertesi (2010)<n>We also determine the dimension complexity: with $S_d$ the optimum at local dimension $le d$ and $D()=mind:S-S_d
  arXiv  Detail & Related papers  (2026-09-03T15:48:01Z)
• Deterministic Minimum-Output-Entropy Nonadditivity via Haagerup's Inequality and Near-Free Permutation Representations [6.9022592726569085]
  We give a realization of the finite-dimensional quadratic certificate underlying Collins's mixed-unitary proof of minimum-output-entropy nonadditivity.
  arXiv  Detail & Related papers  (2026-08-31T16:53:42Z)
• Uniform Statistical Convergence of Empirical Sinkhorn Potentials with Exponential and Polynomial Dependence on the Regularization Parameter [3.6552781109515853]
  We study the empirical Sinkhorn estimator of the entropic optimal transport potentials under the uniform loss.<n>For a fixed regularization parameter $varepsilon>0$, we establish a non-asymptotic statistical rate of $n-1/2$.<n>Key requirement is a residual-stability estimate for the population Sinkhorn map.
  arXiv  Detail & Related papers  (2026-08-29T08:59:00Z)
• Quantum Change Interval: Exact Asymptotics for Minimum Error Localization [8.906035369693457]
  We study a returning quantum change interval in which a source emits $lvertrangle$ over one interval and $lvert0rangle$ elsewhere.<n>We analyze the matrix using Toeplitz comparison and Flner transfer, together with an exact decomposition by excitation number and interval hull.
  arXiv  Detail & Related papers  (2026-08-25T13:30:26Z)
• Research Report on Noise-Shaped One-Bit Coefficients in Discrete Polynomial Fourier Extension [0.0]
  This report studies noise-shaped one-bit coefficients in normalized discrete Fourier extension.<n>For first-order Sigma- quantization, the error is written as $e_k=u_k-q_k=v_k$ with a uniformly bounded state.<n>For the parabolic $_x,t()=x+t2$, the bound is expressed through $J(x,t)=int_01 |x+2t|d$, and the uniform $N-1$ rate is shown to be sharp.
  arXiv  Detail & Related papers  (2026-07-26T21:51:41Z)
• Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
  For singleton queries, Chamfer becomes maximum inner product similarity (MAX-IP)<n>For every fixed $in(0,1)$, there are constants $A_,c_>0$.<n>Unit-sphere MAX-IP matrix is an exact two-valued affine image of the DNF pattern matrix with gap of at least $8$.
  arXiv  Detail & Related papers  (2026-07-22T17:27:20Z)
• No Finite NPA Level Characterizes the Complete Quantum Set in the Simplest Bell Scenario [0.0]
  We show that emphno finite level is exact.<n>Every standard NPA relaxation based on a fixed finite list of words in the measurement projectors strictly contains the complete quantum set.
  arXiv  Detail & Related papers  (2026-07-16T04:52:11Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  We prove optimal sampling bounds achieving $(1pmvarepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions.<n>This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples.
  arXiv  Detail & Related papers  (2026-05-22T15:05:33Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  We study the estimation of relative entropy $D(rho|sigma)$ when $sigma$ is known.<n>Our estimator attains the Cram'er-Rao type bound when the dimension $d$ is fixed.
  arXiv  Detail & Related papers  (2024-06-25T06:07:20Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP) We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
  arXiv  Detail & Related papers  (2022-12-01T15:57:58Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.