Tensor products of convex sets and the volume of separable states on N qudits

Guillaume Aubrun and Stanisław J. Szarek

Abstract

This note deals with estimating the volume of the set of separable mixed quantum states when the dimension of the state space grows to infinity. This has been studied recently for qubits; here we consider larger particles and conclude that, in all cases, the proportion of the states that are separable is super-exponentially small in the dimension of the set. We also show that the partial transpose criterion becomes imprecise when the dimension increases, and that the lower bound 6^{−N/2} on the (Hilbert-Schmidt) inradius of the set of separable states on N qubits obtained recently by Gurvits and Barnum is essentially optimal. We employ standard tools of classical convexity, high-dimensional probability and geometry of Banach spaces. One relatively non-standard point is a formal introduction of the concept of projective tensor products of convex bodies, and an initial study of this concept.

PACS numbers: 03.65.Ud, 03.67.Mn, 03.65.Db, 02.40.Ft

1 Introduction and summary of results

An important problem in quantum information theory is to estimate quantitatively parameters related to entanglement. This phenomenon is thought to be at the heart of quantum information processing while, on the other hand, its experimental creation and handling are still challenging. The set of separable (i.e., unentangled) states has been defined in [1] under the name “classically correlated,” as opposed to “EPRcorrelated” entangled states named so because of their role in the Einstein-Podolsky-Rosen paradox. The question of determining the volume of the set of separable states has been asked for example in [2, 3]; we refer the reader to these sources for background and for motivation. In this paper we obtain estimates which are meaningful when the dimension of the state space is “not too small,” and which are asymptotically tight as that dimension tends to infinity. The effective radius in the sense of volume of (that is, the radius of the Euclidean ball of the same volume as; also referred to as volume radius) the set of separable states for qubits has been determined (precisely on the scale of powers of the dimension) in [4]. Here we shall deal with more general particles, while using the same general approach via the methods of asymptotic convex geometry. The conclusion is that when the dimension of the state space is large, then all but extremely few (as measured by the standard volume) states are entangled; see Theorems 1 and 2 below for precise statements. As further application of our techniques we show the optimality (up to factors of lower order) of the lower bound on the radius of a Hilbert-Schmidt ball contained in the set of separable states on N qubits that was obtained recently by Gurvits and Barnum [5]. Still another consequence is that, for large dimensions, the set of states with positive partial transpose [6, 3] is, in the sense of the volume radius, much closer to the set of all states than to the set of separable states; in other words, the Peres partial transpose criterion becomes less and less precise as the dimension increases.

We now recall the mathematical framework and introduce some notation. The state space is a complex Hilbert space H = ℂ^{D_{1}} ⊗ ⋯ ⊗ ℂ^{D_{N}}. We write d = D_{1} … D_{N} for the dimension of H. This Hilbert space allows to describe quantum interactions between N particles; D_{j} = 2 corresponds to qubits and D_{j} = 3 to qutrits. We write B(H) for the space (or C^{∗}-algebra) of linear maps from H into itself, and B_{sa}(H) for the (real linear) subspace of self-adjoint operators. The space B(H) is endowed with the Hilbert-Schmidt, or Frobenius, scalar product defined by ⟨A, B⟩_{HS} := trA^{†}B ( = ∑_{i,j=1}^{d} \overline{A_{ij}}B_{ij} if A and B are represented as matrices). A state on B(H) (which we will abbreviate to “a state on H”) can be represented as a positive (semi-definite) trace one element of B_{sa}(H). A state is said to be separable if it can be written as a convex combination of tensor products of N states, otherwise it is called entangled. That is, the set of states (also called in this context density operators or density matrices) is

D = D(H) := {ρ ∈ B_{sa}(H), ρ ⩾ 0, trρ = 1},

and the set of separable states is

S = S(H) := conv{ρ_{1} ⊗ ⋯ ⊗ ρ_{N}, ρ_{j} ∈ D(ℂ^{D_{j}})}.

The notation S(H) is in principle ambiguous: separability of a state on B(H) is not an intrinsic property of the Hilbert space H or of the algebra B(H); it depends on the particular decomposition of H as a tensor product of (smaller) Hilbert spaces. However, this will not be an issue here since our study focuses on fixed decompositions.

D and S are convex subsets of B_{sa}(H) of (real) dimension n := d^{2} − 1. We write T_{1} for the affine subspace generated by D (or S); it is the hyperplane of trace one matrices. The space B_{sa}(H) inherits a (real) Euclidean structure from the scalar product ⟨·, ·⟩_{HS}. The corresponding unit ball will be denoted by B_{HS} (or B_{HS}^{d}). We denote by vol the corresponding d^{2}-dimensional Lebesgue volume on B_{sa}(H); we will also write vol for the n-dimensional volume induced on T_{1}.

We shall concentrate on the special case when all the subsystems are identical, i.e., D_{1} = ⋯ = D_{N} = D. Our techniques also apply to general state spaces, but formulae which fit all the situations would be more cumbersome than for this “homogeneous” case. If H = (ℂ^{D})^{⊗N}, there are two “regular” ways to make its dimension tend to infinity: either N ⩾ 2 is fixed and D tends to infinity, or D ⩾ 2 is fixed and N goes to infinity (as in [4] for D = 2). Surprisingly, it turns out that in the latter case the natural Euclidean structure is not the one given by the Hilbert-Schmidt scalar product, but rather by a mixture of that product with a Killing-type form. Our goal is to prove the following theorems (recall that we work with H = (ℂ^{D})^{⊗N} and that d = dim H = D^{N}, N = log_{D} d and n = dim D = d^{2} − 1 = D^{2N} − 1).

Theorem 1 (Small number of large subsystems) There exist universal constants C, c > 0 such that, for all D, N ⩾ 2,

\frac{c^{N}}{d^{1/2−1/2N}} ⩽ (\frac{vol(S)}{vol(D)})^{1/n} ⩽ \frac{C(N ln N)^{1/2}}{d^{1/2−1/2N}}

We point out that considering the nth root of the ratio of volumes is natural from the geometric point of view: if the two sets had been Euclidean balls, we would have obtained the ratio of their radii, and so we are comparing the volume radii of S and D (see section 2.1 for additional geometric background).

Theorem 2 (Large number of small subsystems) There exist universal constants C′, c′ > 0 such that, for all D, N ⩾ 2,

\frac{c′}{d^{1/2+α_{D}}} ⩽ (\frac{vol(S)}{vol(D)})^{1/n} ⩽ \frac{C′(DN ln N)^{1/2}}{d^{1/2+α_{D}}}

where

α_{D} := \frac{1}{2} log_{D}(1 + \frac{1}{D}) − \frac{1}{2D^{2}} log_{D}(D + 1)

For illustration, we list approximate values of α_{D} for small D’s: α_{2} ≈ 0.094, α_{3} ≈ 0.061, α_{4} ≈ 0.044. Note that α_{D} is a positive decreasing function of D, asymptotically equivalent to 1/(2D ln D). The quantity d^{1/2+α_{D}} may be alternatively expressed as ((D + 1)^{1−1/D^{2}})^{N/2}.

Theorem 1 asserts that, as D → ∞, the ratio of the volume radii of S and D is of order d^{−(1/2−1/2N)} = D^{−(N−1)/2} (up to a multiplicative constant depending only on N). Theorem 2 is slightly less definite: while, for fixed D, the ratio in question is determined precisely on the scale of the powers of d, there are some (possibly parasitic) logarithmic factors. [We recall again that N = log_{D} d = ln d/ ln D.] We point out that, apart from the value of the numerical constant, the upper estimate in Theorem 2 is always sharper than that in Theorem 1. However, the gain α_{D} in the exponent is negligible if N is fixed and D → ∞.

It is possible to give reasonable estimates on the constants appearing in both theorems. One can, for example, take c = 1/\sqrt{6}, c′ = 0.3 and C = C′ = 4.4. It is also possible to establish a tighter asymptotic behavior of these constants (relevant if one is only interested in large values of d and particularly N): one can have c′ tending to e^{3/4}/\sqrt{2π} ≈ 0.845 as D or N tend to infinity, and C and C′ tending to \sqrt{2} e^{1/4} ≈ 1.816 as N tends to infinity. Finally, sharper estimates for specific dimensions can be obtained by using known results on, among others, efficient spherical codes; see Appendix G of [4] for an example of such calculation.

