On polyhedral approximations of the positive semidefinite cone
share
Let D be the set of n× n positive semidefinite matrices of trace equal to one, also known as the set of density matrices. We prove two results on the hardness of approximating D with polytopes. First, we show that if 0 < ϵ < 1 and 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 (c√(n)) 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 (cn^1/3). The main ingredient of our proofs is hypercontractivity of the noise operator on the hypercube.
READ FULL TEXT