Complexity of mixed Schatten norms of quantum maps

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