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
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 44,340
Through your library

References found in this work BETA

Add more references

Citations of this work BETA

Quantum Pseudo-Telepathy.Gilles Brassard, Anne Broadbent & Alain Tapp - 2005 - Foundations of Physics 35 (11):1877-1907.

Add more citations

Similar books and articles

Quantum Pseudo-Telepathy.Gilles Brassard, Anne Broadbent & Alain Tapp - 2005 - Foundations of Physics 35 (11):1877-1907.
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
Quantum Mechanics and Computation.Bart D’Hooghe & Jaroslaw Pykacz - 2004 - Foundations of Science 9 (4):387-404.
Do We Really Understand Quantum Mechanics?Franck Laloë - 2012 - Cambridge University Press.
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 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature