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.
Additional Metadata
Keywords graph theory, information theory, quantum information, independence number, orthonormal representation
MSC Graph representations (geometric and intersection representations, etc.) (msc 05C62), Quantum computation (msc 81P68), Communication, information (msc 94Axx)
THEME Life Sciences (theme 5), Logistics (theme 3), Logistics (theme 3)
Publisher National Academy of Sciences
Persistent URL dx.doi.org/10.1073/pnas.1203857110
Journal Proceedings of the National Academy of Sciences of the United States of America
Project Quantum Computer Science
Note Published online before print December 24, 2012, doi: 10.1073/pnas.1203857110 PNAS December 24, 2012 201203857
Citation
Briët, J, Buhrman, H, & 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