Computational Aspects of the Trace Norm Contraction Coefficient
The paper proves that approximating a quantum channel's trace norm contraction coefficient within a constant factor is NP-hard, which means determining the optimal success probability for encoding bits in noisy quantum systems is also NP-hard. It establishes that deciding if the contraction coefficient equals 1 (perfect bit preservation) is hard and provides a converging hierarchy of semidefinite programming bounds to detect when this coefficient is less than 1.