Cite this problem as Problem 30.

Problem

A classical result of Birkhoff states that a doubly stochastic matrix (positive elements, and all rows and columns add to 1) is a convex combination of permutation matrices. In the quantum context, doubly stochastic matrices become doubly stochastic channels, i.e. completely positive maps preserving both the trace and the identity. In the classical case, the permutations are the invertible elements, corresponding in the quantum case to the unitarily implemented channels. It is well-known [1][2] that the analog of Birkhoff’s Theorem fails in the quantum case: in other words, there exist doubly stochastic quantum channels which can not be written as a convex combination of unitary channels. However, large tensor powers of a channel may be easier to represent in this way, because one need not use only product unitaries in the decomposition. Let us denote, for any doubly stochastic channel T, by the Birkhoff defect, defined as the cb-norm distance from T to the convex hull of the unitarily implemented channels. The problem is to decide whether goes to zero as .

This would be a very strong result. A weaker but still interesting version arises by Jamiolkowski dualization: Consider a bipartite state on two systems of the same dimension, whose restrictions are both equal to the chaotic state. Show that high tensor powers of this state are well approximated in trace norm by convex combinations of maximally entangled pure states.

Background

Channels which are convex combinations of unitarily implemented ones have the property that they allow complete correction, given a suitable feedback of classical information from the environment [2]. For the asymptotic capacity under such corrections an explicit coding formula exists [3][4], which suggests, but not quite proves the asymptotic validity of Birkhoffs Theorem in the above sense.

Solution

The problem was solved by Uffe Haagerup and Magdalena Musat [5,6]. The key idea was to look at an intermediate class of operations between doubly stochastic and Birkhoff (i.e., convex combination of reversible) channels. In [5] this class is called “factorizable maps” and it has been considered in a QI context under the name “noisy operations”. Roughly speaking it is the class of operations one can get by coupling the input system to a maximally mixed ancillary one, executing a unitary rotation on the combined system and tracing out the ancilla. Clearly such operations are doubly stochastic. Also, if some tensor power of a channel is Birkhoff, we can take all but one of the input systems as an ancilla, and find that the channel must be a factorizable map. With a similar argument it is clear that tensoring multiple copies will not make a non-factorizable map factorizable. Therefore, for this intermediate class there is no need to go to higher tensor powers, which considerably simplifies the problem. Indeed, in [5] we find some explicit criteria for factorizability, and examples of non-factorizable doubly stochastic channels, as required by the problem.

References

[1] L. J. Landau and R. F. Streater, J. Linear Alg. and Appl. 193, 107-127 (1993).

[2] M. Gregoratti and R.F. Werner, J. Mod. Opt. 50, 915 (2002) and quant-ph/0209025.

[3] A. Winter, quant-ph/0507045.

[4] J. A. Smolin, F. Verstraete, and A. Winter, quant-ph/0505038.

[5] U. Haagerup and M. Musat, Commun. Math. Phys. 303, 555 (2011) and arxiv/1009.0778

[6] U. Haagerup and M. Musat, Commun. Math. Phys. 338, 721 (2015) and arXiv/1408.6476