PIRSA:10070022 Conference

DOI10.48660/10070022

Conference/School: Random Matrix Techniques in Quantum Information - 2010

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}}
}

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.

Resources