Quantum Communication Complexity
Foundations of Physics 33 (11):1593-1616 (2003)
Abstract |
Can quantum communication be more efficient than its classical counterpart? Holevo's theorem rules out the possibility of communicating more than n bits of classical information by the transmission of n quantum bits—unless the two parties are entangled, in which case twice as many classical bits can be communicated but no more. In apparent contradiction, there are distributed computational tasks for which quantum communication cannot be simulated efficiently by classical means. In some cases, the effect of transmitting quantum bits cannot be achieved classically short of transmitting an exponentially larger number of bits. In a similar vein, can entanglement be used to save on classical communication? It is well known that entanglement on its own is useless for the transmission of information. Yet, there are distributed tasks that cannot be accomplished at all in a classical world when communication is not allowed, but that become possible if the non-communicating parties share prior entanglement. This leads to the question of how expensive it is, in terms of classical communication, to provide an exact simulation of the spooky power of entanglement
|
Keywords | Bell's theorem communication complexity distributed computation entanglement simulation pseudo-telepathy spooky communication |
Categories | (categorize this paper) |
DOI | 10.1023/A:1026009100467 |
Options |
![]() ![]() ![]() ![]() ![]() |
Download options
References found in this work BETA
On the Einstein Podolsky Rosen Paradox.J. S. Bell - 2004 [1964] - In Speakable and Unspeakable in Quantum Mechanics. Cambridge University Press. pp. 14--21.
Citations of this work BETA
Objective Computation Versus Subjective Computation.Nir Fresco - 2015 - Erkenntnis 80 (5):1031-1053.
Quantum Pseudo-Telepathy.Gilles Brassard, Anne Broadbent & Alain Tapp - 2005 - Foundations of Physics 35 (11):1877-1907.
Communication Complexity as a Principle of Quantum Mechanics.Adán Cabello - 2006 - Foundations of Physics 36 (4):512-525.
Similar books and articles
Quantum Pseudo-Telepathy.Gilles Brassard, Anne Broadbent & Alain Tapp - 2005 - Foundations of Physics 35 (11):1877-1907.
Communication Complexity as a Principle of Quantum Mechanics.Adán Cabello - 2006 - Foundations of Physics 36 (4):512-525.
The Subtleties of Entanglement and its Role in Quantum Information Theory.Rob Clifton - 2001 - Proceedings of the Philosophy of Science Association 2002 (3):S150-S167.
A Quantum Computer Only Needs One Universe.A. M. Steane - 2003 - Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 34 (3):469-478.
A Simple Model of Secure Public Communication.Hannu Vartiainen - 2009 - Theory and Decision 67 (1):101-122.
On the Physical Explanation for Quantum Computational Speedup.Michael E. Cuffaro - 2013 - Dissertation, The University of Western Ontario
Information Theories with Adversaries, Intrinsic Information, and Entanglement.Karol Horodecki, Michał Horodecki, Pawel Horodecki & Jonathan Oppenheim - 2005 - Foundations of Physics 35 (12):2027-2040.
Quantum Mechanics and Computation.Bart D’Hooghe & Jaroslaw Pykacz - 2004 - Foundations of Science 9 (4):387-404.
Hiding Quantum Data.David P. DiVincenzo, Patrick Hayden & Barbara M. Terhal - 2003 - Foundations of Physics 33 (11):1629-1647.
Quantum Information in a Distributed Apparatus.Subhash C. Kak - 1998 - Foundations of Physics 28 (6):1005-1012.
A Classical Analogy of Entanglement.Robert J. C. Spreeuw - 1998 - Foundations of Physics 28 (3):361-374.
Analytics
Added to PP index
2013-11-22
Total views
29 ( #300,746 of 2,271,604 )
Recent downloads (6 months)
1 ( #825,223 of 2,271,604 )
2013-11-22
Total views
29 ( #300,746 of 2,271,604 )
Recent downloads (6 months)
1 ( #825,223 of 2,271,604 )
How can I increase my downloads?
Downloads