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.