---
_id: '67088'
abstract:
- lang: eng
  text: 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.
author:
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
- first_name: Carsten
  full_name: Hecht, Carsten
  last_name: Hecht
- first_name: Dorian
  full_name: Rudolph, Dorian
  id: '57863'
  last_name: Rudolph
citation:
  ama: Gharibian S, Hecht C, Rudolph D. Semidefinite extension complexity of the separable
    set, with applications to approximate disentanglers. <i>arXiv:260909033</i>.
  apa: Gharibian, S., Hecht, C., &#38; Rudolph, D. (n.d.). Semidefinite extension
    complexity of the separable set, with applications to approximate disentanglers.
    In <i>arXiv:2609.09033</i>.
  bibtex: '@article{Gharibian_Hecht_Rudolph, title={Semidefinite extension complexity
    of the separable set, with applications to approximate disentanglers}, journal={arXiv:2609.09033},
    author={Gharibian, Sevag and Hecht, Carsten and Rudolph, Dorian} }'
  chicago: Gharibian, Sevag, Carsten Hecht, and Dorian Rudolph. “Semidefinite Extension
    Complexity of the Separable Set, with Applications to Approximate Disentanglers.”
    <i>ArXiv:2609.09033</i>, n.d.
  ieee: S. Gharibian, C. Hecht, and D. Rudolph, “Semidefinite extension complexity
    of the separable set, with applications to approximate disentanglers,” <i>arXiv:2609.09033</i>.
    .
  mla: Gharibian, Sevag, et al. “Semidefinite Extension Complexity of the Separable
    Set, with Applications to Approximate Disentanglers.” <i>ArXiv:2609.09033</i>.
  short: S. Gharibian, C. Hecht, D. Rudolph, ArXiv:2609.09033 (n.d.).
date_created: 2026-09-09T12:06:36Z
date_updated: 2026-09-09T12:07:31Z
external_id:
  arxiv:
  - '2609.09033'
language:
- iso: eng
publication: arXiv:2609.09033
publication_status: unpublished
status: public
title: Semidefinite extension complexity of the separable set, with applications to
  approximate disentanglers
type: preprint
user_id: '71541'
year: '2026'
...