CATALYTIC MAJORIZATION AND ℓ_{p} NORMS

GUILLAUME AUBRUN AND ION NECHITA

Abstract. An important problem in quantum information theory is the mathematical characterization of the phenomenon of quantum catalysis: when can the surrounding entanglement be used to perform transformations of a jointly held quantum state under LOCC (local operations and classical communication) ? Mathematically, the question amounts to describe, for a fixed vector y, the set T (y) of vectors x such that we have x ⊗ z ≺ y ⊗ z for some z, where ≺ denotes the standard majorization relation.

Our main result is that the closure of T (y) in the ℓ_{1} norm can be fully described by inequalities on the ℓ_{p} norms: ∥x∥_{p} ⩽ ∥y∥_{p} for all p ⩾ 1. This is a first step towards a complete description of T (y) itself. It can also be seen as a ℓ_{p}-norm analogue of Ky Fan dominance theorem about unitarily invariant norms. The proofs exploits links with another quantum phenomenon: the possibiliy of multiple-copy transformations (x^{⊗n} ≺ y^{⊗n} for given n). The main new tool is a variant of Cramér’s theorem on large deviations for sums of i.i.d. random variables.

1. Introduction

The increasing interest that quantum entanglement has received in the past decade is due, in part, to its use as a resource in quantum information processing. We investigate the problem of entanglement transformation: under which conditions can an entangled state |ϕ⟩ be transformed into another entangled state |ψ⟩ ? We restrict ourselves to LOCC protocols: Alice and Bob share |ϕ⟩ and have at their disposal only local operations (such as unitaries U_{A} ⊗ I_{B} for Alice) and classical communication. Nielsen showed in [13] that such a transformation is possible if and only if λ_{ϕ} ≺ λ_{ψ}, where “≺” is the majorization relation and λ_{ϕ}, λ_{ψ} are the Schmidt coefficients vectors of |ϕ⟩ and |ψ⟩ respectively. Practically in the same time, Jonathan and Plenio [8] discovered a striking phenomenon: entanglement can help LOCC communication, without even being consumed. Precisely, they have found states |ϕ⟩ and |ψ⟩ such that |ϕ⟩ cannot be transformed into |ψ⟩, but, with the help of a catalyst state |χ⟩, the transformation |ϕ⟩ ⊗ |χ⟩ → |ψ⟩ ⊗ |χ⟩ is possible. When such a catalyst exists, we say that the state |ϕ⟩ is trumped by |ψ⟩ and we write λ_{ϕ} ≺_{T} λ_{ψ}. We say then that |ϕ⟩ can be transformed into |ψ⟩ by entanglement-assisted LOCC or ELOCC. It turns out that the trumping relation is much more complicated that the majorization relation; one can easily check on two given states |ϕ⟩ and |ψ⟩ whether λ_{ϕ} ≺ λ_{ψ} is satisfifted or not, but there is no direct way to determine if λ_{ϕ} ≺_{T} λ_{ψ}. Later, Bandyopadhyay et al. [1] discovered that a similar situation occurs when trying to transform by LOCC multiple copies of |ϕ⟩ into |ψ⟩. It may happen that the transformation |ϕ⟩ → |ψ⟩ is not possible, but when considering n copies, one can transform |ϕ⟩^{⊗n} into |ψ⟩^{⊗n}. The phenomenon of multiple simultaneous LOCC transformations, or MLOCC, has been intensively studied in the last years and many similarities with ELOCC have been found [6, 7].

In this note, we make some progress towards a complete characterization of both ELOCC and MLOCC. We show that a set of inequalities involving ℓ_{p} norms (see the remark on Conjecture 1 at the end of the paper) is equivalent to the fact that |ϕ⟩ can be approached by a sequence of states |ϕ_{n}⟩ which are MLOCC/ELOCC-dominated by |ψ⟩. An important point is that we allow the dimension of |ϕ_{n}⟩ to exceed the dimension of |ϕ⟩. Our proof uses probabilistic tools; we introduce probability measures associated to |ϕ⟩ and |ψ⟩ and we use large deviation techniques to show the desired result.

Interestingly, the result can be reversed to give a characterization of ℓ_{p} norms that is similar to the Ky Fan characterization of unitarily invariant norms. We refer the interested reader to Section 3. The rest of the paper is organized as follows: in Section 2 we introduce the notation and the general framework of entanglement transformation of bipartite states. We also state our main result, Theorem 1. The theorem is proved in Section 4. Conclusions and some directions for further study are sketched in Section 5. The appendix at the end of the paper contains basic results from large deviation theory needed in the proof of the main theorem.

Acknowledgement: we thank the referees for several helpful remarks that improved the presentation of the paper.

2. Notation and statement of the results

For d ∈ N^{∗}, let P_{d} be the set of d-dimensional probability vectors : P_{d} = {x ∈ R^{d} s.t. x_{i} ⩾ 0, ∑ x_{i} = 1}. If x ∈ P_{d}, we write x^{↓} for the decreasing rearrangement of x, i.e. the vector x^{↓} ∈ P_{d} such that x and x^{↓} have the same coordinates up to permutation, and x_{i}^{↓} ⩾ x_{i+1}^{↓}. We shall also write x_{max} for x_{1}^{↓} and x_{min} for the smallest nonzero coordinate of x.