The case D = 2 of Theorem 2 was treated in detail in [4]. In this note we present additional ingredients required to deal with the general case. We point out that the (relatively) easy part is the estimation of vol(D), which of course does not depend on the tensor structure of H. It has been shown in [7] that

vol(D) = \sqrt{d} (2π)^{d(d−1)/2} \frac{Γ(1) … Γ(d)}{Γ(d^{2})}  (1)

A direct calculation then yields that the volume radius of D behaves as e^{−1/4}d^{−1/2}(1+O(1/d)) as d → ∞. It is also possible (and easy) to estimate the volume radius of D using techniques with the same flavor as the ones presented here. For example, it was shown in [4] that for any value of d that radius is contained between d^{−1/2}/2 and 2d^{−1/2} (see section 2.2 below). Finally, the fact that the volume radius in question is of order d^{−1/2} as d → ∞ follows from an early paper [8].

The ratio of Euclidean volumes is not the only geometric parameter which is of interest here. An arguably more relevant parameter would be its analogue for the so-called Bures volume, which may be a more appropriate measure of size in the present context (see [9]). Another quantity with physical significance is the largest number ε = ε(H) below which the mixture (1 − ε)Id/d + ερ is separable for any state ρ. Of course it is possible to derive from volume estimates an upper bound on this ε(H), but this bound is weaker that what is already known ([10, 11, 5]). Still, the knowledge of the volume radii yields additional information also in this context: for ε ≫ (vol(S)/vol(D))^{1/ dim D}, the mixture (1 − ε)Id/d + ερ is entangled for “most of” ρ ∈ D, and not just for very special states as those constructed in [10, 11, 5]. Another quantity that has been studied in [11, 5, 12] is the inradius of S, which is the radius of the inscribed Euclidean ball in S (here we assume that the balls are centered at Id/d, which is the natural center of both S and D). It seems that, prior to results on qubits in [4], the only upper bound which was known on the inradius of S was the inradius of D, or 1/\sqrt{d(d − 1)}. [A remarkable fact discovered in [12] is that the two inradii coincide when N = 2.] Theorem 2 improves on this for large N giving, up to logarithmic factors, the upper bound 1/d^{1+α_{D}}. Moreover, the argument shows that the same is true for the symmetrized body Σ := conv(S ∪ −S). [Cf. section 2.2 and note that the distance from the hyperplane containing S to the origin is 1/\sqrt{d} > 1/\sqrt{d(d − 1)}, so the inradius of Σ is at least as large as that of S.] The techniques developed in [4] and in the present paper allow to tighten this bound substantially. We present the following sample result.

Theorem 3 (Tight upper bounds on the inradii of S and Σ) There exists an absolute constant C_{0} > 0 such that, for any N, the set Σ((ℂ^{2})^{⊗N}), and hence also S((ℂ^{2})^{⊗N}), does not contain any Hilbert-Schmidt ball of radius C_{0}\sqrt{N ln N} 6^{−N/2}.

For comparison, let us cite the lower bound of 6^{−N/2} on the inradius of the set Σ noted in [4], Appendix H, and a similar lower bound on the a priori smaller inradius of S shown subsequently in [5]. This means that, at least for N qubits, the inradii of S and of Σ have been determined up to a multiplicative factor which is logarithmic in the dimension of the state space. The argument we present can be generalized to other values of D, leading to an upper bound for the inradii of Σ((ℂ^{D})^{⊗N}) and S((ℂ^{D})^{⊗N}) which is (D(D +1))^{−N/2} (again, up to a logarithmic factor). For the inradius of the set Σ this bound is essentially sharp. However, for D > 2, the value (D(D + 1))^{−N/2} does not coincide with the lower bound for the inradius of S((ℂ^{2})^{⊗N}) that was found in [5] and which is of the form O((D(2D − 1))^{−N/2}). As was noticed in [5], a better upper bound for D > 2 is derived from our upper bound for D = 2 and is (up to a logarithmic factor) of the form (1.5 × D^{2})^{−N/2}. However, this still leaves a gap between the upper and lower estimates which is exponential in N (as N → ∞). A similar discussion of the bilateral case (N = 2, D → ∞) can be found in the Remark at the end of section 3.

Theorem 1 above means that typical (as measured by the standard volume) high-dimensional bipartite states are entangled. This statement is of global nature, and is therefore not helpful when one faces a given state and has to decide about its separability. In turn, lower bounds for the inradii of sets Σ, or for the quantity ε(H) mentioned above provide a sufficient condition for separability which, while very useful in some contexts, is conclusive for only a very small fraction of separable states. A very simple and efficient (at least in small dimensions) necessary condition is the so-called Peres partial transpose criterion ([6]). We briefly recall what partial transposition is, say when the state space is H = ℂ^{D} ⊗ ℂ^{D}. Fix a basis (e_{1}, …, e_{D}) of ℂ^{D}, for example the canonical basis. Any state ρ on H can be uniquely expressed as

ρ = ∑_{i,j,α,β=1}^{D} ρ_{iα,jβ}|e_{i} ⊗ e_{α}⟩⟨e_{j} ⊗ e_{β}|

We then consider T ρ, the partial transpose of ρ (with respect to the first subsystem), defined by the formula

(T ρ)_{iα,jβ} = ρ_{jα,iβ}

One checks that T ρ is also an Hermitian operator of trace one which, however, is not necessarily positive. Following [3], we write PPT (Positive Partial Transpose) for the set of states ρ for which T ρ is also positive. Note that while T ρ depends on the choice of the basis, its eigenvalues do not; so the set PPT is basis-independent. The Peres criterion simply reads: any separable state has a positive partial transpose. In other words, we have the inclusions S ⊂ PPT ⊂ D. An natural question (asked for example in [3]) is then: what is the volume of PPT? Is it close to the volume of S, or rather to the volume of D? The following theorem answers the latter question.

Theorem 4 (Asymptotic roughness of PPT criterion) There exists an absolute constant c_{0} > 0 such that for any bipartite system (H = ℂ^{D} ⊗ ℂ^{D})

c_{0} ⩽ (\frac{vol(PPT)}{vol(D)})^{1/n}

An immediate corollary to Theorems 1 and 4 is that, for large D, the volume of PPT states is much bigger than the volume of separable states. This means that a typical high-dimensional PPT state is entangled, and thus that Peres criterion becomes less and less precise as the dimension increases. Theorem 4 is just a sample result; similar analysis may be performed for other bipartite and multipartite systems. On the other hand, it is quite conceivable that the quantity from Theorem 4 admits a nontrivial (i.e., < 1, independent of D) upper bound, even in the case of bipartite systems. [This would imply that vast majority of entangled states are detected by the PPT criterion.]

2 Preliminaries about convex bodies

In this section we list some known (or elementary) facts from convexity theory that will be needed in the sequel. A convex body is a convex compact subset of ℝ^{n} (or of ℂ^{m} identified with ℝ^{2m}, or of an affine subspace of ℝ^{n}) with nonempty interior. We will say that a convex body K is symmetric if it is symmetric with respect to the origin (i.e., K = −K). To a convex body K ⊂ ℝ^{n} containing the origin in its interior one can canonically associate ∥·∥_{K}, the gauge of K, by setting, for x ∈ ℝ^{n}, ∥x∥_{K} := inf{λ > 0 : x ∈ λK}. If K is symmetric, ∥ · ∥_{K} is the norm for which K is the unit ball. If K and L are two convex bodies in ℝ^{n}, each of which contains the origin in its interior, we define the geometric distance between K and L as the product αβ, where α and β are the smallest numbers for which β^{−1}L ⊂ K ⊂ αL . The concept generalizes to bodies with a common interior point contained in an affine subspace of ℝ^{n}; it quantifies how the shapes of K and L differ.

2.1 The Urysohn inequality

Let K ⊂ ℝ^{n} be a convex body and u ∈ S^{n−1} be a unit vector. The width of K in the direction u is

w(K, u) := max_{x∈K}⟨u, x⟩

Geometrically, w(K, u) is (up to the sign) the distance from the origin to the hyperplane tangent to K in the direction u. The mean width of K is simply the mean of the widths in all directions:

