Semidefinite extension complexity of the separable set, with applications to approximate disentanglers
Abstract
We prove quantitative lower bounds on the semidefinite extension complexity of the set of separable quantum states on ℂd⊗ℂ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≤ aθ has size at least dcθ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≤ 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
- Complexity Barriers to State Preparation in Quantum Approximate Optimization
- Verification Complexity and Extension of Classical Shadows
- Integrated gain-controlled semiconductor optical amplifier for input-power range extension in 100 Gb/s upstream PON receiver applications
- Complexity and Applications of Nearest Stabilizer Product State Problems
- Block entropy area based non-local fermionic mode optimization with gradient disentanglers
BibTeX
@misc{gharibian2026semidefinite,
title = {{Semidefinite extension complexity of the separable set, with applications to approximate disentanglers}},
author = {Sevag Gharibian and Carsten Hecht and Dorian Rudolph},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.09033},
eprint = {2609.09033},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09033},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Semidefinite extension complexity of the separable set, with applications to approximate disentanglers
AU - Sevag Gharibian
AU - Carsten Hecht
AU - Dorian Rudolph
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.09033
UR - https://arxiv.org/abs/2609.09033
AB - We prove quantitative lower bounds on the semidefinite extension complexity of the set of separable quantum states on ℂ^d⊗ℂ^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≤ 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≤ 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.
ER -