The computational complexity of optimally encoding a bit – Omar Fawzi (Inria, ENS Lyon)

Talk recorded at EQUIPTNT Workshop, 6. / 7. October , 2025 in Munich ▶Title: The computational complexity of optimally encoding a bit ▶Speaker: Omar Fawzi (Inria, ENS Lyon) ▶Abstract: We consider the problem of encoding a bit in a quantum system undergoing noise modeled as a quantum channel. We show that determining the optimal success probability is NP-hard. This contrasts with the classical analogue of this problem that can clearly be solved efficiently. Equivalently, we show that approximating the trace norm contraction coefficient of a quantum channel is hard. In addition, we establish a converging hierarchy of semidefinite programming upper bounds on the contraction coefficient. Based on joint work with Idris Delsol, Jan Kochanowski and Akshay Ramachandran available https://arxiv.org/abs/2507.16737. ▶ About the EQUIPTNT Workshop The theme of the workshop are recent developments at the intersection of quantum computing, complexity theory and information processing. ▶ Workshop Website: https://www.math.cit.tum.de/math/pers... MCQST ▶ Website: https://www.mcqst.de ▶ LinkedIn:   / mcqst