Jan Kochanowski

We show that approximating the trace norm contraction coefficient of a quantum channel within a constant factor is NP-hard. Equivalently, this shows that determining the optimal success probability for encoding a bit in a quantum system undergoing noise is NP-hard. This contrasts with the classical analogue of this problem that can clearly be solved efficiently. Our hardness results also hold for deciding if the contraction coefficient is equal to 1. As a consequence, we show that deciding if a non-commutative graph has an independence number of at least 2 is NP-hard. In addition, we establish a converging hierarchy of semidefinite programming upper bounds on the contraction coefficient.

We study the complexity of computing the mixed Schatten $\|\Phi\|_{q\to p}$ 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 $\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 $\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$.

Quantum information processing is limited, in practice, to efficiently implementable operations. This motivates the study of quantum divergences and entropies that preserve their operational meaning while faithfully capturing computational constraints. In this joint submission, we introduce a mathematical framework for computational quantum information theory from which computational divergences and established computational entropies naturally arise. Within this framework, we define a computational max-divergence and computational measured Rényi divergences. We relate these quantities to efficient hypothesis testing and use them to analyze computational resource theories such as entanglement. We further connect the new computational max-divergence to the previously established computational min-entropy and computational hypothesis testing relative entropy. In particular, we show that the computational max-divergence serves as a parent quantity for the computational min-entropy, thereby endowing the computational max-divergence with an operational meaning. Moreover, we prove that the computational hypothesis testing relative entropy is approximately characterized by a smoothed version of the computational max-divergence. Together, these results extend well-known information-theoretic relationships to the computational setting and unify several operationally-motivated computational quantities.