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

### 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 \(\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.