w(K) := ∫_{S^{n−1}} w(K, u)dσ(u)

where σ is the Lebesgue measure on the sphere, normalized so that σ(S^{n−1}) = 1. The classical Urysohn inequality, which is of isoperimetric flavor, states that among all convex bodies of given volume, the Euclidean ball has the minimal mean width. It can be written as follows (see, e.g., Appendix A of [4] for a proof)

(\frac{vol(K)}{vol(B_{n}^{2})})^{\frac{1}{n}} ⩽ w(K),

where B_{2}^{n} is the n-dimensional Euclidean unit ball. The quantity on the left-hand side equals the radius of the Euclidean ball which has the same volume as K and, as we mentioned earlier, is sometimes called the volume radius of K; we will denote it vrad(K). We will use the Urysohn inequality to estimate, among others, the volume radius of Σ, which is the quantity we are interested in. It is often more convenient to rewrite the inequality above by expressing the mean width via a Gaussian integral (rather than an integral over the sphere):

vrad(K) ⩽ \frac{1}{γ_{n}} E max_{x∈K}⟨x, G⟩,

where G is a N (0, Id_{n}) Gaussian vector, E is the expectation with respect to G and γ_{n} := \sqrt{2}Γ(\frac{n+1}{2})/Γ(\frac{n}{2}) is a constant which is close to \sqrt{n}. The identity w(K) = γ_{n}^{−1}E max_{x∈K}⟨x, G⟩ is checked by passing to polar coordinates. We will occasionally call E max_{x∈K}⟨x, G⟩ the Gaussian mean width of K and denote it w_{G}(K).

A special situation is when the body K is a polytope with v vertices on the unit sphere. In this case it is well-known (see Proposition 1.1.3. in [13] for a nice proof) that the expectation w_{G}(K) is smaller than \sqrt{2 ln v}. A somewhat more complicated argument based on another proof ([14], Lemme 0.6.2) and supplemented by numerics shows that the same estimate works for a symmetric polytope with 2v vertices on the unit sphere (or just in the unit ball) provided v > 1. We eventually obtain that, for v > 1 points (x_{i})_{i=1}^{v} in the unit ball,

vrad(conv\{±x_{i}\}_{i=1}^{v}) ⩽ w(conv\{±x_{i}\}_{i=1}^{v}) < \frac{1}{γ_{n}} \sqrt{2 ln v}.  (2)

Note that since γ_{n} = w_{G}(B_{2}^{n}) ∼ \sqrt{n}, the quantity on the right will be small as long as ln v ≪ n.

2.2 Symmetrization and the Rogers-Shephard inequality

Let H be an affine hyperplane in ℝ^{n+1}, not containing the origin, and let W be a convex body in H. Consider the symmetrization Ω of W, defined by Ω := conv(W ∪ −W). This procedure is quite natural in the framework of convex bodies, since much more information is available about centrally symmetric convex bodies as opposed to general ones. In particular, Ω is the unit ball with respect to the norm ∥.∥_{Ω}. If h > 0 is the distance between H and the origin, then we have the following inequalities

2h vol(W) ⩽ vol(Ω) ⩽ 2h \frac{2^{n}}{n + 1}vol(W).  (3)

The left hand inequality is an immediate consequence of the Brunn-Minkowski inequality ([15]), and is an equality if the body W is centrally symmetric. The right hand inequality is the Rogers-Shephard inequality ([16]) and equality is achieved when W is a simplex. The factor \frac{2^{n}}{n+1} may appear large, but we point out that its nth root, which is more relevant here, is smaller than 2.

We now consider symmetric versions of D and S, namely Δ := conv(D ∪ −D) and Σ := conv(S ∪ −S) (the latter was defined already in the Introduction); then n = d^{2} − 1. The set Δ is just the Hermitian part of the unit ball of the usual Schatten class of trace class operators. In other words Δ = {A ∈ B_{sa}(H), ∥A∥_{1} ⩽ 1}, where ∥A∥_{1} is the trace class norm, i.e., the sum of singular values of A or, in our Hermitian setting, of the absolute values of the eigenvalues of A. [See section 2.4 for the functionalanalytic interpretation of Σ.] The inequalities (3) imply now

\frac{1}{2} (\frac{vol(Σ)}{vol(Δ)})^{1/n} ⩽ (\frac{vol(S)}{vol(D)})^{1/n} ⩽ 2 (\frac{vol(Σ)}{vol(Δ)})^{1/n}  (4)

Therefore, the loss in precision when passing from the ratio of the volume radii of S and D to the ratio of the volume radii of Σ and Δ is at most a factor of 2. To be precise, the exponent obtained for the symmetrized bodies is 1/n whereas it should be 1/d^{2} (which is the reciprocal of the dimension of Δ and Σ), but this is not at all an issue. First, we can a posteriori change the exponent, this will at most slightly affect the constants. Second, the extra n + 1 in (3) ensures that no modification of the constants is actually needed (see [4], Appendix C, for a precise general statement in this direction).

For future reference we recall here the estimates from [4] for the volume radius of D (cited in the Introduction), for the volume radius of Δ, and for the mean widths of these sets.

\frac{1}{\sqrt{d}} ⩽ vrad(Δ) = (\frac{vol(Δ)}{vol(B_{2}^{d^{2}})})^{1/d^{2}} ⩽ w(Δ) ⩽ \frac{2}{\sqrt{d}}  (5)

\frac{1}{2\sqrt{d}} ⩽ vrad(D) ⩽ w(D) ⩽ \frac{2}{\sqrt{d}}  (6)

While, as we mentioned in the Introduction, both a closed expression for vrad(D) and its precise asymptotic behavior (as the dimension increases) are known, and while presumably similar information about vrad(Δ) may be obtained via the methods of [7], the compact and transparent inequalities from (5) and (6) are sufficient for our asymptotic results. Moreover, having upper bounds for the larger parameter w(·) will provide us with additional flexibility.

2.3 Ellipsoids associated to convex bodies

An ellipsoid is an affine image of the unit ball B_{2}^{n}. There is a one-to-one correspondence between symmetric ellipsoids and scalar products (or Euclidean structures). Indeed, if E = T B_{2}^{n}, with T a linear map, then E is the unit ball associated to the scalar product ⟨x, y⟩_{E} := ⟨T^{−1}x, T^{−1}y⟩. If K is a convex body in ℝ^{n}, its polar body, denoted K^{o}, is defined by K^{o} = {x ∈ ℝ^{n}, ∀y ∈ K, ⟨x, y⟩ ⩽ 1}. If 0 belongs to the interior of K, K^{o} is also a convex body (if not, it fails to be bounded). We point out that ∥x∥_{K^{o}} = max_{y∈K}⟨x, y⟩ and that the restriction of the gauge ∥ · ∥_{K^{o}} to the sphere coincides with w(K, ·), the width function of K defined in section 2.1. We further note that the polar of a symmetric ellipsoid is again a symmetric ellipsoid. The following definition is useful for our purposes.

Definition: If K is a convex body in ℝ^{n}, a John resolution of identity associated to K is a finite family (x_{i}, c_{i})_{i∈I}, where x_{i} belong to ∂K ∩ S^{n−1} (if K ⊂ B_{2}^{n} or B_{2}^{n} ⊂ K, these are contact points of K with the sphere) and c_{i} are positive numbers, such that

1. ∑ c_{i}x_{i} = 0

2. ∀y ∈ ℝ^{n}, y = ∑ c_{i}⟨x_{i}, y⟩x_{i}

Condition 2 can be rephrased using Dirac notation as ∑ c_{i}|x_{i}⟩⟨x_{i}| = Id_{n}. Taking trace both sides, we see that necessarily ∑ c_{i} = n. We recall the following result due to John

Proposition 1 (John’s theorem) Let K be a convex body in ℝ^{n}. Then there exists a unique ellipsoid of minimal volume containing K, called Löwner ellipsoid, which we denote Löw(K). Similarly, there exists a unique ellipsoid of maximal volume contained in K, called John ellipsoid, which we denote John(K). Moreover, the equality Löw(K) = B_{2}^{n} holds if and only if K ⊂ B_{2}^{n} and there exists a John resolution of identity associated to K. Similarly, the equality John(K) = B_{2}^{n} holds if and only if B_{2}^{n} ⊂ K and there exists a John resolution of identity associated to K.

