Quantum computational complexity: Difference between revisions
Content deleted Content added
why was this article entered, and then immediately deleted again? reverting, until more is learned. |
redirecting to computational complexity; which includes quantum classes |
||
| Line 1: | Line 1: | ||
#REDIRECT [computational complexity theory] |
|||
The notion of communication complexity (CC) was introduced by Yao |
|||
in 1979, who investigated the following problem involving two |
|||
separated parties (Alice and Bob). Alice receives a n-bit string x |
|||
and Bob another n-bit string y, and the goal is for one of them |
|||
(say Bob) to compute a certain function f(x,y) with |
|||
the least amount of communication between them. Note that here we are |
|||
not concerned about the number of computational steps, or the size of |
|||
the computer memory used. Communication complexity tries to quantify |
|||
the amount of communication required for such distributed |
|||
computations. |
|||
Of course they can always succeed by having Alice send her whole |
|||
n-bit string to Bob, who then computes the function, but the idea |
|||
here is to find clever ways of calculating f with less than n$ bits |
|||
of communication. |
|||
This abstract problem is relevant in many contexts: in |
|||
VLSI circuit design, for example, one wants to minimize energy |
|||
use by decreasing the amount of electric signals required between the |
|||
different components during a distributed computation. The problem is |
|||
also relevant in the study of data structures, and in the optimization of computer networks. For a survey of the field, see the book by Kushilevitz and Nisan. |
|||
=== Quantum communication complexity === |
|||
Quantum communication complexity tries to quantify the |
|||
communication reduction possible by using quantum effects during a |
|||
distributed computation. |
|||
At least three quantum generalizations of CC have been |
|||
proposed; for a survey see the suggested text by G. Brassard. |
|||
The first one is the |
|||
qubit-communication model, where the parties can use quantum |
|||
communication instead of classical communication, for example |
|||
by exchanging photons through an optical fiber. |
|||
In a second model the communication is still performed with |
|||
classical bits, but the parties are allowed to manipulate an unlimited |
|||
supply of quantum entangled states as part of their protocols. By doing |
|||
measurements on their entangled states, the parties can save on classical |
|||
communication during a distributed computation. |
|||
The third model involves access to previously shared entanglement in |
|||
addition to qubit communication, and is the least explored of the |
|||
three quantum models. |
|||
References: |
|||
* Kushilevitz, E. and Nisan, N. Communication complexity. Cambridge University Press, 1997. |
|||
* Brassard, G. Quantum communication complexity: a survey. http://arxiv.org/abs/quant-ph/0101005 |
|||
Revision as of 03:48, 26 April 2002
- REDIRECT [computational complexity theory]