Thursday, October 28, 201012:30 PM - 2:00 PMTheoretical Division Conference Room, TA-3, Building 123, Room 121. |
Minimum output entropy of quantum channels is hard to approximate
Aram HarrowUniversity of Washington
The headline result of this talk is that, based on plausible complexity-theoretic assumptions, many properties of quantum channels are computationally hard to approximate. These hard-to-compute 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 two-prover quantum Merlin-Arther 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.
Host: Robin Blume-Kohout, firstname.lastname@example.org