Entanglement-assisted zero-error capacity is upper bounded by the Lovasz theta function

Abstract

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 Lovasz theta function play an important role in zero-error communication. In this paper, we show that the Lovasz theta function is an upper bound on the zero-error capacity even in the presence of entanglement between the sender and receiver.

4 pages, matches published version

Cited by in corpus (16)

• Zero-error communication via quantum channels, non-commutative graphs and a quantum Lovasz theta function
• Graph Homomorphisms for Quantum Players
• No-Signalling Assisted Zero-Error Capacity of Quantum Channels and an Information Theoretic Interpretation of the Lovasz Number
• Semidefinite programming relaxations for quantum correlations
• A linear program for the finite block length converse of Polyanskiy-Poor-Verdú via non-signalling codes
• Entanglement can increase asymptotic rates of zero-error classical communication over classical channels
• A Generalization of Kochen-Specker Sets Relates Quantum Coloring to Entanglement-Assisted Channel Capacity
• Bounds on entanglement assisted source-channel coding via the Lovasz theta number and its variants
• A new property of the Lovász number and duality relations between graph parameters
• Entanglement-assisted zero-error source-channel coding
• Separation between quantum Lovász number and entanglement-assisted zero-error classical capacity
• Entanglement can completely defeat quantum noise
• On optimal entanglement assisted one-shot classical communication
• Multi-party zero-error classical channel coding with entanglement
• Activated zero-error classical communication over quantum channels assisted with quantum no-signalling correlations
• On exact counting and quasi-quantum complexity