Physics – Quantum Physics
Scientific paper
2009-07-21
Physics
Quantum Physics
Survey paper, 63 pages LaTeX. A reformatted version will appear in Reviews of Modern Physics
Scientific paper
Quantum information processing is the emerging field that defines and realizes computing devices that make use of quantum mechanical principles, like the superposition principle, entanglement, and interference. In this review we study the information counterpart of computing. The abstract form of the distributed computing setting is called communication complexity. It studies the amount of information, in terms of bits or in our case qubits, that two spatially separated computing devices need to exchange in order to perform some computational task. Surprisingly, quantum mechanics can be used to obtain dramatic advantages for such tasks. We review the area of quantum communication complexity, and show how it connects the foundational physics questions regarding non-locality with those of communication complexity studied in theoretical computer science. The first examples exhibiting the advantage of the use of qubits in distributed information-processing tasks were based on non-locality tests. However, by now the field has produced strong and interesting quantum protocols and algorithms of its own that demonstrate that entanglement, although it cannot be used to replace communication, can be used to reduce the communication exponentially. In turn, these new advances yield a new outlook on the foundations of physics, and could even yield new proposals for experiments that test the foundations of physics.
Buhrman Harry
Cleve Richard
Massar Serge
Wolf Ronald de
No associations
LandOfFree
Non-locality and Communication Complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Non-locality and Communication Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Non-locality and Communication Complexity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-175531