Minimum output entropy of quantum channels is hard to approximate Speaker(s): Aram Harrow
Abstract: The headline result of this talk is that, based on plausible complexitytheoretic assumptions, many properties of quantum channels are computationally hard to approximate. These hardtocompute properties include the minimum output entropy, the 1>p norms of channels, and their "regularized" versions, such as the classical capacity.
The proof of this claim has two main ingredients. First, I show how many channel problems can be fruitfully recast in the language of twoprover quantum MerlinArther games (which I'll define during the talk). Second, the main technical contribution is a procedure that takes two copies of a multipartite quantum state and estimates whether or not it is close to a product state.
This is based on arXiv:1001.0017, which is joint work with Ashley Montanaro.
Date: 06/07/2010  3:00 pm