For a proof of this theorem, see [17]. These ellipsoids are affine invariants: for any affine map T, we have John(T K) = T John(K) and Löw(T K) = T Löw(K). In the symmetric case (the one we mostly deal with in the sequel), John and Löwner ellipsoids are also symmetric and dual to each other with respect to polarity. More precisely, if K is symmetric, we have John(K^{o}) = Löw(K)^{o} and Löw(K^{o}) = John(K)^{o}; this is a consequence of the fact that for any symmetric ellipsoid E, we have vol(E^{o}) = vol(B_{2}^{n})^{2}/vol(E). It is therefore immediate to pass from the statement about John ellipsoid to the statement about Löwner ellipsoid (actually the theorem is usually stated for the John ellipsoid only).

2.4 Tensor products of convex bodies

If K and K′ are convex bodies, respectively in ℝ^{n} and ℝ^{n′}, their projective tensor product is the convex body K ˆ⊗K′ in ℝ^{n} ⊗ ℝ^{n′} ∼ ℝ^{nn′} defined as follows

K ˆ⊗K′ = conv{x ⊗ x′, x ∈ K, x′ ∈ K′}.

This terminology is motivated by the fact that when K and K′ are unit balls with respect to some norms, the set K ˆ⊗K′ is the unit ball of the corresponding projective tensor product norm on ℝ^{n} ⊗ ℝ^{n′}. The relevance of the notion to our discussion is obvious: the set of separable states is the projective tensor product of sets of states on factor spaces; more precisely, if H = H_{1} ⊗ H_{2}, then S(H) = D(H_{1}) ˆ⊗D(H_{2}). It is easy to see that the operation ˆ⊗ commutes with symmetrizations: if K̃ = conv(K ∪ −K) and K̃′ = conv(K′ ∪ −K′), then conv(K ˆ⊗K′, −K ˆ⊗K′) = K̃ ˆ⊗K̃′. It follows that, in our notation, Σ(H) = Δ(H_{1}) ˆ⊗Δ(H_{2}). Since, as was pointed out in section 2.2, Δ is the unit ball in the trace class norm, Σ(H) is the unit ball of the projective tensor product of the spaces B_{sa}(H_{k}), k = 1, 2, each endowed with the trace class norm.

The definition of K ˆ⊗K′ – similarly as other definitions, comments and lemmas of this section – immediately generalizes to tensor products of any finite number of factors. However, for the sake of transparency, we shall concentrate in this section on the case of two bodies. We also point out that while the definition appears to be well-adapted to 0-symmetric sets, cones and linear maps as morphisms (this is used in the proof of Lemma 1 below and, later, in the first paragraph of section 5), the projective tensor product is not invariant under affine maps. We refer to [18], Chapter 2, for a discussion of related categorical issues and to [19] for exhaustive treatment of tensor products of normed spaces.

If E = SB_{2}^{n} and E′ = S′B_{2}^{n′} are two ellipsoids, respectively in ℝ^{n} and ℝ^{n′}, their Hilbertian tensor product is the ellipsoid E ⊗_{2} E′ := (S ⊗ S′)B_{2}^{nn′}. This definition does not depend on the choice of S and S′. It turns out that Löwner ellipsoids behave well with respect to projective tensor product, as the following lemma shows (note that the analogous statement does not hold for the John ellipsoid).

Lemma 1 Let K ⊂ ℝ^{n} and K′ ⊂ ℝ^{n′} be two convex bodies. Then the Löwner ellipsoid of their projective tensor product is the Hilbertian tensor product of the respective Löwner ellipsoids.

In terms of scalar products, for every x, y in ℝ^{n} and x′, y′ in ℝ^{n′}, we have

⟨x ⊗ x′, y ⊗ y′⟩_{Löw(K ˆ⊗K′)} = ⟨x, y⟩_{Löw(K)}⟨x′, y′⟩_{Löw(K′)}

Proof: First suppose that Löw(K) = B_{2}^{n} and Löw(K′) = B_{2}^{n′}. By John’s theorem, there exist John resolutions of identity for K and K′, respectively (x_{i}, c_{i})_{1⩽i⩽k} and (x′_{j}, c′_{j})_{1⩽j⩽k′}. We easily check that K ˆ⊗K′ ⊂ B_{2}^{nn′} = B_{2}^{n} ⊗_{2} B_{2}^{n′}. Moreover, (x_{i} ⊗ x′_{j}, c_{i}c′_{j})_{1⩽i⩽k,1⩽j⩽k′} is also a John resolution of identity for K ˆ⊗K′. It is enough to check this on pure tensors: take y ∈ ℝ^{n} and y′ ∈ ℝ^{n′} and verify the two conditions

1. ∑_{i=1}^{k} ∑_{j=1}^{k′} c_{i}c′_{j}x_{i} ⊗ x′_{j} = (∑_{i=1}^{k} c_{i}x_{i}) ⊗ (∑_{j=1}^{k′} c′_{j}x′_{j}) = 0

2. ∑_{i=1}^{k} ∑_{j=1}^{k′} c_{i}c′_{j}⟨x_{i} ⊗ x′_{j}, y ⊗ y′⟩x_{i} ⊗ x′_{j} = (∑_{i=1}^{k} c_{i}⟨x_{i}, y⟩x_{i}) ⊗ (∑_{j=1}^{k′} c′_{j}⟨x′_{j}, y′⟩x′_{j}) = y ⊗ y′

For the general case, let T and T′ be linear maps such that T Löw(K) = B_{2}^{n} and T′Löw(K′) = B_{2}^{n′}. Using the elementary identities Löw(T K) = T Löw(K) and (T ⊗ T′)(K ˆ⊗K′) = (T K) ˆ⊗(T′K′), the result follows from the previous particular case. ■

The next “Chevet-Gordon type” lemma relates the mean widths of convex sets to that of their projective tensor product. It is most conveniently stated for the mean Gaussian width w_{G}(·) defined in section 2.1.

Lemma 2 Let K ⊂ B_{2}^{n} ⊂ ℝ^{n} and K′ ⊂ B_{2}^{n′} ⊂ ℝ^{n′} be convex sets, one of which is the convex hull of a subset of the corresponding unit sphere. Then

w_{G}(K ˆ⊗K′) ⩽ w_{G}(K) + w_{G}(K′).

Restating the assertion of the Lemma in terms of the standard mean width gives

w(K ˆ⊗K′) ⩽ \frac{γ_{n}}{γ_{nn′}} w(K) + \frac{γ_{n′}}{γ_{nn′}} w(K′) ⩽ \frac{w(K)}{\sqrt{n′}} + \frac{w(K′)}{\sqrt{n}},

where the second inequality follows from the fact that the sequence (γ_{k}/\sqrt{k}) is increasing (which can be deduced from inequalities proved in [20]; the fact that the coefficients on the right hand side are approximately 1/\sqrt{n′} and 1/\sqrt{n} follows from the simpler relationship γ_{k} ∼ \sqrt{k}.) We thus get seemingly strong upper bounds for mean widths and, a fortiori, for volume radii of projective tensor products of convex bodies. However, in spite of its elegance, Lemma 2 will play only rather limited role in our arguments. This is because, when iterated, it yields asymptotically worse dependence on the number of factors than the techniques employed in subsequent sections. Accordingly, its main use will be in considerations involving few factors and in ameliorating the numerical constants which appear in the statements of the Theorems. The Lemma can be shown by an argument very similar to that of section 2.3 of [21], we skip the proof; here we just note that we do not know whether the hypothesis that one of the sets be spanned by a subset of the sphere is necessary. This requirement is satisfied for all sets in our applications, and it is not at all restrictive if the widths of K, K′ are estimated via cardinalities of their spanning sets.

Finally, let us note that if K and K′ are circled convex bodies in respective complex vector spaces (a convex body K ⊂ ℂ^{n} is said to be circled if K = e^{iϑ}K for all real ϑ), then K ˆ⊗K′ is circled; as was the case for symmetrizations, the operation absconv (the absolute convex hull) commutes with the projective tensor product.

3 Proof of Theorem 1: Small number of large subsystems

