Violating the Shannon capacity of metric graphs with entanglement
Edited by Robion C. Kirby, University of California, Berkeley, CA, and approved November 27, 2012 (received for review May 1, 2012)
Correction
February 14, 2013
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 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.
Acknowledgments
J.B. thanks Oded Regev for discussions at Ecole Normale Supérieur Paris and for comments on the manuscript. We thank Monique Laurent and David García Soriano for discussions and Lex Schrijver for literature pointers. Work supported by the European Union Seventh Framework Programme Grant QCS (to J.B. and H.B.).
References
1
C Shannon, The zero error capacity of a noisy channel. IRE Trans Inf Theory 2, 8–19 (1956).
2
A Einstein, P Podolsky, N Rosen, Can quantum-mechanical description of physical reality be considered complete? Phys Rev 47, 777–780 (1935).
3
JS Bell, On the Einstein-Podolsky-Rosen paradox. Physics 1, 195–200 (1964).
4
A Aspect, P Grangier, G Roger, Experimental tests of realistic local theories via Bell’s theorem. Phys Rev Lett 47, 460–463 (1981).
5
TS Cubitt, D Leung, W Matthews, A Winter, Improving zero-error classical communication with entanglement. Phys Rev Lett 104, 230503 (2010).
6
L Mančinska, G Scarpa, S Severini, A generalization of Kochen-Specker sets relates quantum coloring to entanglement-assisted channel capacity. Available at http://arxiv.org/abs/1207.1111. (2012).
7
CH Bennett, PW Shor, JA Smolin, AV Thapliyal, Entanglement-assisted capacity of a quantum channel and the reverse Shannon theorem. IEEE Trans Inf Theory 48, 2637–2655 (2002).
8
D Leung, L Mančinska, W Matthews, M Ozols, A Roy, Entanglement can increase asymptotic rates of zero-error classical communication over classical channels. Commun Math Phys 311, 97–111 (2012).
9
G Brassard, R Cleve, A Tapp, Cost of exactly simulating quantum entanglement with classical communication. Phys Rev Lett 83, 1874–1877 (1999).
10
D Avis, J Hasegawa, Y Kikuchi, Y Sasaki, A quantum protocol to win the graph colouring game on all Hadamard graphs. IEICE Trans Fundam Electron Commun Comput Sci 89, 1378–1381 (2006).
11
PJ Cameron, A Montanaro, MW Newman, S Severini, A Winter, On the quantum chromatic number of a graph. Electron J Comb 14, 1 (2007).
12
CD Godsil, MW Newman, Coloring an orthogonality graph. SIAM J Discrete Math 22, 683 (2008).
13
P Frankl, V Rödl, Forbidden intersections. Trans Am Math Soc 300, 259–286 (1987).
14
U Scarpis, Sui determinanti di valore massimo. Rend, Reale Istituto Lombardo di Scienze e Lettere 31, 1441–1446 (1898).
15
REAC Paley, On orthogonal matrices. J Math Phys 12, 311–320 (1933).
16
MA Nielsen, IL Chuang Quantum Computation and Quantum Information (Cambridge Univ Press, New York, 2000).
17
JL Alperin, RB Rowen, Groups and representations. Graduate Texts in Mathematics, Number 162 (Springer, New York). (1995).
18
W Haemers, An upper bound for the Shannon capacity of a graph. Colloq Math. Soc János Bolyai 25, 267–272 (1978).
19
P Frankl, RM Wilson, Intersection theorems with geometric consequences. Combinatorica 1, 357–368 (1981).
20
R Lidl, H Niederreiter, (1983) Finite fields. Encyclopedia of Mathematics and Its Applications, ed Rota G-C (Addison-Wesley, Reading, MA), Vol 20.
Information & Authors
Information
Published in
Classifications
Submission history
Published online: December 24, 2012
Published in issue: November 26, 2013
Keywords
Acknowledgments
J.B. thanks Oded Regev for discussions at Ecole Normale Supérieur Paris and for comments on the manuscript. We thank Monique Laurent and David García Soriano for discussions and Lex Schrijver for literature pointers. Work supported by the European Union Seventh Framework Programme Grant QCS (to J.B. and H.B.).
Notes
*We stress that in our definition orthogonality corresponds to adjacency. Some authors prefer to demand orthogonality for nonadjacent vertices instead.
†Buhrman H, Cleve R, Wigderson A (1998) Quantum vs. classical communication and computation. Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC 1998), pp 63–68.
‡
Hence the symbol ⊠.
This article is a PNAS Direct Submission.
Authors
Competing Interests
The authors declare no conflict of interest.
Metrics & Citations
Metrics
Altmetrics
Citations
Cite this article
Violating the Shannon capacity of metric graphs with entanglement, Proc. Natl. Acad. Sci. U.S.A.
110 (48) 19227-19232,
https://doi.org/10.1073/pnas.1203857110
(2013).
Copied!
Copying failed.
Export the article citation data by selecting a format from the list below and clicking Export.
Cited by
Loading...
View Options
View options
PDF format
Download this article as a PDF file
DOWNLOAD PDFLogin options
Check if you have access through your login credentials or your institution to get full access on this article.
Personal login Institutional LoginRecommend to a librarian
Recommend PNAS to a LibrarianPurchase options
Purchase this article to access the full text.