PIRSA:10070022

Minimum output entropy of quantum channels is hard to approximate

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

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

          @misc{ pirsa_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},
            year = {2010},
            month = {jul},
            note = {PIRSA:10070022 see, \url{https://pirsa.org}}
          }

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

Talk numberPIRSA:10070022
DOI10.48660/10070022
Collection
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.