Dvoretzky’s theorem and the complexity of entanglement detection

- Institut Camille Jordan, Université Claude Bernard Lyon 1
- More about Guillaume Aubrun

- Mathematics, Case Western Reserve University and Université Pierre et Marie Curie
- More about Stanislaw Szarek

*Discrete Analysis*, January. https://doi.org/10.19086/da.1242.

### Editorial introduction

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 ρ:H→H such that tr(ρ)=1 and tr(ρP)≥0 for every orthogonal projection P. A linear operator satisfying just the second condition is called *positive*. If H=H1⊗H2 then an important piece of information about ρ is the extent to which it can be split up into a part that acts on H1 and a part that acts on H2. An appropriate formal definition is the following: we say that ρ is *separable* if it can be approximated in the trace-class norm by operators of the form ∑iciρ1i⊗ρ2i, where each ρ1i is a state on H1, each ρ2i is a state on H2, and the ci 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 Φ is a linear map from operators to operators that takes positive operators to positive operators, and if ρ is separable, then (Φ⊗I)ρ is a positive operator: that is simply because (Φ⊗I)(∑iciρ1i⊗ρ2i)=∑iciΦρ1i⊗ρ2i and each Φρ1i is positive. Interestingly, however, the converse is true: if ρ is entangled, then there exists a positive Φ such that (Φ⊗I)(ρ) is *not* positive. This equivalence is called the *Horodecki criterion* for entanglement.

The Horodecki criterion gives us a witness Φ for each entangled state ρ. 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 H1 and H2). 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(cd3/logd).

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 Φ 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.