Violating the Shannon capacity of metric graphs with entanglement

DOI10.1073/PNAS.1203857110zbMATH Open1292.81015arXiv1207.1779OpenAlexW2130940102WikidataQ37353214 ScholiaQ37353214MaRDI QIDQ5170983FDOQ5170983

Authors: Jop Briët, Harry Buhrman, Dion Gijswijt 

Publication date: 25 July 2014

Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)

Abstract: 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, Mancinska, Matthews, Ozols and Roy [Comm. Math. Phys. 311, 2012] presented two examples of graphs whose Shannon capacity is strictly less than the capacity attainable if the sender and receiver have entangled quantum systems. Here we give new, possibly infinite, families of graphs for which the entangled capacity exceeds the Shannon capacity.

Full work available at URL: https://arxiv.org/abs/1207.1779

Recommendations

• On the Shannon capacity of a graph
• Entanglement-assisted capacity of a quantum channel and the reverse Shannon theorem
• The Shannon capacity of a union
• On entanglement-assisted classical capacity
• The classical capacity achievable by a quantum channel assisted by limited entanglement

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Distance in graphs (05C12) Quantum coherence, entanglement, quantum correlations (81P40) Quantum information, communication, networks (quantum-theoretic aspects) (81P45)

Cites Work

• Entanglement can increase asymptotic rates of zero-error classical communication over classical channels
• Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?
• Intersection theorems with geometric consequences
• Entanglement-assisted capacity of a quantum channel and the reverse Shannon theorem
• Coloring an Orthogonality Graph

Cited In (4)

• Quantum homomorphisms
• Sandwich theorems and capacity bounds for non-commutative graphs
• Bounds on entanglement assisted source-channel coding via the Lovász \(\vartheta\) number and its variants
• Exclusivity structures and graph representatives of local complementation orbits

This page was built for publication: Violating the Shannon capacity of metric graphs with entanglement

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5170983)