Quantum Lunch Location:
T-Division Conference Room, TA-3,
Building 123, Room 121
Quantum Institute: Visitor Schedule
The Quantum Lunch is regularly held on Thursdays in the Theoretical Division Conference Room, TA-3, Building 123, Room 121.
For more information, contact Diego Dalvit.
To add your name to the Quantum Lunch email list, contact Charlotte Lehman
Thursday, October 28, 2010
12:30 PM - 2:00 PM
Speaker: Aram Harrow (University of Washington)
Technical Host: Robin Blume-Kohout
TOPIC: Minimum output entropy of quantum channels is hard to approximate
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.
This is based on arXiv:1001.0017, which is joint work with Ashley Montanaro.