Problem 30: Asymptotic Version of Birkhoff's Theorem

From OpenQIProblemsWiki
Jump to: navigation, search


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 [LS,GW] 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 [math]d_B(T)[/math] 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 [math]d_B(T^{\otimes n})[/math] goes to zero as [math]n\to\infty[/math].
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.


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 [GW]. For the asymptotic capacity under such corrections an explicit coding formula exists [W,MVW], which suggests, but not quite proves the asymptotic validity of Birkhoffs Theorem in the above sense.

Partial Results



[LS] L. J. Landau and R. F. Streater, J. Linear Alg. and Appl. 193, 107-127 (1993).
[GW] M. Gregoratti and R.F. Werner, J. Mod. Opt. 50, 915 (2002) and quant-ph/0209025.
[W] A. Winter, quant-ph/0507045.
[MVW] J. A. Smolin, F. Verstraete, and A. Winter, quant-ph/0505038.