A Caltech Library Service

Entanglement-assisted zero-error capacity is upper-bounded by the Lovász ϑ function

Beigi, Salman (2010) Entanglement-assisted zero-error capacity is upper-bounded by the Lovász ϑ function. Physical Review A, 82 (1). Art. No. 010303. ISSN 1050-2947.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


The zero-error capacity of a classical channel is expressed in terms of the independence number of some graph and its tensor powers. This quantity is hard to compute even for small graphs such as the cycle of length seven, so upper bounds such as the Lovász theta function play an important role in zero-error communication. In this paper, we show that the Lovász theta function is an upper bound on the zero-error capacity even in the presence of entanglement between the sender and receiver.

Item Type:Article
Related URLs:
Additional Information:© 2010 The American Physical Society. Received 29 March 2010; published 26 July 2010. The author is grateful to the unknown referee whose comments helped to improve the presentation of the paper. This work has been supported in part by National Science Foundation under Grant No. PHY-0803371 and by National Security Agency/Army Research Office under Grant No. W911NF-09-1-0442.
Funding AgencyGrant Number
National Security Agency/Army Research OfficeW911NF-09-1-0442
Issue or Number:1
Classification Code:PACS: 03.67.Ac, 03.67.Bg, 89.70.Kn
Record Number:CaltechAUTHORS:20100816-152009414
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:19450
Deposited By: Tony Diaz
Deposited On:16 Aug 2010 23:19
Last Modified:03 Oct 2019 01:57

Repository Staff Only: item control page