It is well known that state-of-the-art linear programming solvers are more efficient than their semidefinite programming counterparts and can scale to much larger problem sizes. This leads us to consider the question, how well can we approximate semidefinite programs with linear programs? In this paper, we prove lower bounds on the size of linear programs that approximate the positive semidefinite cone. Let D be the set of n × n positive semidefinite matrices of trace equal to one. We prove two results on the hardness of approximating D with polytopes. We show that if 0 < ε < 1and A is an arbitrary matrix of trace equal to one, any polytope P such that (1-ε) (D-A) ⊂ P ⊂ D-A must have linear programming extension complexity at least [Formula: see text], where c > 0 is a constant that depends on ε. Second, we show that any polytope P such that D ⊂ P and such that the Gaussian width of P is at most twice the Gaussian width of D must have extension complexity at least [Formula: see text]. Our bounds are both superpolynomial in n and demonstrate that there is no generic way of approximating semidefinite programs with compact linear programs. The main ingredient of our proofs is hypercontractivity of the noise operator on the hypercube.
In combinatorial optimization, many problems can be modeled by optimizing a linear functional over a polytope. The standard tool to manage such a problem is the well-known linear programming. But on this occasion, linear programming reaches its limits for example for the family of the correlation polytopes CORRn (n ϵ IN), that forms a very important family of polytopes in combinatorial optimization, because the number of facets of any polytope that maps linearly onto CORRn grows exponentially in n. The question rises whether semidefinite programming, a broad generalization of linear programming, can provide relief. The feasible set of a semidefinite program (SDP) is a so-called spectrahedron, the solution set of a linear matrix inequality (LMI). Instead of the number of facets of the polytope in the case of a linear program, the size of the LMI defining the spectrahedron is a measure for the complexity of the SDP. In their breakthrough work, Lee, Raghavendra and Steurer [LRS] negated 2015 this question. They proved a super-polynomial lower bound in n on the size of any LMI defining any spectrahedron that linearly maps onto CORRn
A fundamental problem in quantum coding theory is to determine the maximum size of quantum codes of given block length and distance. A recent work introduced bounds based on semidefinite programming, strengthening the well-known quantum linear programming bounds. However, floating-point inaccuracies prevent the extraction of rigorous non-existence proofs from the numerical methods. Here, we address this by providing rational infeasibility certificates for a range of quantum codes. Using a clustered low-rank solver with heuristic rounding to algebraic expressions, we can improve upon
18 upper bounds on the maximum size of
n-qubit codes with
6≤n≤19. Our work highlights the practicality and scalability of semidefinite programming for quantum coding bounds.
We prove quantitative lower bounds on the semidefinite extension complexity of the set of separable quantum states on
Cd⊗Cd. 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.