Birkhoff's theorem states that every doubly stochastic map is a convex combination of permutation matrices. The quantum analog of a stochastic map is a quantum channel, which is a completely positive trace preserving map taking Hermitian matrices to Hermitian matrices. One can ask whether Birkhoff's theorem generalizes to quantum channels. The quantum analog of a doubly stochastic map is a unital channel, i.e. a channel which maps the identity matrix to the identity matrix. The natural generalization of Birkhoff's theorem to quantum channels would be the statement that every unital channel is a convex combination of unitaries. This is false. The weaker “asymptotic Birkhoff conjecture” is that as $n\to\infty$, the tensor product of $n$ copies of a quantum channel is approximated well by a convex combination of unitaries. We show that this is also false, and give a classification of unital maps related to this conjecture.