  A quantum channel is said to be a mixed-unitary channel if it can be
expressed as a convex combination of unitary channels. We prove that, given the
Choi representation of a quantum channel, it is NP-hard with respect to
polynomial-time Turing reductions to determine whether or not that channel is a
mixed-unitary channel. This hardness result holds even under the assumption
that the channel is not within an inverse-polynomial distance (in the dimension
of the space upon which it acts) of the boundary of the mixed-unitary channels.
