Total: 1
We study the complexity of computing the mixed Schatten ‖ norms of linear maps \Phi between matrix spaces. When \Phi is completely positive, we show that \| \Phi \|_{q \to p} can be computed efficiently when q \geq p. The regime q \geq p is known as the non-hypercontractive regime and is also known to be easy for the mixed vector norms \ell_{q} \to \ell_{p} [Boyd, 1974]. However, even for entanglement-breaking completely-positive trace-preserving maps \Phi, we show that computing \| \Phi \|_{1 \to p} is \mathsf{NP}-complete when p>1. Moving beyond the completely-positive case and considering \Phi to be difference of entanglement breaking completely-positive trace-preserving maps, we prove that computing \| \Phi \|^+_{1 \to 1} is \mathsf{NP}-complete. In contrast, for the completely-bounded (cb) case, we describe a polynomial-time algorithm to compute \|\Phi\|_{cb,1\to p} and \|\Phi\|^+_{cb,1\to p} for any linear map \Phi and p\geq1.