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

Abstract
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.