The Shannon capacity of a graph G is the maximum asymptotic rate at which messages can be sent with zero probability of error through a noisy channel with confusability graph G. This extensively studied graph parameter disregards the fact that on atomic scales, nature behaves in line with quantum mechanics. Entanglement, arguably the most counterintuitive feature of the theory, turns out to be a useful resource for communication across noisy channels. Recently [Leung D, Mančinska L, Matthews W, Ozols M, Roy A (2012) Commun Math Phys 311:97–111], two examples of graphs were presented whose Shannon capacity is strictly less than the capacity attainable if the sender and receiver have entangled quantum systems. Here, we give natural, possibly infinite, families of graphs for which the entanglement-assisted capacity exceeds the Shannon capacity.
graph theory, information theory, quantum information, independence number, orthonormal representation
Graph representations (geometric and intersection representations, etc.) (msc 05C62), Quantum computation (msc 81P68), Communication, information (msc 94Axx)
Life Sciences (theme 5), Logistics (theme 3), Logistics (theme 3)
National Academy of Sciences
Proceedings of the National Academy of Sciences of the United States of America
Quantum Computer Science
Published online before print December 24, 2012, doi: 10.1073/pnas.1203857110 PNAS December 24, 2012 201203857
Algorithms and Complexity

Briët, J, Buhrman, H.M, & Gijswijt, D. (2012). Violating the Shannon capacity of metric graphs with entanglement. Proceedings of the National Academy of Sciences of the United States of America. doi:10.1073/pnas.1203857110