Detecting mixed-unitary quantum channels is NP-hard

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 Φ is a mixed-unitary channel. This hardness result holds even under the assumption that Φ is not within an inverse-polynomial distance (in the dimension of the space upon which Φ acts) of the boundary of the mixed-unitary channels.