PIRSA:10070022

Minimum output entropy of quantum channels is hard to approximate

APA

Harrow, A. (2010). Minimum output entropy of quantum channels is hard to approximate. Perimeter Institute for Theoretical Physics. https://pirsa.org/10070022

MLA

Harrow, Aram. Minimum output entropy of quantum channels is hard to approximate. Perimeter Institute for Theoretical Physics, Jul. 06, 2010, https://pirsa.org/10070022

BibTex

          @misc{ scivideos_PIRSA:10070022,
            doi = {10.48660/10070022},
            url = {https://pirsa.org/10070022},
            author = {Harrow, Aram},
            keywords = {},
            language = {en},
            title = {Minimum output entropy of quantum channels is hard to approximate},
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2010},
            month = {jul},
            note = {PIRSA:10070022 see, \url{https://scivideos.org/pirsa/10070022}}
          }
          

Aram Harrow Massachusetts Institute of Technology (MIT) - Department of Physics

Talk numberPIRSA:10070022
Talk Type Conference

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.