There is an operation on probability vectors that is fundamental in what follows: the tensor product ⊗. If x = (x_{1}, …, x_{d}) ∈ P_{d} and x′ = (x′_{1}, …, x′_{d′}) ∈ P_{d′}, the tensor product x ⊗ x′ is the vector (x_{i}x′_{j})_{ij} ∈ P_{dd′}; the way we order the coordinates of x ⊗ x′ is immaterial for our purposes. We also define the direct sum x ⊕ x′ as the concatenated vector (x_{1}, …, x_{d}, x′_{1}, …, x′_{d′}) ∈ R^{d+d′}.

It x ∈ P_{d} satisfies x_{d} = 0, it will be useful to identify x with the truncated vector (x_{1}, …, x_{d−1}) ∈ P_{d−1}. This identification induces a canonical inclusion P_{d−1} ⊂ P_{d}. Thus, every vector x ∈ P_{d} can be thought of as a vector of P_{d′} for all d′ ⩾ d by appending d′ − d null elements to x. We consider thus the set of all probability vectors P_{<∞} = ⋃_{d>0} P_{d}. In other words, P_{<∞} is the set of finitely supported probability vectors.

Let us now introduce the classical majorization relation [11, 2]. If x, y ∈ R^{d} we define the submajorization relation ≺_{w} as follows

x ≺_{w} y iff. ∀k ∈ {1, … d}, ∑_{i=1}^{k} x_{i}^{↓} ⩽ ∑_{i=1}^{k} y_{i}^{↓},

and the majorization relation ≺ as

x ≺ y iff. ∑_{i=1}^{d} x_{i} = ∑_{i=1}^{d} y_{i} and ∀k ∈ {1, … d − 1}, ∑_{i=1}^{k} x_{i}^{↓} ⩽ ∑_{i=1}^{k} y_{i}^{↓}.

We usually work with probability vectors, for which both relations coincide. However, it will be useful in the proof to work with deficient vectors (of total mass less than 1) and to use submajorization. We write S_{d}(y) for the set of vectors x in P_{d} which are majorized by y. It is well-known that S_{d}(y) is a compact convex set whose extreme points are the vectors obtained by permuting the coordinates of y; many other characterizations of S_{d}(y) are known [14, 3]. This relation behaves well with respect to direct sums and tensor products: x ≺ y implies x ⊕ z ≺ y ⊕ z and x ⊗ z ≺ y ⊗ z for any z ∈ P_{<∞}. The majorization relation has been shown to have a very important role in quantum information. Nielsen has proved [13] that a state |ϕ⟩ belonging to Alice and Bob can be transformed into the state |ψ⟩ by using local operations and classical communication (LOCC) if and only if

λ_{ϕ} ≺ λ_{ψ},

where λ_{ϕ} (respectively λ_{ψ}) is the vector of eigenvalues of the density matrix for Alice’s system when the joint system is in the state |ϕ⟩ (respectively |ψ⟩). Not long after Nielsen’s theorem, Jonathan and Plenio have discovered a very intriguing phenomenon: there exist states |ϕ⟩ and |ψ⟩ such that the transformation |ϕ⟩ → |ψ⟩ is impossible by LOCC, but, with the aid of a catalyst state |χ⟩, the transformation |ϕ⟩ ⊗ |χ⟩ → |ψ⟩ ⊗ |χ⟩ becomes possible; we say that |ϕ⟩ can be transformed into |ψ⟩ by Entanglement-assisted LOCC or ELOCC. This result has motivated a more complex relation between probability vectors: if x, y ∈ P_{d}, we say that y trumps x and write x ≺_{T} y if there exists z ∈ P_{<∞} such that x ⊗ z ≺ y ⊗ z. It is important to require that the auxiliary vector z (called the catalyst) is finitely supported (see Remark 2). Given y ∈ P_{d}, we write T_{d}(y) for the set of d-dimensional vectors trumped by y, that is

T_{d}(y) = {x ∈ P_{d} s.t. x ≺_{T} y}.

The set T_{d}(y) is in general larger than S_{d}(y) [4] and much more complicated to describe. Up to now, there is no known simple procedure to decide whether x ∈ T_{d}(y) or not. Hence, finding a tractable characterization of the relation ≺_{T} (or, equivalently, of the set T_{d}(y)) has become an important open problem in quantum information theory [16]. The geometry of T_{d}(y) has been studied in [3, 4]: it is a bounded convex set that it is neither closed nor open (provided y is not too simple). We shall introduce now another important extension of LOCC transformations. Bandyopadhyay et al [1] found an example of entangled states |ϕ⟩ and |ψ⟩ with the property that the LOCC transformation |ϕ⟩ → |ψ⟩ is impossible but, when one tries to transform multiple copies of the states, the transformation |ϕ⟩^{⊗n} → |ψ⟩^{⊗n} becomes possible. We say that |ψ⟩ MLOCC-dominates |ϕ⟩. We introduce the analogue of the trumping relation for probability vectors:

x ≺_{M} y iff ∃n ⩾ 1 s.t. x^{⊗n} ≺ y^{⊗n},

and the set of probability vectors MLOCC-dominated by a given vector y:

M_{d}(y) = {x ∈ P_{d} s.t. x ≺_{M} y}.

Not much is known about the set M_{d}(y). It has been studied in [6] and shown to have many similarities with the set T_{d}(y): for example it is neither closed nor open in general. One important point is that, for all y, we have M_{d}(y) ⊆ T_{d}(y) (see [6]).

