Dvoretzky's theorem and the complexity of entanglement detection

Dvoretzky's theorem and the complexity of entanglement detection, Discrete Analysis 2017:1, 20 pp. Let $H$ be a Hilbert space. A _state_ on $H$ is a linear operator $\rho:H\to H$ such that tr$(\rho)=1$ and tr$(\rho P)\geq 0$ for every orthogonal projection $P$. A linear operator satisfying just the second condition is called _positive_. If $H=H_1\otimes H_2$ then an important piece of information about $\rho$ is the extent to which it can be split up into a part that acts on $H_1$ and a part that acts on $H_2$. An appropriate formal definition is the following: we say that $\rho$ is _separable_ if it can be approximated in the trace-class norm by operators of the form $\sum_ic_i\rho^1_i\otimes\rho^2_i$, where each $\rho^1_i$ is a state on $H_1$, each $\rho^2_i$ is a state on $H_2$, and the $c_i$ are positive constants. An operator that is not separable is called _entangled_. Owing to the importance of entanglement, it is useful to have a criterion that detects it. A simple necessary condition is that if $\Phi$ is a linear map from operators to operators that takes positive operators to positive operators, and if $\rho$ is separable, then $(\Phi\otimes I)\rho$ is a positive operator: that is simply because $(\Phi\otimes I)(\sum_ic_i\rho^1_i\otimes\rho^2_i)=\sum_ic_i\Phi\rho^1_i\otimes\rho^2_i$ and each $\Phi\rho^1_i$ is positive. Interestingly, however, the converse is true: if $\rho$ is entangled, then there exists a positive $\Phi$ such that $(\Phi\otimes I)(\rho)$ is _not_ positive. This equivalence is called the _Horodecki criterion_ for entanglement. The Horodecki criterion gives us a witness $\Phi$ for each entangled state $\rho$. The starting question for this paper is how many different witnesses one needs to detect all entangled states (as a function of the dimensions of $H_1$ and $H_2$). More precisely, since this number is known to be infinite, the paper considers the stronger notion of _robustly_ entangled states, which are states that remain entangled even when you average them with a suitable multiple of the identity. The main result of the paper is that the number needed is large: the authors obtain a bound of $\exp(cd^3/\log d)$. A key observation that enables them to prove this is that there is a resemblance between the problem they are considering and a result from a famous paper of Figiel, Lindenstrauss and Milman concerning Dvoretzky's theorem [1]. It follows from the analysis in the FLM paper that the product of the logarithm of the number of faces of a symmetric convex body with the logarithm of the number of vertices has to be at least $cn$, so it is not possible for a symmetric convex body to have few faces and few vertices (in strong contrast with a general convex body, since an $n$-dimensional simplex has $n+1$ of each). Something like that occurs here. Roughly speaking, the set of separable states can be regarded as having "few" extreme points, and therefore "many" faces. A single witness $\Phi$ cannot help with too many faces, so the number of witnesses needed must be large. These interesting ideas are new to the field of quantum information. [1] T. Figiel, J. Lindenstrauss and V. D. Milman, _The dimension of almost spherical sections of convex bodies,_ Acta Math. 139 (1-2) (1977), pp. 53-94.