  Let $D$ be the set of $n\times 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
< \epsilon < 1$ and $A$ is an arbitrary matrix of trace equal to one, any
polytope $P$ such that $(1-\epsilon)(D-A) \subset P \subset D-A$ must have
linear programming extension complexity at least $\exp(c\sqrt{n})$ where $c >
0$ is a constant that depends on $\epsilon$. Second, we show that any polytope
$P$ such that $D \subset P$ and such that the Gaussian width of $P$ is at most
twice the Gaussian width of $D$ must have extension complexity at least
$\exp(cn^{1/3})$. The main ingredient of our proofs is hypercontractivity of
the noise operator on the hypercube.