We report progress towards a description of the sets of M_{d}(y) and T_{d}(y). The main ingredient of our approach is the following observation. Consider two vectors x, y ∈ P_{d}. Whether x ≺ y, x ≺_{M} y, x ≺_{T} y or not depends only on the non-zero coordinates of x and y. Thus, it is possible to ≺/≺_{M}/≺_{T} - compare vectors of different sizes by appending the necessary amount of zero coordinates to the end of one of them. Hence, it seems more natural (at least from a mathematical point of view) to consider the sets

T_{<∞}(y) = {x ∈ P_{<∞} s.t. x ≺_{T} y} = {x ∈ P_{<∞} s.t. ∃z ∈ P_{<∞} s.t. x ⊗ z ≺ y ⊗ z} = ⋃_{d′⩾d} T_{d′}(y)

and

M_{<∞}(y) = {x ∈ P_{<∞} s.t. x ≺_{M} y} = {x ∈ P_{<∞} s.t. ∃n ⩾ 1 s.t. x^{⊗n} ≺ y^{⊗n}} = ⋃_{d′⩾d} M_{d′}(y).

The important point here is that both T_{<∞}(y) and M_{<∞}(y) do not depend anymore on the size of y, but only on the non-null coordinates of y. Of course, if y ∈ P_{d}, T_{d}(y) = T_{<∞}(y) ∩ P_{d} and M_{d}(y) = M_{<∞}(y) ∩ P_{d}; this shows that the sets T_{<∞}(y) and M_{<∞}(y) are not closed either in general (otherwise T_{d}(y) and M_{d}(y) would be also closed). We then write \overline{T_{<∞}(y)} and \overline{M_{<∞}(y)} to denote the closure taken with respect to the ℓ_{1}-norm, the natural topology in this setting (see Remark 3). Recall that for p ⩾ 1, the ℓ_{p} norm of a vector x ∈ P_{d} is defined as

(1)  ∥x∥_{p} = (∑_{i=1}^{d} x_{i}^{p})^{1/p}

and ∥x∥_{∞} = max x_{i}. We now come to our main result:

Theorem 1. Consider two vectors x, y ∈ P_{<∞}. The following assertions are equivalent: (a) x ∈ \overline{M_{<∞}(y)},

(b) x ∈ \overline{T_{<∞}(y)},
(c) ∥x∥_{p} ⩽ ∥y∥_{p} ∀p ⩾ 1.

Remark 1. Note that instead of demanding that ∥x∥_{p} ⩽ ∥y∥_{p} for all p ⩾ 1, it suffices to ask for x, y ∈ P_{d} that the inequality holds for all p ∈ [1, p_{max}(x, y)], where p_{max}(x, y) = log d/(log y_{max} − log x_{max}). The inequalities for p > p_{max} follow by simple computation. For such results in a more general setting, see [12].

Remark 2. It is important to see at this point how the set \overline{T_{<∞}(y)} is related to the set T_{d}(y). First of all, note that if we drop the closure, we have equality: T_{<∞}(y) ∩ P_{d} = T_{d}(y) for y ∈ P_{d}. However, when taking the ℓ_{1} closure of the left hand side, we obtain a strict inclusion: \overline{T_{d}(y)} ⊊ \overline{T_{<∞}(y)} ∩ P_{d}. An example for such a vector is provided by the phenomenon of infinite-dimensional catalysis, discovered by Daftuar [3]. Take y = (0.5, 0.25, 0.25) and x = (0.4, 0.4, 0.2). It is obvious that x ∉ \overline{T_{d}(y)} because x_{3} < y_{3} and the condition x_{d} ⩾ y_{d} is necessary for x ∈ \overline{T_{d}(y)}. However, there exist an infinitedimensional catalyst z = (1 − α)(1, α, α^{2}, …, α^{k}, …), where α = 2^{− \frac{1}{8}} , such that x ⊗ z ≺ y ⊗ z and ||x ⊗ z||_{p} ⩽ ||y ⊗ z||_{p} for all p ⩾ 1. Note that z is ℓ_{p}-bounded and thus ∥x∥_{p} ⩽ ∥y∥_{p} for all p ⩾ 1. By the preceding theorem, we have that x ∈ \overline{T_{<∞}(y)} ∩ P_{3}. For further remarks on this topic, see Section 5.

Remark 3. The use of the ℓ_{1} norm is natural in this context from a mathematical point of view since P_{<∞} is a subset of the norm-closed hyperplane of ℓ_{1} defined by ∑ x_{i} = 1. Let us explain also how it relates to other physically motivated distances between the approaching states |ϕ_{n}⟩ and the original state |ϕ⟩. Recall that x is the eigenvalue vector of the reduced density matrix corresponding to Alice’s (or, equivalently to Bob’s) part of the system. From the details of the proof (see also Section 5), one sees that the size of the approaching vectors x_{n} increases with n. So, in order to compare ρ and ρ_{n}, we have to realize them as density matrices on the same Hilbert space H. Moreover, we can suppose that the two states are diagonalizable in the same basis (Alice can achieve this by applying a local unitary basis change). As usually, we append the necessary number of zero eigenvalues to x in order to have the same size as x_{n}. We obtain the following equality:

∥x − x_{n}∥_{1} = ∥ρ − ρ_{n}∥_{tr}.