The upper bound can be obtained through a standard discretization argument. Recall that, for δ > 0, a δ-net of a set K is a subset N ⊂ K such that for each x ∈ K there exists y ∈ N whose distance to x is smaller than δ. If N ⊂ ℂ^{D}, we write P (N) for the polytope conv{±|x⟩⟨x|}_{x∈N} ⊂ B_{sa}(ℂ^{D}). The following elementary lemma shows that if N is a net of the unit sphere of ℂ^{D} – which may be identified with S^{2D−1} as a metric space – then P (N) is a good approximation of Δ(ℂ^{D}).

Lemma 3 Let δ < \sqrt{2 − \sqrt{2}} ≈ 0.765 and let N be a δ-net of the unit sphere of ℂ^{D}. Then

(1 − 2δ^{2} + δ^{4}/2)Δ(ℂ^{D}) ⊂ P (N) ⊂ Δ(ℂ^{D})

Proof: The second inclusion is trivial. Let us check the first one through the corresponding dual (polar) norms

∥A∥_{Δ(ℂ^{D})^{o}} = max_{x∈ℂ^{D},∥x∥=1}⟨ A, ±|x⟩⟨x| ⟩_{HS} = max_{x∈ℂ^{D},∥x∥=1} |⟨x|A|x⟩| = max_{λ∈σ(A)} |λ| = ∥A∥_{op},

∥A∥_{P (N)^{o}} = max_{y∈N} |⟨y|A|y⟩|

where ∥·∥_{op} is the operator norm and σ(·) is the spectrum (recall that we consider only Hermitian matrices here). We need to show that ∥A∥_{P (N)^{o}} ≥ (1−2δ^{2}+δ^{4}/2)∥A∥_{op}. To this end, let A ∈ B_{sa}(ℂ^{D}) be such that ∥A∥_{op} and the largest eigenvalue of A are both equal to 1, and let x ∈ ℂ^{D} be a norm one vector such that Ax = x. Choose y_{0} ∈ N verifying ∥x − y_{0}∥ ⩽ δ. We claim that ⟨y_{0}|A|y_{0}⟩ ≥ 1 − 2δ^{2} + δ^{4}/2; the inequality between the norms follows then by homogeneity. The claim is easily established by writing y_{0} = y_{1} + y_{2} with y_{1} = ⟨y_{0}|x⟩x and noting that ⟨y_{1}|A|y_{1}⟩ ≥ |⟨y_{0}|x⟩|^{2} ≥ (1 − δ^{2}/2)^{2}, |⟨y_{2}|A|y_{2}⟩| ≤ ∥y_{2}∥^{2} ≤ δ^{2}(1 − δ^{2}/4) and ⟨y_{1}|A|y_{2}⟩ = 0. ■

