Catalytic majorization

Cite this problem as Problem 4.


With a Theorem by Nielsen [1], we have a completely explicit criterion to decide, when one pure bipartite state can be converted to another such state, using only local quantum operations and classical communication. Using Nielsen’s criterion one can show [2] that the following strange situation can happen:

state A cannot be converted to state B, but A\otimes C  can be converted to B\otimes C, where C is a suitably chosen entangled state, the “catalyst”.

The problem is to give a similarly efficient criterion to decide which pure bipartite states can be converted into each other using a catalyst.


Here is Nielsen’s criterion, which is a surprisingly direct rendering of the intuition that a “more entangled” pure state has a “more mixed” restriction. Thus A can be converted to B if and only if the eigenvalue sequence of the restriction of A is more mixed than that of B in the sense of majorization of probability vectors [3]. We say that one probability vector p=(p_1,\ldots,p_n) is ”more mixed” than another, q=(q_1,\ldots,q_n) in the sense of majorization, if one and hence all of the following equivalent statements hold:

*For all k:\quad \sum_{i> k} p_i \le \sum_{i> k} q_i, provided both p and q are first brought into decreasing order.

*There is a doubly stochastic matrix D (positive entries, sum of all rows and all columns = 1) such that p=D q.

*For every convex function f : \mathbb{R}\rightarrow \mathbb{R}: \quad \sum_i f(p_i) \le \sum_i f(q_i)

The above problem can be rephrased completely in this context of majorization of classical probability vectors, since tensoring pure bipartite states means again tensoring of probability vectors for the eigenvalues of the reduced density operators. Thus we would like to characterize the order relation “catalytic majorization”:

*For some r, (p\otimes r) is more mixed than (q\otimes r) in the sense of majorization.

There is some further literature on the use of majorization for the characterization of pure state entanglement [4], [5], [6], [7] and on catalysis [8] that may be useful.

Partial Results

  • Daftuar and Klimesh have shown that the dimension of the required catalyst is in general unbounded.
  • Recently, considerable progress towards the solution of the problem has been made with several papers presenting new results in 2007. Aubrun and Nechita [9]. For a given probability vector y, this paper characterizes a certain \ell_1 closure of the set of vectors x that are catalytically majorized by y. The authors make the case that this result contains the characteristics of the catalytic majorization relation that are most relevant to the physics of quantum state transformations under entanglement-assisted LOCC (ELOCC). However a subtlety arises due to the nature of the set of infinite component probability vectors.
  • In the same year Matthew Klimesh presented a more complete write up [10] of is proof sketch from 2004 [11]. Some of the steps are still in a fairly rough outline form, but the essential ideas should (mostly) be there. The main result is captured in Theorem 2:

Let x=(x_1,...,x_d) and y=(y_1,...,y_d) be d-dimensional probability vectors. Suppose that x and y do not contain components equal to 0 and that x\neq y. Then x\prec_T y if and only if f_r(x)< f_r(y) for all real r. Here

  f_r(x) = \left\{ \begin{array}{ll}  \ln\sum_{i=1}^d x_i^r \; for \; r>1 \; and \; r<0\\  \sum_{i=1}^d x_i \ln x_i \; for \; r=1\\  -\ln \sum_{i=1}^d x_i^r \; for \; 0< r<1\\  -\sum_{i=1}^d x_i \ln x_i \; for \; r=0  \end{array} \right.

  • Shortly before, S. Turgut proposed the proof of a very similar theorem[12] which can be formulated as: For two n-element sequences of non-negative numbers x and y such that x has non-zero elements and the sequences are distinct (i.e., x^{\uparrow}\neq y^{\uparrow}), the relation x \prec_T y is equivalent to the following three inequalities

(1)   \begin{alignat*}{4} A_{\nu}(x) && > && A_{\nu}(y) ,  \nu \in (-8, 1)\\ A_{\nu}(x) && < && A_{\nu}(y) ,  \nu \in (1,+8) \\ \sigma(x) && > && \sigma(y) \\ \end{alignat*}

where all inequalities are strict.

It seems likely that the above results will lead to a complete solution but independent checks for hidden subtleties that may make the above results incomplete are still required.


[1] M. A. Nielsen, Phys. Rev. Lett. 83, 436-439 (1999), quant-ph/9811053. The original proof in this paper can be simplified considerably.

[2] D. Jonathan and M. B. Plenio, Phys. Rev. Lett. 83, 3566-3569 (1999), quant-ph/9905071.

[3] We have avoided the use of a comparison symbol, or the terminology “p is majorized by q”, because there are different conventions in the literature. There is a rich literature on the subject, starting with the still recommended classic G. H. Hardy, J. E. Littlewood, and G. Polya, Inequalities, Cambridge University Press (1934). Further standard references are A. W. Marshal and I. Olkin, Inequalities: Theory of Majorization and Its Applications, Academic Press (1979) and, in the quantum context, R. Bhatia, Matrix Analysis, Springer (1996).

[4] G. Vidal, Phys. Rev. Lett. 83, 1046-1049 (1999), quant-ph/9902033.

[5] D. Jonathan and M. B. Plenio, Phys. Rev. Lett. 83, 1455-1458 (1999), quant-ph/9903054.

[6] G. Vidal, D. Jonathan, and M. A. Nielsen, Phys. Rev. A 62, 012304 (2000), quant-ph/9910099.

[7] M. Nielsen, Physical Review A 61, 064301 (2000), quant-ph/0008073 (2000).

[8] J. Eisert and M. Wilkens, Phys. Rev. Lett. 85, 437-440 (2000), quant-ph/9912080.

[9] G. Aubrun and I. Nechita, Catalytic Majorization and p Norms, quant-ph/0702153.

[10] M. Klimesh, Inequalities that Collectively Completely Characterize the Catalytic Majorization Relation, quant-ph/0709.3680.

[11] M. Klimesh, Entropy Measures and Catalysis of Bipartite Quantum State Transformations, Proc. 2004 International Symposium on Information Theory (ISIT 2004), June 27-July 2, 2004, Page 357.

[12] S. Turgut, Necessary and Sufficient Conditions for the Trumping Relation, quant-ph/0707.0444.