So, for Alice’s part of the system, we obtain a convergence in the trace norm sense. It is well known that the trace norm distance is related to the probability that the two states can be distinguished by some measurement. Moreover, by using some classical inequalities (see [15], Chapter 9), the fidelity F (ρ, ρ_{n}) can be shown to converge to 1.

3. A ℓ_{p} version of Ky Fan theorem

In this section, we explain how Theorem 1 can be seen as an analogue of Ky Fan dominance theorem. We refer to [2] for background. We denote by ℳ_{d} the space of complex d × d matrices. A norm ||| · ||| on ℳ_{d} is said to be unitarily invariant if |||UAV ||| = |||A||| for all unitary matrices U, V. A norm || · || on R^{d} is said to be symmetric if

||(x_{1}, …, x_{d})|| = ||(±x_{σ(1)}, …, ±x_{σ(d)})||

for all choices of signs in {±1}^{d} and all permutations σ ∈ 𝔖_{d}. It is well-known ([2], Theorem IV.2.1) that unitarily invariant norms on ℳ_{d} are in 1-to-1 correspondance with symmetric norms on R^{d} (consider the restriction of ||| · ||| to diagonal matrices).

Examples of unitarily invariant norms are given by Ky Fan norms, defined for k = 1, 2, …, d by

|||A|||_{(k)} = ∑_{j=1}^{k} s_{j}(A),

where s_{1}(A) ⩾ ⋯ ⩾ s_{d}(A) denote the ordered singular values of a matrix A. The Ky Fan dominance theorem asserts that these norms are extremal among unitarily invariant norms in the following sense: if A, B satisfy |||A|||_{(k)} ⩽ |||B|||_{(k)} for any k = 1, ⋯, d, then |||A||| ⩽ |||B||| for any unitarily invariant norm ; this condition can also be formulated as s(A) ≺_{w} s(B), where s(·) denotes the vector of singular values of a matrix.

This gives a way to derive an infinite family of inequalities from a finite one. However this may be a too strong requirement and one can wonder what happens for an important special class of unitarily invariant norms: the Schatten p-norms (or noncommutative ℓ_{p} norms), defined for p ⩾ 1 by

|||A|||_{p} = (∑_{j=1}^{d} s_{j}(A)^{p})^{1/p} .

To state our result, we need to compare matrices of different sizes. If d < d′ we identify ℳ_{d} with the top-left corner of ℳ_{d′} ; this gives a natural inclusion ℳ_{d} ⊂ ℳ_{d′} and we write ℳ_{<∞} = ⋃_{d} ℳ_{d}. Note that the tensor product of matrices is a well-defined operation on ℳ_{<∞}.

Theorem 2. Let A, B ∈ ℳ_{d}. The following are equivalent (1) |||A|||_{p} ⩽ |||B|||_{p} for all p ⩾ 1.

(2) There exists in ℳ_{<∞} a sequence (A_{n}) so that lim_{n→∞} |||A_{n}−A|||_{1} = 0 and |||A_{n}^{⊗n}||| ⩽ |||B_{n}^{⊗n}|||

for all unitarily invariant norms |||.||| (or, equivalently, so that s(A_{n}^{⊗n}) ≺_{w} s(B^{⊗n})).

Of course, a main difference between this result and Ky Fan dominance theorem is that condition (ii) here is hard to check and involves infinitely many inequalities.

Proof (sketch). Because of the bijective correspondance between unitarily invariant norms on matrices and symmetric norms on vectors, it is enough to prove the theorem for positive diagonal matrices. This is almost the content of the equivalence (a) ⟺ (c) of Theorem 1. The only slight remark that we need in order to get condition (2) as stated here is the following: in Lemma 2 below, it follows from the proof that we can actually choose the integer n so that x^{⊗N} ≺_{w} y^{⊗N} for any N ⩾ n. □

4. The proof of the theorem

We shall prove the sequence of implications (a) ⇒ (b) ⇒ (c) ⇒ (a). The first two are well known; we sketch their proof for completeness. The third is the most difficult one and represents our contribution to the theorem.

(a) ⇒ (b) Because the closure is taken with respect to the same topology (ℓ_{1}) for both \overline{M_{<∞}(y)} and \overline{T_{<∞}(y)}, it is enough to show M_{<∞}(y) ⊂ T_{<∞}(y). Let x ∈ M_{<∞}(y) and consider n such that x^{⊗n} ≺ y^{⊗n}. The trick here (see [6]) is to use the following z as a catalyst

z = x^{⊗(n−1)} ⊕ x^{⊗(n−2)} ⊗ y ⊕ ⋯ ⊕ x ⊗ y^{⊗(n−2)} ⊕ y^{⊗(n−1)}.

For simplicity we do not normalize z, but this is irrelevant. The vector z has been constructed such that

x ⊗ z = x^{⊗n} ⊕ w and y ⊗ z = y^{⊗n} ⊕ w,

where w is the same in both expressions. This implies that x ⊗ z ≺ y ⊗ z, i.e. x ∈ T_{<∞}(y).