Tensoring the conclusion of the preceding lemma and recalling that Δ(ℂ^{D})^{ˆ⊗N} = Σ(H) yields an inclusion (1 − 2δ^{2} + δ^{4}/2)^{N}Σ(H) ⊂ P (N)^{ˆ⊗N}. Observe that P (N)^{ˆ⊗N} is another symmetric polytope with at most 2(#N)^{N} vertices. It is well-known ([22], Lemma 4.10) that for δ ⩽ 1 we can find δ-nets in S^{2D−1} of cardinality not exceeding ⩽ (1 + 2/δ)^{2D}. We thus get a bound on the volume of the polytope using the estimation (2).

We note for future reference that the above discussion can be carried out using other Euclidean structures, the only constraint being that the vertices of the polytope are of norm not exceeding 1. Thus, if E is any ellipsoid containing Σ(H), we obtain

(\frac{vol(Σ(H))}{vol(E)})^{1/d^{2}} ⩽ inf_{0<δ<\sqrt{2−\sqrt{2}}} \frac{1}{γ_{d^{2}}(1 − 2δ^{2} + δ^{4}/2)^{N}} \sqrt{2 ln ((1 + 2/δ)^{2DN})}  (7)

Using E = B_{HS} and, say, δ = 1/\sqrt{N ln 2N} leads to an estimate vrad(Σ(H)) = O((DN ln N)^{1/2}/d). [Indeed, for large d we have then γ_{d^{2}} ∼ d and, for large N, (1−2δ^{2} +δ^{4}/2)^{N} ∼ 1 and ln ((1 + 2/δ)^{2DN}) ∼ DN ln N.] We obtain the upper bound announced in Theorem 1 by combining this with the lower bound on vrad(Δ(H)) given by (5) and with (4). Finally, the more precise statements about the constants indicated in the introduction can be obtained by using (1), Lemma 2 and Appendix C of [4].

The lower estimate will be proved by showing that Σ(H) contains a Euclidean ball of appropriately large volume. We start with the following lemma

Lemma 4 Let K := (B_{2}^{D})^{ˆ⊗m} be the projective tensor product of m copies of the D-dimensional Euclidean ball (real or complex). Then K contains the following multiple of the Euclidean ball in (ℂ^{D})^{⊗m} (resp., (ℝ^{D})^{⊗m})

\frac{1}{D^{(m−1)/2}} B_{2}^{D^{m}} ⊂ K.

Proof: Let (e_{1}, …, e_{D}) be the canonical basis of ℂ^{D}. We write an element A of (ℂ^{D})^{⊗m} as a generalized matrix: A = (a_{i_{1}...i_{m}}) stands for

A = D ; ∑ ; i_{1}, …, i_{m} = 1 a_{i_{1}...i_{m}}e_{i_{1}} ⊗ ⋯ ⊗ e_{i_{m}}

The norm dual to ∥ · ∥_{K} is

∥A∥_{K^{o}} = {max \atop x^{1}, …, x^{m} ∈ B_{2}^{D}} | D ; ∑ ; i_{1}, …, i_{m} = 1 a_{i_{1}...i_{m}}x_{i_{1}}^{1} … x_{i_{m}}^{m} |  (8)

Let us write ∥A∥_{2} for the Euclidean norm of A, i.e., ∥A∥_{2}^{2} = ∑ |a_{i_{1}...i_{m}}|^{2}. We want to show that ∀A ∈ (ℂ^{D})^{⊗m} we have D^{−(m−1)/2}∥A∥_{2} ⩽ ∥A∥_{K^{o}}. By homogeneity, we can assume that ∥A∥_{2} = 1. Now choose x^{1}, …, x^{m−1} randomly and independently to be uniformly distributed on the unit sphere of ℂ^{D}. We write E for the corresponding expectation. Let X_{k}, k = 1, …, D, be the random variable obtained by summing only on the kth “hyper-slice,” that is

X_{k} = X_{k}(x^{1}, …, x^{m−1}) := D ; ∑ ; i_{1}, …, i_{m−1} = 1 a_{i_{1}...i_{m−1}k}x_{i_{1}}^{1} … x_{i_{m−1}}^{m−1}

We can easily calculate E|X_{k}|^{2} since many cancellations come from the fact that E(x_{i}^{k}\overline{x_{j}^{l}}) = \frac{1}{D} δ_{kl}δ_{ij}. We obtain

E|X_{k}|^{2} = \frac{1}{D^{m−1}} D ; ∑ ; i_{1}, …, i_{m−1} = 1 |a_{i_{1}...i_{n−1}k}|^{2}

Therefore, E(∑_{k=1}^{D} |X_{k}|^{2}) = \frac{1}{D^{m−1}} . This implies the existence of unit vectors x^{1}, …, x^{m−1} such that, denoting Y_{k} := X_{k}(x^{1}, …, x^{m−1}), we have ∑_{k=1}^{D} |Y_{k}|^{2} ⩾ \frac{1}{D^{m−1}} . Choosing these points in (8), we obtain

∥A∥_{K^{o}} ⩾ max_{x^{m}∈B_{2}^{D}} ∑_{k=1}^{D} Y_{k}x_{k}^{m} = (∑_{k=1}^{D} |Y_{k}|^{2})^{1/2} ⩾ \frac{1}{D^{(m−1)/2}}

■

Remark: It turns out that this lemma is surprisingly sharp. As shown in Lemma 8 below, even the a priori larger volume radius of K is (up to multiplicative factor depending only on m) of the same order D^{−(m−1)/2}. Note that for m = 2 we obtain even the optimal constant (these are the classical inclusion relations for balls in Schatten classes).

Let H = (ℂ^{D})^{⊗N} and Γ(H) ⊂ B(H) be the convex hull of rank one product operators

Γ(H) := conv{|x_{1} ⊗ ⋯ ⊗ x_{N}⟩⟨y_{1} ⊗ ⋯ ⊗ y_{N}| : x_{1}, y_{1}, …, x_{N}, y_{N} ∈ B_{2}^{D}}.

The convex body Γ(H) is most naturally seen as the Nth projective tensor power of the set of (not necessarily Hermitian) operators on ℂ^{D} whose trace class norm is ≤ 1. However, it can also be identified with (B_{2}^{D})^{ˆ⊗2N} when we identify B(K) with \overline{K} ⊗ K. It then follows from the preceding lemma that Γ(H) contains a Euclidean ball (a Hilbert-Schmidt ball in this context) of radius D^{−(2N−1)/2}.

The next lemma will relate Γ(H) to Σ(H), allowing to deduce that the latter body contains a suitably large Euclidean ball. Let d_{N} be the geometric distance between the sets Δ and Σ corresponding to N qubits, i.e. the smallest positive number such that Δ((ℂ^{2})^{⊗N}) ⊂ d_{N}Σ((ℂ^{2})^{⊗N}). We then have

Lemma 5 Let π : B(H) → B_{sa}(H) be the projection onto Hermitian part, π(A) := \frac{1}{2}(A + A^{†}). Then

π(Γ(H)) ⊂ d_{N} Σ(H).

Proof: It is enough to show that extreme points of π(Γ) are contained in d_{N}Σ. Any extreme point A of π(Γ) can be written as

A = \frac{1}{2} (|x_{1} ⊗ ⋯ ⊗ x_{N}⟩⟨y_{1} ⊗ ⋯ ⊗ y_{N}| + |y_{1} ⊗ ⋯ ⊗ y_{N}⟩⟨x_{1} ⊗ ⋯ ⊗ x_{N}|)

It may appear at the first sight that the above representation shows that A is separable. However, while the two terms in the parentheses are indeed product operators, they are not Hermitian and we can only conclude that A ∈ Δ(H) (as a Hermitian operator whose trace class norm is ≤ 1).

Let H_{i} be the 2-dimensional subspace of ℂ^{D} spanned by x_{i} and y_{i} (if the vectors are proportional, add any vector to get a 2-dimensional space) and let H′ := H_{1} ⊗ ⋯ ⊗ H_{N}. Then A can be considered as an operator on H′; more precisely, as an element of Δ(H′) (and, conversely, any operator acting on H′ can be canonically lifted to one acting on H). Note that since we are in the asymptotics where N is small and D is large, the dimension of the problem has been dramatically decreased. Since A belongs to Δ(H′), it also belongs to d_{N}Σ(H′), and thus to d_{N}Σ(H). ■

To effectively apply Lemma 5, upper bounds on d_{N} are needed. It has been observed in [4], Appendix H, that d_{N} ≤ 6^{N/2}. This estimate has been subsequently slightly improved in [5] to 2/3 × 6^{N/2}, and even to a_{N} × 6^{N/2} with lim_{N→∞} a_{N} ≈ 0.624. [These bounds are in fact based on estimates for the a priori larger quantities, the geometric distances between Σ((ℂ^{2})^{⊗N}) (or S((ℂ^{2})^{⊗N}) − Id/2^{N}) and Hilbert-Schmidt balls, which are essentially reciprocals of the Hilbert-Schmidt inradii of these sets; and in this latter context they are “nearly optimal;” see Theorem 3 and the comments following it.] Thus Σ(H) ⊃ 3/2 × 6^{−N/2}π(Γ(H)); combining this inclusion with Lemma 4 or, more precisely, with the observation following the definition of Γ(H), we conclude that Σ(H) contains the Hilbert-Schmidt ball of radius 3/2 × 6^{−N/2}D^{−(2N−1)/2} = 3/2 × 6^{−N/2}/d^{1−1/2N}. This gives a lower bound for the volume radius which, together with (5), yields

(\frac{vol(Σ)}{vol(Δ)})^{1/d^{2}} ⩾ \frac{3/4 × 6^{−N/2}}{d^{1/2−1/2N}}

To conclude the proof of the theorem we pass to the bodies S and D using (4).

Remarks: (1) The bipartite case (N = 2) was studied in [12], which contains in particular the remarkable result that D and S have then the same inradius, which equals 1/\sqrt{d(d − 1)}. However, the inradii of the symmetrized bodies, which are (in both cases) comparable with the volume radii, are (asymptotically) very different: the inradius of Δ equals 1/\sqrt{d}, while the inradius of Σ has just been shown to be of order 1/d^{3/4}.

(2) The upper bound on d_{N} was further slightly improved in subsequent versions of [5] and, most recently, in [23], where it was shown that S contains a ball of radius \sqrt{3} × 6^{−N/2}, which implies d_{N} ≤ (3^{N−1}(2^{N} − 1))^{1/2}.

4 Proof of Theorem 2: Large number of small subsystems

This part deals with asymptotic estimations of volumes when N, the number of subsystems, tends to infinity whereas the dimension D of each subsystem remains bounded. This case is probably the one with most physical interest. When all subsystems are 2-dimensional (qubits), Theorem 2 has been proved in [4].

For the proof of the present case it is more convenient to deal with an affine image of Σ which is more balanced than Σ itself or, equivalently, to consider a new scalar product which is better adapted to the analysis of Σ than the Hilbert-Schmidt product. It is a known phenomenon that high-dimensional convex bodies often enjoy hidden symmetries (or approximate symmetries) that are only revealed when one looks at them through a suitable Euclidean structure. In our situation, in the asymptotics when N is large and D is bounded, our Theorem 1, obtained with the usual Euclidean structure, misses the genuine volumic behavior of the bodies S and Σ. The appropriate scalar product will be here the one derived from the Löwner ellipsoid of Σ. To see why, just look back at the equation (7). This bound is the tightest when E is the Löwner ellipsoid of Σ. It turns out that it is possible to describe completely this ellipsoid. First recall that Σ(H) = Δ(ℂ^{D}) ˆ⊗ … ˆ⊗Δ(ℂ^{D}). By Lemma 1, it is enough to calculate the Löwner ellipsoid of Δ(ℂ^{D}), and by tensoring we get the Löwner ellipsoid of Σ(H).

We will determine the Löwner ellipsoid of Δ(ℂ^{D}) using the following elementary general lemma.

Lemma 6 Let u be a unit vector in ℝ^{n} and H_{0} = {u}^{⊥} be the orthogonal hyperplane. Let h > 0 be real number and H = H_{0} + hu be a translate of H_{0}. We consider a convex body Ω = conv{W ∪ −W }, where W is a convex body in H. Then the following assertions are equivalent:

1. Ω is in Löwner position (i.e. the unit ball B_{2}^{n} is the Löwner ellipsoid of Ω).

2. h = 1/\sqrt{n} and B_{2}^{n} ∩ H is the Löwner ellipsoid of W.

Proof: Assume that Ω is in Löwner position, so Ω ⊂ B_{2}^{n}. By John’s theorem (Proposition 1), this means that there exists a John resolution of identity (x_{i}, c_{i}), with x_{i} ∈ Ω ∩ S^{n−1} and ∑ c_{i}|x_{i}⟩⟨x_{i}| = Id. Since x_{i} are extreme points of Ω, they must be in W or −W, and since Ω is symmetric we can assume they are all in W. Let P be the orthogonal projection onto H_{0}. It follows that ∑ c_{i}|P x_{i}⟩⟨P x_{i}| = P; note that ∥P x_{i}∥ = \sqrt{1 − h^{2}}. This means that (P x_{i}, c′_{i}) is a John resolution of identity in H_{0}, with c′_{i} = (1 − h^{2})c_{i}. By Proposition 1, (1 − h^{2})^{−1/2}P W is in Löwner position, or equivalently B_{2}^{n} ∩ H is the Löwner ellipsoid of W. Moreover, we have the conditions ∑ c′_{i} = n − 1 and ∑ c_{i} = n, which force h = 1/\sqrt{n}.

The converse follows by retracing the above argument in the opposite direction. ■

Lemma 7 The Löwner ellipsoid of Δ(ℂ^{D}) is determined by the following scalar product defined for A, B ∈ B_{sa}(ℂ^{D}) by

⟨A, B⟩_{Löw(Δ(ℂ^{D}))} = (1 + \frac{1}{D})tr(AB) − \frac{1}{D} tr(A)tr(B)

Proof: First remark that, because of its uniqueness, the Löwner ellipsoid of any body K must inherit all the symmetries of K. Since D(ℂ^{D}) is invariant under unitary conjugations (i.e., the maps π_{U}(X) = UXU^{†} with U ∈ U(D)), the ellipsoid Löw(D(ℂ^{D})) must be similarly invariant, and thus it is the circumscribed Euclidean ball. This is actually somewhat delicate; the relevant fact is that the action of the group {π_{U} : U ∈ U(D)} on the hyperplane T_{1} containing D(ℂ^{D}) is irreducible (in particular, Id/D is the only fixed point and so it must be the center). In the language of convex bodies (see [24]) we say that D(ℂ^{D}) has enough symmetries. On the other hand, the fact that this group acts transitively on the set of extreme points of D(ℂ^{D}) (which are the pure states) implies by itself only that all these extreme points are contact points, i.e., belong to the boundary of the Löwner ellipsoid.

By Lemma 6, we know that the trace of the Löwner ellipsoid of Δ(ℂ^{D}) on the hyperplane T_{1} is a Euclidean ball (centered at Id/D), so we have for some real numbers α and β

⟨A, B⟩_{Löw(Δ(ℂ^{D}))} = αtr(AB) + βtr(A)tr(B)

To determine α and β, observe that ⟨ρ, ρ⟩_{Löw(Δ(ℂ^{D}))} = 1 for any pure state (hence contact point) ρ, and that (from the condition on h in Lemma 6; note that n = D^{2}), ⟨Id/D, Id/D⟩_{Löw(Δ(ℂ^{D}))} = 1/D^{2}. This gives α = 1 + 1/D and β = −1/D. ■

It is possible to use the Löwner ellipsoid of Σ(H) as the ellipsoid E in formula (7). Choosing δ = 1/\sqrt{N ln 2N} as earlier, we obtain the upper estimate in the formula

\frac{1}{d} ⩽ (\frac{vol(Σ)}{vol(Löw(Σ))})^{1/d^{2}} ⩽ \frac{C\sqrt{DN ln N}}{d}  (9)

The lower estimate follows from the classical fact ([17]) that for a centrally symmetric convex body K in ℝ^{n}, we have the inclusion Löw(K) ⊂ \sqrt{n} K. Improvements on constants can be derived from a result of Barthe ([25]) which asserts that for an n-dimensional symmetric body K, the ratio (vol(K)/vol(Löw(K))^{1/n} is minimal when K is the unit ball of ℓ_{1}^{n} (and thus is at least (4/π)^{1/2}(Γ(n/2 + 1)/Γ(n + 1))^{1/n}) =

\sqrt{\frac{2e}{π}}(1 − O(\frac{1}{n}))\frac{1}{\sqrt{n}} ; we recall that here n = d^{2}).

It remains to calculate the volume of the Löwner ellipsoid of Σ. It follows from Lemma 1 that, if Φ denotes a linear map which sends B_{2}^{D^{2}} onto Löw(Δ(ℂ^{D})), then Ψ := Φ^{⊗N} maps B_{HS} onto Löw(Σ(H)). By Lemma 7, we can define Φ by Φ(A) = (1 + 1/D)^{−1/2}A if A has trace 0 and Φ(Id) = \sqrt{D} Id. This gives det(Φ) = \sqrt{D(1 + 1/D)^{1−D^{2}}} and finally

\frac{vol(Löw(Σ))}{vol(B_{HS})} = det(Ψ) = det(Φ)^{ND^{2N−2}} = d^{−α_{D}d^{2}}  (10)

To complete the proof it remains to combine the volume estimates (5),(9),(10) and (4).

5 Proof of Theorem 3: Tight upper bounds on the inradii

The idea is to show that there is a projection of the set Σ = Σ((ℂ^{2})^{⊗N}) which is demonstrably small. Specifically, let P : B_{sa}(ℂ^{2}) → B_{sa}(ℂ^{2}) be the orthogonal projection onto the 3-dimensional subspace of trace zero matrices and let Π := P^{⊗N}. Since projective tensor products commute with linear maps (in the sense that (T_{1} ⊗ … ⊗ T_{s})(K_{1} ˆ⊗ … ˆ⊗K_{s}) = (T_{1}K_{1}) ˆ⊗ … ˆ⊗(T_{s}K_{s})), we have

Π (Σ((ℂ^{2})^{⊗N})) = P^{⊗N} (Δ(ℂ^{2})^{ˆ⊗N}) = (P (Δ(ℂ^{2})))^{ˆ⊗N} .

Since Δ(ℂ^{2}) is a cylinder whose axis coincides with the kernel of P, the image of Δ(ℂ^{2}) under P is a 3-dimensional Euclidean ball of radius 1/\sqrt{2} (more precisely, D(ℂ^{2})−Id/2). Accordingly, the image of the corresponding set Σ under Π is the nth projective tensor power of such a ball. The relevant parameters of such sets (mean widths, volume radii) are majorized by the following statement, which is a complement of Lemma 4.

Lemma 8 There is an absolute constant C_{1} such that if D, m are positive integers (m ⩾ 2) and K := (B_{2}^{D})^{ˆ⊗m} is the projective tensor product of m copies of the D-dimensional Euclidean ball (real or complex), then

vrad(K) ⩽ w(K) < \frac{C_{1}\sqrt{m ln m}}{D^{(m−1)/2}}

Proof: The first inequality in Lemma 8 – comparing the volume radius of a convex body to its mean width – is just the Urysohn inequality. The proof of the second follows the same lines as – but is simpler than – the approach that yielded formula (7). We present the details only for the case that is relevant to Theorem 3, namely D = 3 in the real setting. The argument is very similar to the one used in [4] to obtain an upper bound for the volume of Σ((ℂ^{2})^{⊗m}), where the reader is referred for additional background and justifications.

We start by noting that, for any δ ∈ (0, \sqrt{2}), the sphere S^{2} contains a δ-net F whose cardinality is ⩽ 16/δ^{2}. On the other hand, an elementary geometric argument shows that the convex hull of any δ-net contains a (Euclidean) ball of radius 1 − δ^{2}/2. Accordingly, the convex hull of F^{⊗m}, the mth tensor power of F, contains (1 − δ^{2}/2)^{m}(B_{2}^{3})^{ˆ⊗m}. Since #(F^{⊗m}) ⩽ (#F)^{m} ⩽ (4/δ)^{2m}, it follows from (2) that

w((1 − δ^{2}/2)^{m}(B_{2}^{3})^{ˆ⊗m}) ⩽ w(conv(F^{⊗m})) < γ_{3^{m}}^{−1}\sqrt{2 ln ((4/δ)^{2m})}

and, consequently,

vrad((B_{2}^{3})^{ˆ⊗m}) ⩽ w((B_{2}^{3})^{ˆ⊗m}) < 2γ_{3^{m}}^{−1}(1 − δ^{2}/2)^{−m}\sqrt{m ln (4/δ)}.

We now choose δ = 1/\sqrt{m ln 2m}; then, for large m, (1 − δ^{2}/2)^{−m} ∼ 1, ln (4/δ) ∼ \frac{1}{2} ln m and γ_{3^{m}} ∼ 3^{m/2}. This yields the asserted upper bound on the mean width with C_{1} ∼ \sqrt{2/3} for large m. A more careful calculation using Lemma 2 for small m shows that C_{1} = 1.673 works for all m. [The discussion of constants above and in the remainder of this section is specific to D = 2, but can be analogously carried over in the general case; for example, it is easy to show that C_{1} ∼ 1 works for large m and all D.] As in [4], further improvements are possible by working with explicit nets and/or by noting that F can be chosen to be symmetric, but we will not pursue them since it is likely that, for the problem at hand, sharper estimates can be obtained by analytic methods. ■

We now return to the proof of Theorem 3. From prior considerations, the image of Σ under the projection Π is congruent to 2^{−N/2}(B_{2}^{3})^{ˆ⊗N} and so, by Lemma 8,

w(Π(Σ)) = 2^{−N/2}w((B_{2}^{3})^{ˆ⊗N} < 3^{1/2}C_{1}\sqrt{N ln N} 6^{−N/2}.

Since the inradius is trivially smaller than the mean width, and since the inradius of the set S of separable states does not exceed that of its symmetrization Σ, Theorem 3 follows (with C_{0} = 3^{1/2}C_{1} < 3). It is also routine to obtain an (identical or nearly identical) upper bound on the mean width of S; however, some care is needed because the dimensions of S and Σ are not the same.

Since our argument is of a global nature, we are not able to produce an explicit state in the ball of radius r := C_{0}\sqrt{N ln N} 6^{−N/2} and centered at Id/d which is not separable. However, standard tools of asymptotic geometric analysis (cf. [8] or [22]) imply that even stronger properties are satisfied “generically.” Denote by H_{0} the d_{0} := 3^{N}-dimensional range of the projection Π. Then, for most of the unit vectors u on the unit sphere of H_{0}, the state σ = Id/2^{N} + 2ru is not separable, and the same holds for any state ρ such that Π(ρ) = Π(σ) (here “most of” means that the exceptional set is of normalized measure < 2^{−d_{0}/2}). Moreover, a slightly weaker but comparable property holds simultaneously for all u in a “generic” (in the sense of the invariant measure on the corresponding Grassmannian) ⌈d_{0}/2⌉- dimensional subspace of H_{0}.

As mentioned in the introduction, the above argument can be generalized to other values of D and leads to an upper bound for the inradii of the sets Σ and S corresponding to (ℂ^{D})^{⊗N} which is, up to a logarithmic factor, (D(D + 1))^{−N/2}. While this upper bound differs, for D > 2, from the lower bound for the inradius of S that was found in [5], it gives the correct order for the inradius of the set Σ. Indeed, Σ contains Löw(Σ)/d, which itself contains (D(D + 1))^{−N/2}B_{HS} (this argument parallels the one for qubits given in [4], Appendix H, where we refer the reader for details).

6 Proof of Theorem 4: Asymptotic roughness of PPT criterion

We will use the following proposition which is taken from [26].

Proposition 2 Let K and L be convex bodies in ℝ^{n} with the same centroid. Then

vol(K)vol(L) ⩽ vol(K − L)vol(K ∩ L),

where K − L := {x − y : x ∈ K, y ∈ L} is the Minkowski difference.

We apply the proposition with K = D and L = T D. This gives

\frac{vol(D)}{vol(PPT)} ⩽ \frac{vol(D − T D)}{vol(D)}  (11)

Note that we actually used the proposition in the space T_{1} ∼ ℝ^{n}, seen as a vector space with Id/d as origin; the point Id/d is also the centroid of D (and T D), it is even the the only fixed point under the group of symmetries of D (cf. the proof of Lemma 7). We rewrite (11) using volume radii

(\frac{vol(D)}{vol(PPT)})^{1/n} ⩽ \frac{vrad(D − T D)}{vrad(D)}

Recall that we majorized the volume radius by the mean width using the Urysohn inequality (here mean width is also taken in T_{1}). This is very convenient since, as one can check immediately from the definition, the mean width is additive with respect to the Minkowski operations: w(D − T D) = w(D) + w(−T D). Since −T is an isometry, it preserves the uniform measure on the sphere S^{n−1} and thus w(−T D) = w(D). This gives

(\frac{vol(D)}{vol(PPT)})^{1/n} ⩽ \frac{2w(D)}{vrad(D)}

We now appeal to (6) to majorize the right hand side by 8, which proves Theorem 4 with c_{0} = 1/8. Note also that one can use the explicit formula (1) for the volume of D; this shows that asymptotically (the lower estimate for) c_{0} tends to e^{−1/4}/4 ≈ 0.195. Moreover, numerical evidence (which presumably can be confirmed by rigorous calculation using appropriate Stirling-type formulae, or inequalities similar to those of [20]) suggests that vrad(D) ⩾ e^{−1/4}/\sqrt{d} for all dimensions d, which would imply that the asymptotic value is in fact a bound.

Finally, observe that the above proof works actually for any (Hilbert-Schmidt) isometry in T_{1} which fixes Id/d, and not only for the partial transpose T.

Acknowledgments: The contribution of the first named author is a part of his Ph. D. thesis written at the University of Paris VI under the supervision of the second named author, and has been partially supported by the European Network PHD, MCRN-511953. The second named author has been partially supported by the National Science Foundation (U.S.A.).

References

[1] R. F. Werner, Phys. Rev. A 40, 4277 (1989).

[2] K. Życzkowski, P. Horodecki, A. Sanpera, and M. Lewenstein, Phys. Rev. A 58, 883 (1998).

[3] M. Horodecki, P. Horodecki, and R. Horodecki, in Quantum Information, edited by G. Alber et al., Springer Tracts in Modern Physics Vol. 173, (Springer, Berlin, 2001), p. 151.

[4] S. J. Szarek, Phys. Rev. A, Phys. Rev. A 72, 032304 (2005)

[5] L. Gurvits and H. Barnum, arXiv.org e-print quant-ph/0409095.

[6] A. Peres, Phys. Rev. Lett. 77, 1413 (1996).

[7] K. Życzkowski and H.-J. Sommers, J. Phys. A 36, 10115 (2003).

[8] S. J. Szarek and N. Tomczak-Jaegermann, Compos. Math. 40, 367 (1980).

[9] S. L. Braunstein and C. M. Caves, Phys. Rev. Lett. 72, 3439 (1994).

[10] P. Rungta et al, in Directions in Quantum Optics, Lecture Notes in Physics, Vol. 561 (Springer, Berlin, 2001), p. 149.

[11] L. Gurvits and H. Barnum, Phys. Rev. A 68, 042312 (2003).

[12] L. Gurvits and H. Barnum, Phys. Rev. A 66, 062311 (2002).

[13] M. Talagrand, Spin glasses: a challenge for mathematicians (Springer-Verlag, Berlin, 2003).

[14] X. Fernique, Fonctions aléatoires gaussiennes, vecteurs aléatoires gaussiens (Université de Montréal, Montreal, 1997).

[15] R. J. Gardner, Bull. Amer. Math. Soc. (N.S.) 39, 355 (2002).

[16] C. A. Rogers and G. C. Shephard, J. Lond. Math. Soc. 33, 270 (1958).

[17] K. Ball, In Flavors of geometry, vol. 31 of Math. Sci. Res. Inst. Publ. (Cambridge Univ. Press, Cambridge, 1997).

[18] G. Svetlichny, On the Foundations of Experimental Statistical Sciences. http://www.mat.puc-rio.

    br/~svetlich/files/statsci.pdf

[19] A. Defant and K. Floret, Tensor norms and operator ideals (North-Holland, Amsterdam, 1993).

[20] Y. Luke, Math. Balkanica 2, 118 (1972).

[21] K. R. Davidson and S. J. Szarek, in Handbook of the geometry of Banach spaces, edited by W. B. Johnson and J. Lindenstrauss (North-Holland, Amsterdam, 2001), Vol. 1, pp. 317–366; (North-Holland, Amsterdam, 2003), Vol. 2, pp. 1819–1820.

[22] G. Pisier, The volume of convex bodies and Banach space geometry (Cambridge University, Cambridge, U.K., 1989).

[23] G. Aubrun, S. J. Szarek, and E. Werner, preprint.

[24] N. Tomczak-Jaegermann, Banach-Mazur distances and finite-dimensional operator ideals (Longman Scientific & Technical, Harlow, 1989).

[25] F. Barthe, Invent. Math. 134, 335 (1998).

[26] V. D. Milman and A. Pajor, Adv. Math. 152, 314 (2002).

Équipe d’Analyse Fonctionnelle, B.C. 186, Université Paris VI, 4 Place Jussieu, F-75252 Paris, France

E-mail: aubrun@math.jussieu.fr

Department of Mathematics, Case Western Reserve University, Cleveland, OH 44106-7058, U.S.A. and Équipe d’Analyse Fonctionnelle, B.C. 186, Université Paris VI, 4 Place Jussieu, F-75252 Paris, France

E-mail: szarek@cwru.edu