No-signalling-assisted zero-error capacity of quantum channels and an information theoretic interpretation of the lovász number

Runyao Duan, Andreas Winter

Research output: Contribution to journalArticleResearchpeer-review

21 Citations (Scopus)

Abstract

© 2015 IEEE. We study the one-shot zero-error classical capacity of a quantum channel assisted by quantum no-signalling correlations, and the reverse problem of exact simulation of a prescribed channel by a noiseless classical one. Quantum no-signalling correlations are viewed as two-input and twooutput completely positive and trace preserving maps with linear constraints enforcing that the device cannot signal. Both problems lead to simple semidefinite programmes (SDPs) that depend only on the Choi-Kraus (operator) space of the channel. In particular, we show that the zero-error classical simulation cost is precisely the conditional min-entropy of the Choi-Jamiozkowski matrix of the given channel. The zero-error classical capacity is given by a similar-looking but different SDP; the asymptotic zero-error classical capacity is the regularization of this SDP, and in general, we do not know of any simple form. Interestingly, however, for the class of classical-quantum channels, we show that the asymptotic capacity is given by a much simpler SDP, which coincides with a semidefinite generalization of the fractional packing number suggested earlier by Aram Harrow. This finally results in an operational interpretation of the celebrated Lovász θ function of a graph as the zero-error classical capacity of the graph assisted by quantum no-signalling correlations, the first information theoretic interpretation of the Lovász number.
Original languageEnglish
Article number7353184
Pages (from-to)891-914
JournalIEEE Transactions on Information Theory
Volume62
DOIs
Publication statusPublished - 1 Feb 2016

Keywords

  • Graph Theory
  • Quantum information
  • Zero-error information theory

Fingerprint Dive into the research topics of 'No-signalling-assisted zero-error capacity of quantum channels and an information theoretic interpretation of the lovász number'. Together they form a unique fingerprint.

Cite this