(b) ⇒ (c) Let z ∈ P_{<∞} be the catalyst for x ≺_{T} y: x ⊗ z ≺ y ⊗ z. A function φ : R^{d} → R is said to be Schur-convex if a ≺ b implies φ(a) ⩽ φ(b). It is well-known (see [11, 14]) that if h : R → R is a convex function, then φ : x ↦ ∑_{i=1}^{d} h(x_{i}) is Schur-convex. Consequently, the functions x ↦ ∥x∥_{p}^{p} are Schur-convex for p ⩾ 1. Moreover, they satisfy the identity ∥x ⊗ z∥_{p} = ∥x∥_{p}∥z∥_{p}, and similarly for y. Since ∥z∥_{p} is finite, we get that ∥x∥_{p} ⩽ ∥y∥_{p}. To show that the same is true for x ∈ \overline{T_{<∞}(y)}, it suffices to check that the set of x ∈ ℓ_{1} such that ∥x∥_{p} ⩽ ∥y∥_{p} is norm-closed; this follows from the inequality ∥ · ∥_{p} ⩽ ∥ · ∥_{1}.

(c) ⇒ (a) We will adapt some techniques used by G. Kuperberg in a slightly different context [10]. In our proof, we allow deficient vectors, i.e. vectors with total mass smaller than 1, and we use submajorization.

As in [10], we associate to a positive vector x ∈ R^{d} the measure μ_{x} = ∑_{i=1}^{d} x_{i}δ_{log x_{i}}, where δ_{z} is the Dirac measure at point z. The basic property is that the tensor product operation of vectors corresponds to the convolution of associated measures:

μ_{x⊗y} = μ_{x} ∗ μ_{y}.

The convolution of two measures μ and ν is defined by the relation

μ ∗ ν(A) = (μ × ν) ({(x, y) ∈ R^{2} : x + y ∈ A}) .

Moreover, if μ and ν are probability measures and X_{μ} and X_{ν} denote independent random variables with laws respectively μ and ν, then μ ∗ ν is the law of X_{μ} + X_{ν}.

The following lemma gives a way to prove majorization using comparison of the tails of the associated measures

Lemma 1. Let x and y be two vectors of R^{d} with non-negative components. Consider the measures μ_{x} and μ_{y} associated with x and y. Assume that, for all t ∈ R, μ_{x}[t, ∞) ⩽ μ_{y}[t, ∞). Then x ≺_{w} y.

Proof. Note that

μ_{x}[t, ∞) = ∑_{i:log x_{i}⩾t} x_{i} = ∑_{i:x_{i}⩾exp(t)} x_{i}.

Thus, for all u > 0, ∑_{i:x_{i}⩾u} x_{i} ⩽ ∑_{i:y_{i}⩾u} y_{i}. For simplicity, we assume first that all coordinates of y are distinct. We will show by induction on k ∈ {1, …, d} that ∑_{i=1}^{k} x_{i}^{↓} ⩽ ∑_{i=1}^{k} y_{i}^{↓}. For the first step; use u = y_{1}^{↓} to conclude that x_{1}^{↓} ⩽ y_{1}^{↓}. Now, fix k ∈ {1, …, d−1} and suppose that ∑_{i=1}^{k} x_{i}^{↓} ⩽ ∑_{i=1}^{k} y_{i}^{↓}. If x_{k+1}^{↓} ⩽ y_{k+1}^{↓}, the induction step is obvious. If x_{k+1}^{↓} > y_{k+1}^{↓}, we use u = x_{k+1}^{↓} to get

∑_{i=1}^{k+1} x_{i}^{↓} ⩽ ∑_{i:x_{i}⩾x_{k+1}^{↓}} x_{i} ⩽ ∑_{i:y_{i}⩾x_{k+1}^{↓}} y_{i} ⩽ ∑_{i:y_{i}⩾y_{k+1}^{↓}} y_{i} = ∑_{i=1}^{k+1} y_{i}^{↓}.

This completes the induction when y has distinct coordinates. The general case follows by approximating y by y + ε_{n}, where (ε_{n}) is a suitable sequence of positive vectors tending to 0. The approximation is possible since the set of vectors y majorizing a fixed x is closed. □

We now get to the key lemma in our argument. We shall use a slightly modified version of Cramér large deviations theorem — see Appendix.

Lemma 2. Let x, y in R^{d}, with nonnegative coordinates. Assume that for any 1 ⩽ p ⩽ ∞, we have the strict inequality ∥x∥_{p} < ∥y∥_{p}. Then there exists an integer n such that x^{⊗n} ≺_{w} y^{⊗n}.

Proof. Consider x and y satisfying the hypotheses of the lemma. We can assume by multiplying both vectors by a positive constant K that ∥y∥_{1} = 1. Let p = 1 − ∥x∥_{1} > 0. We introduce the measures μ_{x} and μ_{y} associated to x and y; μ_{y} is a probability measure but μ_{x} is not, so we add a mass at −∞ by setting \overline{μ}_{x} = μ_{x} + pδ_{−∞}. Let X and Y be random variables distributed according to \overline{μ}_{x} and μ_{y} respectively. We denote by (X_{n}) (resp. (Y_{n})) a sequence of i.i.d. copies of X (resp. Y). We are going to show that for n large enough

(2)  ∀t ∈ R, P(X_{1} + ⋯ + X_{n} ⩾ nt) ⩽ P(Y_{1} + ⋯ + Y_{n} ⩾ nt).

This is equivalent to showing that

∫_{nt}^{∞} dμ_{x}^{∗n} = ∫_{nt}^{∞} d\overline{μ}_{x}^{∗n} ⩽ ∫_{nt}^{∞} dμ_{y}^{∗n},

which, by the previous lemma implies x^{⊗n} ≺_{w} y^{⊗n}. Note that the asymptotic behavior of the quantities appearing in (2) is governed by Cramér’s theorem. Let f_{n}(t) = P(X_{1} + ⋯ + X_{n} ⩾ nt)^{1/n} and g_{n}(t) = P(Y_{1} + ⋯ + Y_{n} ⩾ nt)^{1/n}. Applying Cramér’s theorem (see Appendix), we obtain

f(t) := lim_{n→∞} f_{n}(t) = \begin{cases}1 − p if t ⩽ E(X|X ≠ −∞) \\ e^{−Λ_{X}^{∗}(t)} otherwise. \end{cases}

g(t) := lim_{n→∞} g_{n}(t) = \begin{cases}1 if t ⩽ E(Y) \\ e^{−Λ_{Y}^{∗} (t)} otherwise. \end{cases}

Note also that the log-Laplace of X, defined for λ ∈ R by Λ_{X}(λ) = log Ee^{λX}, is related to the ℓ_{p} norms of x:

∀λ ⩾ 0, Λ_{X}(λ) = log ∥x∥_{λ+1}^{λ+1}.

The same holds for Y: Λ_{Y} (λ) = log ∥y∥_{λ+1}^{λ+1} and thus we have Λ_{X}(λ) < Λ_{Y} (λ) for λ ⩾ 0.

Let M_{X} = esssup X = log ∥x∥_{∞} and M_{Y} = esssup Y = log ∥y∥_{∞} ; by hypothesis M_{X} < M_{Y}. First of all, note that f_{n}(t) = 0 for t ⩾ M_{X}, so it suffices to show that f_{n} ⩽ g_{n} on (−∞, M_{X}], for n large enough. We claim that f < g on (−∞, M_{Y}), and thus on (−∞, M_{X}]. Indeed, for E(Y) ⩽ t < M_{Y}, the supremum in the definition of Λ_{Y}^{∗} (t) is attained at a point λ_{0} ⩾ 0 (cf Appendix), so we have that

f(t) ⩽ e−(λ^{0}t − Λ^{X}(λ^{0})) < e−(λ^{0}t − Λ^{Y} (λ^{0})) = g(t),

where the strict inequality follows from the fact that Λ_{X}(λ) < Λ_{Y} (λ), for all λ ⩾ 0. For t < E(Y), g(t) = 1 and f(t) ⩽ 1 − p < 1. Moreover, the functions f and g admit finite limits in −∞: lim_{t→−∞} f(t) = 1 − p and lim_{t→−∞} g(t) = 1. Thus, on the compact set [−∞, M_{X}], the functions f and g are well-defined, non-increasing, continuous and satisfy f < g.

We now use the following elementary fact: if a sequence of non-increasing functions defined on a compact interval I converges pointwise towards a continuous limit, then the convergence is actually uniform on I (for a proof see [17] Part 2, Problem 127; this statement is attributed to Pólya or to Dini depending on authors). We apply this result to (f_{n}) and (g_{n}) on the interval I = [−∞, M_{X}] to conclude that the convergence is uniform for both sequences. As f < g, we can therefore find n large enough such that f_{n} ⩽ g_{n} on I, and thus on R. This is equivalent to (2) and completes the proof of the lemma. □

Remark 4. It is possible to avoid the use of Cramér’s theorem by using low-technology estimates on large deviations probability instead, as done in [10]. This requires additional care to get the required uniform bounds and slightly obfuscates the argument. The only advantage is to give explicit bounds for the value of n in Lemma 2, which our compactness argument does not. These bounds are quite bad anyway, and for example do not allow to replace the ℓ_{1}-closure in the main theorem by a ℓ_{p}-closure for some p < 1.

Proof of (c) ⇒ (a) (continued) Recall that x and y are such that ∥x∥_{p} ⩽ ∥y∥_{p} for any p ⩾ 1 and that we want to find, for any ε > 0 small enough, a vector x_{ε} ∈ M_{<∞}(y) such that ∥x − x_{ε}∥_{1} ⩽ ε. Let d_{x} (resp. d_{y}) be the number of nonzero coordinates of x (resp. y). We proceed as follows : let 0 < ε < 2d_{x}x_{min} and consider the (deficient) vector x′_{ε} obtained from x by subtracting ε/2d_{x} to each of its nonzero coordinates. This implies that x′_{ε} is a positive vector, ∥x − x′_{ε}∥_{1} = ε/2 and that x′_{ε} satisfies the hypotheses of Lemma 2. Applying the lemma, we obtain the existence of an integer n such that (x′_{ε})^{⊗n} ≺_{w} y^{⊗n}.

Remember that x′_{ε} is deficient; we now enlarge it into a vector x_{ε} ∈ P_{<∞} by adding mass ε/2. But since we want to keep the property x_{ε}^{⊗n} ≺_{w} y^{⊗n} (which is identical to x_{ε}^{⊗n} ≺_{w} y^{⊗n}), a safe way to do this is to add a large number of coordinates, each of them being very small. More precisely, let x_{ε} = x′_{ε} ⊕ δ^{⊕D}, where δD = ε/2 and δ is a positive number such that δ(x′_{ε})_{max}^{n−1} ⩽ min((x′_{ε})_{min}^{n}, y_{min}^{n}). We claim that x_{ε}^{⊗n} ≺ y^{⊗n}, that is, for any k ⩾ 1,

(3)  ∑_{i=1}^{k}(x_{ε}^{⊗n})_{i}^{↓} ⩽ ∑_{i=1}^{k}(y^{⊗n})_{i}^{↓}.

Indeed, δ has been chosen so that the d_{x}^{n} largest coordinates of x_{ε}^{⊗n} are exactly the coordinates of (x′_{ε})^{⊗n}, so when 1 ⩽ k ⩽ d_{x}^{n}, (3) follows from the relation (x′_{ε})^{⊗n} ≺_{w} y^{⊗n}. If d_{x} < k ⩽ d_{y}^{n}, the inequality also holds since the choice of δ guarantees (x_{ε}^{⊗n})_{k}^{↓} ⩽ (y^{⊗n})_{k}^{↓}. Finally if k ⩾ d_{y}^{n}, (3) holds trivially since the right-hand side equals 1.

In conclusion, x_{ε}^{⊗n} ≺ y^{⊗n}, and thus x_{ε} ∈ M_{<∞}(y). But x_{ε} has been constructed such that ∥x − x_{ε}∥_{1} ⩽ ε and thus x ∈ \overline{M_{<∞}(y)} which completes the proof of the theorem.

5. Conclusion and further remarks

In conclusion, we are able to give a nice description of the ℓ_{1}-closure of the set T_{<∞}(y). However, this closure may be substantially larger than the usual closure \overline{T_{d}(y)} in P_{d}, and requires approximation by vectors with growing support. Our result can be seen as a contribution to a conjecture attributed to Nielsen [3]:

Conjecture 1. Fix a vector y ∈ P_{d}. Then a vector x ∈ P_{d} belongs to \overline{T_{d}(y)} if and only if the following conditions are verified.

(1) For p ⩾ 1, ∥x∥_{p} ⩽ ∥y∥_{p}.

(2) For 0 < p ⩽ 1, ∥x∥_{p} ⩾ ∥y∥_{p}.

(3) For p < 0, ∥x∥_{p} ⩾ ∥y∥_{p}.

M. Klimesh announced a proof of this conjecture in a short communication [9], but the solution has not appeared in print yet. However, his methods are different from our approach (private communication). Note that the definition of ∥ · ∥_{p} given in (1) is extended to any p ∈ R^{∗}. For p < 1, ∥ · ∥_{p} is not a norm in the usual sense. We have shown that the condition (1) above is equivalent to x ∈ \overline{T_{<∞}(y)}. Notice however that \overline{T_{<∞}(y)} is in general larger than \overline{T_{d}(y)}; note also that the set of x ∈ P_{d} that satisfy conditions (1–3) is closed. The “only if” part of the conjecture follows from standard convexity/concavity properties of functionals ∥ · ∥_{p}, see [14, 3].

This question also appears in [6] where it is formulated using the Rényi entropies. For any real p ≠ 1, the p-Rényi entropy is defined for x ∈ P_{d} as

H_{p}(x) = \frac{sgn(p)}{p − 1} log_{2} (∑_{i=1}^{d} x_{i}^{p}) .

The limit case p = 1 corresponds to the usual entropy. The conditions (1–3) of the conjecture can be concisely reformulated as “H_{p}(x) ⩽ H_{p}(y) for all p”.

An intermediate notion is the following: for y ∈ P_{d}, let \overline{T_{<∞}(y)}^{b} be the set of vectors x ∈ P_{d} such that there is a sequence (x_{n}) in T_{<∞}(y) tending to x, with a uniform bound on the size of the support of x_{n}. We think that a description of \overline{T_{<∞}(y)}^{b} could be related to the set of vectors which satisfy conditions (1) and (2) — but not necessarily (3) — in Conjecture 1.

There is one more consequence of our main theorem we would like to discuss. Recall that when defining catalysis, we insisted on the fact that the catalyst should be finitely-supported. Let P_{∞} ⊂ ℓ_{1} be the set of infinite-dimensional probability vectors, and for y in P_{<∞}, define the set T′(y) of (finitely supported) vectors trumped by y using infinite catalysts:

T′(y) = {x ∈ P_{<∞} s.t. ∃z ∈ P_{∞} s.t. x ⊗ z ≺ y ⊗ z}.

As shown in [3] (Section 4.3), in general T_{<∞}(y) ≠ T′(y). However, since x ∈ T′(y) implies ∥x∥_{p} ⩽ ∥y∥_{p} for all p ⩾ 1, it follows from our main theorem that \overline{T_{<∞}(y)} = \overline{T′(y)}.

6. Appendix: On Cramér’s theorem

We review here some facts from large deviations theory. A complete reference for all the material contained here is [5]. Let X be a random variable taking values in [−∞, ∞). We allow X to equal −∞ with positive probability; this is a nonstandard hypothesis. We however exclude the trivial case P(X = −∞) = 1. We write E for the expectation. We assume also that the conditional expectation E(X|X ≠ −∞) is finite. The cumulant generating function Λ_{X} of the random variable X is defined for any λ ∈ R by

Λ_{X}(λ) = log Ee^{λX}.

It is a convex function taking values in (−∞, +∞]. Its convex conjugate Λ_{X}^{∗}, sometimes called the Cramér transform, is defined as

(4)  Λ_{X}^{∗}(x) = sup_{λ∈R} λx − Λ_{X}(λ).

Note that Λ_{X} is a smooth and strictly convex function on [0, +∞]. Moreover, Λ′_{X}(0) = E(X|X ≠ −∞) and lim_{λ→+∞} Λ′_{X}(λ) = esssup(X). Consequently, for any x such that E(X|X ≠ −∞) < x < esssup(X), the supremum in (4) is attained at a unique point λ ⩾ 0. We now state Cramér’s theorem in a suitable formulation

