Violating the Shannon capacity of metric graphs with entanglement

DOI10.1073/PNAS.1203857110MaRDI QIDQ5170983zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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.

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

Cites work

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

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)