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)
December 24, 2012
110 (48) 19227-19232

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.

Continue Reading

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

The cover image for PNAS Vol.110; No.48
Proceedings of the National Academy of Sciences
Vol. 110 | No. 48
November 26, 2013
PubMed: 23267109

Classifications

Submission history

Published online: December 24, 2012
Published in issue: November 26, 2013

Keywords

  1. graph theory
  2. information theory
  3. quantum information
  4. independence number
  5. orthonormal representation

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

Affiliations

Centrum Wiskunde & Informatica, 1098 XG, Amsterdam, The Netherlands;
Harry Buhrman
Centrum Wiskunde & Informatica, 1098 XG, Amsterdam, The Netherlands;
Institute for Logic, Language and Computation, University of Amsterdam, 1098 XH, Amsterdam, The Netherlands; and
Dion Gijswijt
Centrum Wiskunde & Informatica, 1098 XG, Amsterdam, The Netherlands;
Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, 2600 GA, Delft, The Netherlands

Notes

1
To whom correspondence should be addressed. E-mail: [email protected].
Author contributions: J.B. and H.B. designed research; J.B., H.B., and D.G. performed research; J.B., H.B., and D.G. contributed new reagents/analytic tools; and J.B., H.B., and D.G. wrote the paper.

Competing Interests

The authors declare no conflict of interest.

Metrics & Citations

Metrics

Note: The article usage is presented with a three- to four-day delay and will update daily once available. Due to ths delay, usage data will not appear immediately following publication. Citation information is sourced from Crossref Cited-by service.


Altmetrics

Citations

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 PDF

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Personal login Institutional Login

    Recommend to a librarian

    Recommend PNAS to a Librarian

    Purchase options

    Purchase this article to access the full text.

    Single Article Purchase

    Violating the Shannon capacity of metric graphs with entanglement
    Proceedings of the National Academy of Sciences
    • Vol. 110
    • No. 48
    • pp. 19175-19651

    Figures

    Tables

    Media

    Share

    Share

    Share article link

    Share on social media