Proposition 1. Let X be a [−∞, +∞)-valued random variable such that Λ_{X}(λ) < +∞ for any λ ⩾ 0. Let (X_{i}) be a sequence of i.i.d. copies of X. Then for any t ∈ R

lim_{n→∞} \frac{1}{n} log P(X_{1} + ⋯ + X_{n} ⩾ tn) = \begin{cases}log P(X ≠ −∞) if t ⩽ E(X|X ≠ −∞) \\ −Λ_{X}^{∗}(t) otherwise. \end{cases}

Proof. Let X̂ denote the random variable X conditioned to be finite, that is for any Borel set B ⊂ R

P(X̂ ∈ B) = \frac{1}{1 − p}P(X ∈ B),

where p = P(X = −∞). A consequence of the classical Cramér theorem ([5], Corollary 2.2.19) states that

(5)  ∀t ∈ R, lim_{n→∞} \frac{1}{n} log P(X̂_{1} + ⋯ + X̂_{n} ⩾ tn) = − inf_{s⩾t} Λ∗ ; X̂(s).

One checks that ΛX̂ = Λ_{X} − log(1 − p), and consequently

(6)  Λ∗ ; X̂ = Λ_{X}^{∗} + log(1 − p).

Note also that

(7)  P(X_{1} + ⋯ + X_{n} ⩾ tn) = (1 − p)^{n}P(X̂_{1} + ⋯ + X̂_{n} ⩾ tn).

Finally, note that the infimum on the right hand side of (5) is null for t ⩽ E(X̂) and equals Λ∗ ; X̂(t) for t > E(X̂). This follows from the fact that the convex function t ↦ Λ∗ ; X̂(t) attains its zero minimum at t = E(X̂) and is increasing for t ⩾ E(X̂). Thus, we can rewrite equation (5) as:

(8)  lim_{n→∞} \frac{1}{n} log P(X̂_{1} + ⋯ + X̂_{n} ⩾ tn) = \begin{cases}0 if t ⩽ E(X̂) \\ −Λ∗ ; X̂(t) otherwise. \end{cases}

The proposition follows from the equations (6), (7) and (8). □

References

[1] S. Bandyopadhyay, V. Roychowdhury and U. Sen Classification of nonasymptotic bipartite pure-state entanglement transformations, Phys. Rev. A, 65 (2002), 052315.

[2] R. Bhatia, Matrix Analysis. Graduate Texts in Mathematics, 169. Springer-Verlag, New York, 1997.

[3] S. K. Daftuar, Eigenvalues Inequalities in Quantum Information Processing, Ph. D. Thesis, California Institute of

technology, 2004. Available at http://resolver.caltech.edu/CaltechETD:etd-03312004-100014

[4] S. K. Daftuar and M. Klimesh, Mathematical structure of entanglement catalysis, Phys. Rev. A (3) 64 (2001), no. 4, 042314

[5] A. Dembo and O. Zeitouni, Large deviations Techniques and Applications, Second edition. Applications of Mathematics (New York), 38. Springer-Verlag, New York, 1998.

[6] R. Duan, Y. Feng, X. Li and M. Ying, Multiple-copy entanglement transformation and entanglement catalysis, Phys. Rev. A 71 (2005), 042319

[7] R. Duan, Z. Ji, Y. Feng, X. Li and M. Ying, Some issues in quantum information theory, J. Comput. Sci. & Technol. 21 (2006), no. 5, 776–789.

[8] D. Jonathan and M. B. Plenio, Entanglement-assisted local manipulation of pure quantum states, Phys. Rev. Lett. 83 (1999), no. 17, 3566–3569.

[9] M. Klimesh, Entropy measures and catalysis of bipartite quantum state transformations, extended abstract, ISIT 2004, Chicago, USA.

[10] G. Kuperberg, The capacity of hybrid quantum memory, IEEE Trans. Inform. Theory 49 (2003), 1465–1473.

[11] A. Marshall and I. Olkin, Inequalities: theory of majorization and its applications, Mathematics in Science and Engineering, 143. Academic Press Inc., New York-London, 1979

[12] T. Mitra and E. Ok, Majorization by L^{p}-Norms, preprint, available at http://homepages.nyu.edu/~eo1/

Papers-PDF/Major.pdf

[13] M. Nielsen, Conditions for a class of entanglement transformations, Phys. Rev. Lett. 83, 436 (1999).

[14] M. Nielsen, An introduction to majorization and its applications to quantum mechanics, preprint, available at

www.qinfo.org/talks/2002/maj/book.ps

[15] M. Nielsen and I. Chuang, Quantum computation and quantum information. Cambridge University Press, Cambridge, 2000.

[16] Open problems in Quantum Information Theory, available at http://www.imaph.tu-bs.de/qi/problems/ or

quant-ph/0504166

[17] G. Pólya and G. Szegö, Problems and Theorems in Analysis, Springer-Verlag, Berlin-New York, 1978.

Address : Université de Lyon, Université Lyon 1, CNRS, UMR 5208 Institut Camille Jordan, Batiment du Doyen Jean Braconnier, 43, boulevard du 11 novembre 1918, F - 69622 Villeurbanne Cedex, France

Email: aubrun@math.univ-lyon1.fr, nechita@math.univ-lyon1.fr