On polyhedral approximations of the positive semidefinite cone

11/23/2018
by   Hamza Fawzi, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset