Quantum communication and complexity.
In the setting of communication complexity, two distributed parties want to compute a function depending on both their inputs, using as little communication as possible. The required communication can sometimes be significantly lowered if we allow the parties the use of quantum  communication. We survey the main results of the young area of quantum communication its relation to teleportation and dense coding, the main examples of fast quantum communication protocols, lower bounds, and some applications.
Introduction
The area of communication complexity deals with the following type of prob-
lem. There are two separated parties, called Alice and Bob. Alice receives some
input x 2 X, Bob receives some y 2 Y , and together they want to compute
some function f(x; y). As the value f(x; y) will generally depend on both x
and y, neither Alice nor Bob will have sufficient information to do the computation
by themselves, so they will have to communicate in order to achieve
their goal. In this model, individual computation is free, but communication
is expensive and has to be minimized. How many bits do they need to communicate
between them in order to solve this? Clearly, Alice can just send
her complete input to Bob, but sometimes more efficient schemes are possible.
This model was introduced by Yao [52] and has been studied extensively, both
for its applications (like lower bounds on VLSI and circuits) and for its own
sake. We refer to [38,32] for definitions and results.
An interesting variant of the above is quantum communication complexity:
suppose that Alice and Bob each have a quantum computer at their disposal
and are allowed to exchange quantum bits (qubits) and/or to make use
Partially supported by the EU fifth framework project QAIP, IST-1999-11234.
Preprint submitted to Elsevier Preprint 21 October 2000
of the quantum correlations given by shared EPR-pairs (entangled pairs of
qubits named after Einstein, Podolsky, and Rosen [27]). Can Alice and Bob
now compute f with less communication than in the classical case? Quantum
communication complexity was first considered by Yao [53] for the model with
qubit communication and no prior EPR-pairs, and it was shown later that for
some problems the amount of communication required in the quantum world
is indeed considerably less than the amount of classical communication.
In this survey, we first give brief explanations of quantum computation and
communication, and then cover the main results of quantum communication
complexity: upper bounds (Section 5), lower bounds (Section 6), and applications
(Section 7). We include proofs of some of the central results and references
to others. Some other recent surveys of quantum communication complexity
are [48,15,35], and a more popular account can be found in [47]. Our
survey differs from these in being a bit more extensive and up to date.
Quantum Computation
In this section we briefly give the relevant background from quantum compu-
tation, referring to the book of Nielsen and Chuang [44] for more details.
2.1 States and operations
The classical unit of computation is a bit, which can take on the values 0 or
1. In the quantum case, the unit of computation is a qubit which is a linear
combination or superposition of the two classical values:
More generally, an m-qubit state jOEi is a superposition of all 2 m different
classical m-bit strings:
The classical state jii is called a basis state. The coefficient ff i is a complex
number, which is called the amplitude of jii. The amplitudes form a
dimensional complex vector, which we require to have norm 1 (i.e.
1). If some system is in state jOEi and some other is in state j/i, then their
joint state is the tensor product
We can basically do two things to a quantum state: measure it or perform a
unitary operation to it. If we measure jOEi, then we will see a basis state; we
will see jii with probability jff . Since the numbers jff induce a probability
distribution on the set of basis states they must sum to 1, which they indeed
do because jOEi has norm 1. A measurement "collapses" the measured state to
the measurement outcome: if we see jii, then jOEi has collapsed to jii, and all
other information in jOEi is gone.
Apart from measuring, we can also transform the state, i.e., change the am-
plitudes. Quantum mechanics stipulates that this transformation U must be
a linear transformation on the 2 m -dimensional vector of amplitudes:
ff 0:::0
Since the new vector of amplitudes fi i must also have norm 1, it follows that the
linear transformation U must be norm-preserving and hence unitary. 2 This
in turn implies that U has an inverse (in fact equal to its conjugate transpose
U   ), hence non-measuring quantum operations are reversible.
2.2 Quantum algorithms
We describe quantum algorithms in the quantum circuit model [25,53], rather
than the somewhat more cumbersome quantum Turing machine model [24,12].
A classical Boolean circuit is a directed acyclic graph of elementary Boolean
gates (usually AND, OR, and NOT), only acting on one or two bits at a time.
It transforms an initial vector of bits (containing the input) into the output. A
quantum circuit is similar, except that the classical Boolean gates now become
elementary quantum gates. Such a gate is a unitary transformation acting only
on one or two qubits, and implicitly acting as the identity on the other qubits
of the state. A simple example of a 1-qubit gate is the Hadamard transform,
which maps basis state jbi to 1
In matrix form, this is
An example of a 2-qubit gate is the controlled-NOT (CNOT) gate, which
negates the second bit of the state depending on the first bit: jc; bi ! jc; b \Phi ci.
Both quantum measurements and quantum operations allow for a somewhat
more general description than given here (POVMs and superoperators, respectively,
see [44]), but the above definitions suffice for our purposes.
In matrix form, this is
It is known that the set of gates consisting of CNOT and all 1-qubit gates is
universal, meaning that any other unitary transformation can be written as a
product of gates from this set. We refer to [4,44] for more details.
The product of all elementary gates in a quantum circuit is a big unitary
transformation which transforms the initial state (usually a classical bitstring
containing the input x) into a final superposition. The output of the circuit is
then the outcome of measuring some dedicated part of the final state. We say
that a quantum circuit computes some function f : f0; 1g n ! Z exactly if it
always outputs the right value f(x) on input x. The circuit computes f with
bounded error if it outputs f(x) with probability at least 2=3, for all x. Notice
that a quantum circuit involves only one measurement; this is without loss of
generality, since it is known that measurements can always be pushed to the
end at the cost of a moderate amount of extra memory.
The complexity of a quantum circuit is usually measured by the number of
elementary gates it contains. A circuit is deemed efficient if its complexity is
at most polynomial in the length n of the input. The most spectacular instance
of an efficient quantum circuit (rather, a uniform family of such circuits, one
for each n) is still Shor's 1994 efficient algorithm for finding factors of large
integers. It finds a factor of arbitrary n-bit numbers with high probability
using only n 2 polylog(n) elementary gates. This compromises the security of
modern public-key cryptographic systems like RSA, which are based on the
assumed hardness of factoring.
2.3 Query algorithms
A type of quantum algorithms that we will refer to later are the query algo-
rithms. In fact, most existing quantum algorithms are of this type. Here the
input is not part of the initial state, but encoded in a special "black box"
quantum gate. The black box maps basis state ji; bi to ji; b \Phi x i i, thus giving
access to the bits x i of the input. Note that a quantum algorithm can run the
black box on a superposition of basis states, gaining access to several input
bits x i at the same time. One such application of the black box is called a
query. The complexity of a quantum circuit for computing some function f is
now the number of queries we need on the worst-case input; we don't count
the complexity of other operations in this model. In the classical world, this
query complexity is known as the decision tree complexity of f .
A simple but illustrative example is the Deutsch-Jozsa algorithm [26,23]: suppose
we get the promise that the input x 2 f0; 1g n is either or has exactly
n=2 0s and n=2 1s. Define in the first case and
in the second. It is easy to see that a deterministic classical computer needs
queries for this (if the computer has queried n=2 bits and they are
all 0, the function value is still undetermined). On the other hand, here is a
1-query quantum algorithm for this problem:
(1) Start in a basis state zeroes followed by a 1
(2) Apply a Hadamard transform to each of the
(3) Query the black box once
Apply a Hadamard transform to the first n qubits
(5) Measure the first n qubits, output 1 if the observed state is
output 0 otherwise
By following the state through these steps, it may be verified that the algorithm
outputs 1 if the input is the input is balanced.
Another important quantum query algorithm is Grover's search algorithm [30],
which finds an i such that x such an i exists in the n-bit input. It
has error probability  1=3 on each input and uses O(
n) queries, which is
optimal [10,13,54]. Note that the algorithm can also be viewed as computing
the OR-function: it can determine whether at least one of the input bits is 1.
3 Quantum Communication
The area of quantum information theory deals with the properties of quantum
information and its communication between different parties. We refer
to [11,44] for general surveys, and will here restrict ourselves to explaining
two important primitives: teleportation [8] and superdense coding [9]. These
pre-date quantum communication complexity and show some of the power of
quantum communication.
We first show how teleporting a qubit works. Alice has a qubit ff 0
that she wants to send to Bob via a classical channel. Without further resources
this would be impossible, but Alice also shares an EPR-pair 1
j11i) with Bob. Initially, their joint state is
The first two qubits belong to Alice, the third to Bob. Alice performs a CNOT
on her two qubits and then a Hadamard transform on her first qubit. Their
joint state can now be written as2
Alice
-z
Alice then measures her two qubits and sends the result (2 random classical
bits) to Bob, who now knows which transformation he must do on his qubit
in order to regain the qubit ff 0
j1i. For instance, if Alice sent 11 then
Bob knows that his qubit is ff 0
j0i. A bit-flip (jbi ! j1 \Gamma bi) followed by
a phase-flip (jbi ! (\Gamma1) b jbi) will give him Alice's original qubit ff 0
j1i.
Note that the qubit on Alice's side has been destroyed: teleporting moves a
qubit from A to B, rather than copying it. In fact, copying an unknown qubit is
impossible [50], which can be seen as follows. Suppose C were a 1-qubit copier,
i.e. for every qubit jOEi. In particular
would not copy
p(j0i+j1i) correctly, since
by linearity
In teleportation, Alice uses 2 classical bits and 1 EPR-pair to send 1 qubit to
Bob. Superdense coding achieves the opposite: using 1 qubit and 1 EPR-pair,
Alice can send 2 classical bits b 2
to Bob. It works as follows. Initially they
share an EPR-pair 1
Alice applies a phase-
flip to her half of the pair. Second, if b 2
applies a bit-flip. Third, she
sends her half of the EPR-pair to Bob, who now has one of 4 states jOE b2 b1 i:
Since these states are orthogonal, Bob can apply a unitary transformation
i and thus learns b 2
Suppose Alice wants to send n classical bits of information to Bob and they do
not share any prior entanglement. Alice can just send her n bits to Bob, but,
alternatively, Bob can also first send n=2 halves of EPR-pairs to Alice and
then Alice can send n bits in n=2 qubits using dense coding. In either case, n
qubits are exchanged between them. If Alice and Bob already share n=2 prior
EPR-pairs, then n=2 qubits suffice by superdense coding. The following result
shows that this is optimal. We will refer to it as Holevo's theorem, because
the first part is an immediate consequence of a result of [31] (the second part
was derived in [22]).
Theorem 1 (Holevo) If Alice wants to send n bits of information to Bob
via a qubit channel, and they don't share prior entanglement, then they have
to exchange at least n qubits. If they do share unlimited prior entanglement,
then Alice has to send at least n=2 qubits to Bob, no matter how many qubits
Bob sends to Alice.
A somewhat stronger and more subtle variant of this lower bound was recently
derived by Nayak [40], improving upon [1]. Suppose that Alice doesn't want
to send Bob all of her n bits, but just wants to send a message which allows
Bob to learn one of her bits x i , where Bob can choose i after the message has
been sent. Even for this weaker form of communication, Alice has to send an
n)-qubit message.
4 Quantum Communication Complexity: The Model
First we sketch the setting for classical communication complexity, referring
to [38,32] for more details. Alice and Bob want to compute some function
. If the domain D equals X \Theta Y then
f is called a total function, otherwise it is a promise function. Alice receives
input x 2 X, Bob receives input y 2 Y , with (x; y) 2 D. As the value f(x; y)
will generally depend on both x and y, some communication between Alice
and Bob is required in order for them to be able to compute f(x; y). We are
interested in the minimal amount of communication they need.
A communication protocol is a distributed algorithm where first Alice does
some individual computation, and then sends a message (of one or more bits)
to Bob, then Bob does some computation and sends a message to Alice, etc.
Each message is called a round. After one or more rounds the protocol terminates
and outputs some value, which must be known to both players. The
cost of a protocol is the total number of bits communicated on the worst-case
input. A deterministic protocol for f always has to output the right value
f(x; y) for all (x; y) 2 D. In a bounded-error protocol, Alice and Bob may flip
coins and the protocol has to output the right value f(x; y) with probability
2=3 for all (x; y) 2 D. We use D(f) and R 2
(f) to denote the minimal cost of
deterministic and bounded-error protocols for f , respectively. The subscript
'2' in R 2
(f) stands for 2-sided bounded error. For R 2
(f) we can either allow
Alice and Bob to toss coins individually (private coin) or jointly (public coin).
This makes not much difference: a public coin can save at most O(log n) bits
of communication [42], compared to a protocol with a private coin.
Some often studied total functions where
ffl Equality: EQ(x;
ffl Inner product: IP(x;
(for is the ith bit of x and x " y 2 f0; 1g n is the bit-wise
AND of x and y)
ffl Disjointness: DISJ(x; This function is 1 iff there is no i
(viewing x and y as characteristic vectors of sets, the sets
are disjoint)
It is known that
n). However, R 2
(EQ) is only O(1), as follows. Alice and Bob jointly toss a
random string r 2 f0; 1g n . Alice sends the bit a to Bob (where '\Delta' is
inner product mod 2). Bob computes and compares this with a. If
then a 6= b with probability 1/2. Thus Alice
and Bob can decide equality with small error using O(n) public coin flips and
O(1) communication. Since public coin and private coin protocols are close,
this also implies that R 2
n) with a private coin.
Now what happens if we give Alice and Bob a quantum computer and allow
them to send each other qubits and/or to make use of EPR-pairs which they
share at the start of the protocol? Formally speaking, we can model a quantum
protocol as follows. The total state consists of 3 parts: Alice's private space,
the channel, and Bob's private space. The starting state is jxij0ijyi: Alice
gets x, the channel is initially empty, and Bob gets y. Now Alice applies a
unitary transformation to her space and the channel. This corresponds to
her private computation as well as to putting a message on the channel (the
length of this message is the number of channel-qubits affected by Alice's
operation). Then Bob applies a unitary transformation to his space and the
channel, etc. At the end of the protocol Alice or Bob makes a measurement
to determine the output of the protocol. We use Q(f) to denote the minimal
communication cost of a quantum protocol that computes f(x; y) exactly (=
with error probability 0). This model was introduced by Yao [53]. In the
second model, introduced by Cleve and Buhrman [21], Alice and Bob share
an unlimited number of EPR-pairs at the start of the protocol, but now they
communicate via a classical channel: the channel has to be in a classical state
throughout the protocol. We use C   (f) for the minimal complexity of an exact
protocol for f in this model. Note that we only count the communication, not
the number of EPR-pairs used. The third variant combines the strengths of the
other two: here Alice and Bob start out with an unlimited number of shared
EPR-pairs and they are allowed to communicate qubits. We use Q   (f) to
denote the communication complexity in this third model. By teleportation, 1
EPR-pair and 2 classical bits can replace 1 qubit of communication, so we have
bounded-error quantum protocols. Note that a shared EPR-pair can simulate
a public coin toss: if Alice and Bob each measure their half of the pair, they
get the same random bit.
Before continuing to study this model, we first have to face an important ques-
tion: is there anything to be gained here? At first sight, the following argument
seems to rule out any significant gain. By definition, in the classical world D(f)
bits have to be communicated in order to compute f . Since Holevo's theorem
says that k qubits cannot contain more information than k classical bits, it
seems that the quantum communication complexity should be roughly D(f)
qubits as well (maybe D(f)=2 to account for superdense coding, but not less).
Fortunately and surprisingly, this argument is false, and quantum communication
can sometimes be much less than classical communication complexity.
The information-theoretic argument via Holevo's theorem fails, because Alice
and Bob do not need to communicate the information in the D(f) bits of the
classical protocol; they are only interested in the value f(x; y), which is just
bit. Below we will survey the main examples that have so far been found of
gaps between quantum and classical communication complexity.
5 Quantum Communication Complexity: Upper bounds
5.1 Initial steps
Quantum communication complexity was introduced by Yao [53] and studied
by Kremer [37], but neither showed any advantages of quantum over classical
communication. Cleve and Buhrman [21] introduced the variant with classical
communication and shared EPR-pairs, and exhibited the first quantum protocol
provably better than any classical protocol. It uses quantum entanglement
to save 1 bit of classical communication. This gap was extended by Buhrman,
Cleve, and van Dam [16] and, for more than 2 parties, by Buhrman, van Dam,
Hyer, and Tapp [19].
5.2 Buhrman, Cleve, Wigderson
The first impressively large gaps between quantum and classical communication
complexity were exhibited by Buhrman, Cleve, and Wigderson [17].
Their protocols are distributed versions of known quantum query algorithms,
like the Deutsch-Jozsa and Grover algorithms. The following lemma shows
how a query algorithm induces a communication protocol:
binary connective (for instance \Phi or "). If
there is a T -query quantum algorithm for g, then there is a protocol for f that
communicates T (2 log n+4) qubits (and uses no prior entanglement) and that
has the same error probability as the query algorithm.
Proof The quantum protocol consists of Alice's simulating the quantum
query algorithm A on input x?y. Every query in A will correspond to 2 rounds
of communication. Namely, suppose Alice at some point wants to apply a query
to the state
i;b ff ib ji; bi (for simplicity we omit Alice's workspace).
Then she adds a j0i-qubit to the state, applies the unitary mapping ji; b; 0i !
sends the resulting state to Bob. Bob now applies the unitary
mapping ji; b; x sends the result back to Alice. Alice
applies ji; b; x takes off the last qubit, and ends up with the state
which is exactly the result of applying an x ? y-query
to jOEi. Thus every query to x ? y can be simulated using 2 log
of communication. The final quantum protocol will have T (2 log n
of communication and computes f(x; y) with the same error probability as A
has on input x ? y. 2
Now consider the disjointness function: DISJ(x;
Grover's algorithm can compute the NOR of n variables with O(
n) queries
with bounded-error, the previous lemma implies a bounded-error protocol for
disjointness with O(
log n) qubits. On the other hand, the linear lower
bound for disjointness is a well-known result of classical communication complexity
[33,46]. Thus we obtain the following near-quadratic separation:
Theorem 2 (Buhrman, Cleve, Wigderson)
log n) and R 2
Another separation is given by a distributed version of the Deutsch-Jozsa
problem of Section 2.3: define EQ 0 (x; This is a promise
version of equality, where the promise is that x and y are either equal or are
at Hamming distance n=2. Since there is an exact 1-query quantum algorithm
for In contrast, Buhrman, Cleve,
and Wigderson use a combinatorial result of Frankl and Rodl [29] to prove the
classical lower bound D(EQ 0 n). Thus we have the following exponential
separation for exact protocols:
Theorem 3 (Buhrman, Cleve, Wigderson)
5.3 Raz
Notice the contrast between the two separations of the previous section. For
the Deutsch-Jozsa problem we get an exponential quantum-classical separa-
tion, but the separation only holds if we force the classical protocol to be exact;
it is easy to see that O(log n) bits are sufficient if we allow some error (the
classical protocol can just try a few random positions i and check if x
not). On the other hand, the gap for the disjointness function is only quadratic,
but it holds even if we allow classical protocols to have some error probability.
Ran Raz [45] has exhibited a function where the quantum-classical separation
has both features: the quantum protocol is exponentially better than the classical
protocol, even if the latter is allowed some error probability. Consider
the following promise problem P:
Alice receives a unit vector v 2 R m and a decomposition of the corresponding
space in two orthogonal subspaces H (0) and H (1) . Bob receives an m \Theta m
unitary transformation U . Promise: Uv is either "close" to H (0) or to H (1) .
Question: which of the two?
As stated, this is a problem with continuous input, but it can be discretized
in a natural way by approximating each real number by O(log m) bits. Alice
and Bob's input is now log m) bits long. There is a simple yet
efficient 2-round quantum protocol for this problem: Alice views v as a log m-
qubit vector and sends this to Bob. Bob applies U and sends back the result.
Alice then measures in which subspace H (i) the vector Uv lies and outputs
the resulting i. This takes only qubits of communication.
The efficiency of this protocol comes from the fact that an m-dimensional
vector can be "compressed" or "represented" as a log m-qubit state. Similar
compression is not possible with classical bits, which suggests that any classical
protocol for P will have to send the vector v more or less literally and hence
will require a lot of communication. This turns out to be true but the proof
(given in [45]) is surprisingly hard. The result is the first exponential gap
between
and R 2
Theorem 4 (Raz) Q 2
n) and R 2
6 Quantum Communication Complexity: Lower Bounds
In the previous section we exhibited some of the power of quantum communication
complexity. Here we will look at its limitations, first for exact protocols
and then for the bounded-error case.
6.1 Lower bounds on exact protocols
Quite good lower bounds are known for exact quantum protocols for total
functions. For a total function
the communication matrix of f . This is an jXj \Theta jY j Boolean matrix which
completely describes f . Let rank(f) denote the rank of M f over the reals.
Mehlhorn and Schmidt [39] proved that D(f)  log rank(f ), which is the
main source of lower bounds on D(f ). For Q(f) a similar lower bound follows
from techniques of Yao and Kremer [53,37], as first observed in [17]. This
bound was later extended to the case where Alice and Bob share unlimited
prior entanglement by Buhrman and de Wolf [20]. Their result turned out to
be equivalent to a result in Nielsen's thesis [43, Section 6.4.2]. The result is:
Theorem 5 Q   (f)  log rank(f)=2 and C   (f)  log rank(f).
Hence quantum communication complexity in the exact model is maximal
whenever M f has full rank, which it does for almost all functions, including
equality, (the complement of) inner product, and disjointness.
How tight is the log rank(f) lower bound? It has been conjectured that D(f)
(log rank(f)) O(1) for all total functions, in which case log rank(f) would characterize
D(f) up to polynomial factors. If this log-rank conjecture is true, then
Theorem 5 implies that Q   (f) and D(f) are polynomially close for all total
f , since then Q   (f)  D(f)  (log rank(f)) O(1)  (2Q   (f)) O(1) . Some small
classes of functions where this provably holds are identified in [20]. It should
be noted that, in fact, no total f is known where Q   (f) is more than a factor
of 2 smaller than D(f) (the factor of 2 can be achieved by superdense coding).
6.2 Lower bounds on bounded-error protocols
The previous section showed some strong lower bounds for exact quantum
protocols. The situation is much worse in the case of bounded-error protocols,
for which very few good lower bounds are known. One of the few general
lower bound techniques known to hold for bounded-error quantum complexity
(without prior entanglement), is the so-called "discrepancy method". This was
shown by Kremer [37], who used it to derive an \Omega\Gamma n) lower bound for Q 2
(IP).
Cleve, van Dam, Nielsen, and Tapp [22] later independently proved such a
lower bound for Q  (IP).
We will sketch the very elegant proof of [22] here for the case of exact protocols;
for bounded-error protocols it is similar but more technical. The proof uses
the IP-protocol to communicate Alice's n-bit input to Bob, and then invokes
Holevo's theorem to conclude that many qubits must have been communicated
in order to achieve this. Suppose Alice and Bob have some protocol for IP.
They can use this to compute the following mapping:
Now suppose Alice starts with an arbitrary n-bit state jxi and Bob starts with
the uniform superposition 1
they apply the above mapping,
the final state becomes
x\Deltay jyi:
If Bob now applies a Hadamard transform to each of his n qubits, then he
obtains the basis state jxi, so Alice's n classical bits have been communicated
to Bob. Theorem 1 now implies that the IP-protocol must
qubits, even if Alice and Bob share unlimited prior entanglement.
The above proof works for IP, but does not easily yield good bounds in general.
Neither does the discrepancy method, or an approximate version of the rank
lower bound which was noted in [17]. New lower bound techniques for quantum
communication are required. Of particular interest is whether the upper bound
log n) of [17] is tight. Because disjointness can be reduced
to many other problems (it is in fact "coNP-complete" [3]), a good lower
bound for disjointness would imply many other lower bounds as well. The
best known lower bound is only \Omega\Gammaly/ n), which was proven for
(DISJ)
in [2] (this also follows from discrepancy) and for Q  (DISJ) in [20]. Buhrman
and de Wolf [20] have a translation of the approximate rank lower bound to
properties of polynomials which might prove an \Omega\Gamma
n) bound for disjointness,
but a crucial link is still missing in their approach.
7 Quantum Communication Complexity: Applications
The main applications of classical communication complexity have been in
proving lower bounds for various models like VLSI, Boolean circuits, formula
size, Turing machine complexity, data structures, automata size etc. We refer
to [38,32] for many examples. Typically one proceeds by showing that a
communication complexity problem f is "embedded" in the computational
problem P of interest, and then uses communication complexity lower bounds
on f to establish lower bounds on P . Similarly, quantum communication complexity
has been used to establish lower bounds in various models of quantum
computation, though such applications have received relatively little attention
so far. We will briefly mention some.
Yao [53] initially introduced quantum communication complexity as a tool
for proving a superlinear lower bound on the quantum formula size of the
majority function (a "formula" is a circuit of restricted form). More recently,
Klauck [34] used one-way quantum communication complexity lower bounds
to prove lower bounds on the size of quantum formulae.
Since upper bounds on query complexity give upper bounds on communication
complexity (Lemma 1), lower bounds on communication complexity give lower
bounds on query complexity. For instance, IP(x; so the
\Omega\Gamma n) bound for IP (Section 6.2) implies an \Omega\Gamma n= log n) lower bound for the
quantum query complexity of the parity function, as observed by Buhrman,
Cleve, and Wigderson [17]. This lower bound was later strengthened to n=2
in [5,28].
Furthermore, as in the classical case, lower bounds on (one-way) communication
complexity imply lower bounds on the size of finite automata. This was
used by Klauck [34] to show that Las Vegas quantum finite automata cannot
be much smaller than classical deterministic finite automata.
Finally, Ben-Or [7] has recently applied the lower bounds for IP in a new proof
of the security of quantum key distribution.
8 Other Developments and Open Problems
Here we mention some other results in quantum communication complexity
or related models:
ffl Quantum sampling. For the sampling problem, Alice and Bob do not
want to compute some f(x; y), but instead want to sample an (x; y)-pair
according to some known joint probability distribution, using as little communication
as possible. Ambainis et.al. [2] give a tight algebraic characterization
of quantum sampling complexity, and exhibit an exponential gap
between the quantum and classical communication required for a sampling
problem related to disjointness.
ffl Spooky communication. Brassard, Cleve, and Tapp [14] exhibit tasks
which can be achieved in the quantum world with entanglement and no
communication, but which would require communication in the classical
world. They also give upper and lower bounds on the amount of classical
communication needed to "simulate" EPR-pairs. Their results may be
viewed as quantitative extensions of the famous Bell inequalities [6].
ffl Las Vegas protocols. In this paper we just considered two modes of com-
putation: exact and bounded-error. An intermediate type of protocols are
zero-error or Las Vegas protocols. These never output an incorrect answer,
but may claim ignorance with probability at most 1/2. Some quantum-
classical separations for zero-error protocols may be found in [18,34].
One-way communication. Suppose the communication is one-way: Alice
just sends qubits to Bob. Klauck [34] showed for all total functions that
quantum communication is not significantly better than classical communication
in this case.
ffl Rounds. It is well known in classical communication complexity that allowing
Alice and Bob k+1 rounds of communication instead of k can reduce
the required communication exponentially. An analogous result has recently
been shown for quantum communication [41] (see also [36]).
ffl Non-deterministic communication complexity. A non-deterministic
protocol has positive acceptance probability on input (x; y) iff f(x;
Classically, the non-deterministic communication complexity is characterized
by the logarithm of the cover number of the communication matrix M f .
Recently, de Wolf [49] showed that the quantum non-deterministic communication
complexity is characterized (up to a factor of 2) by the logarithm
of the rank of a non-deterministic version of M f .
Finally, here's a list of interesting open problems in quantum communication
complexity:
ffl Raz's exponential gap only holds for a promise problem. Are D(f) and
polynomially related for all total f? As we showed in Section 6.1, a
positive answer to this question would be implied by the classical log-rank
conjecture. A similar question can be posed for the relation between R 2
and Q  (f ).
ffl Does entanglement add much power to qubit communication? That is, what
are the biggest gaps between Q(f) and Q   (f ), and between Q 2
(f) and
ffl Develop good lower bound techniques for bounded-error quantum protocols.
In particular one that gives a good lower bound for disjointness.
ffl Classically, Yao [51] used the minimax theorem from game theory to show an
equivalence between deterministic protocols with a probability distribution
on the inputs, and bounded-error protocols. Is some relation like this true in
the quantum case as well? If so, lower bound techniques for exact quantum
protocols can be used to deal with the previous question.



--R

Quantum dense coding and a lower bound for 1-way quantum finite automata
The quantum communication complexity of sampling.
Complexity classes in communication complexity theory.
Elementary gates for quantum computation.
Quantum lower bounds by polynomials.
On the Einstein-Podolsky-Rosen paradox
Security of quantum key distribution.
Teleporting an unknown quantum state via dual classical and Einstein- Podolsky-Rosen channels
Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states
Strengths and weaknesses of quantum computing.
Quantum information theory.
Quantum complexity theory.
Tight bounds on quantum searching.
The cost of exactly simulating quantum entanglement with classical communication.
Quantum computing and communication complexity.
Quantum entanglement and communication complexity.
Quantum vs. classical communication and computation (preliminary version).
Bounds for small-error and zero-error quantum algorithms
Multiparty quantum communication complexity.
Communication complexity lower bounds by polynomials.
Substituting quantum entanglement for communication.
Quantum entanglement and the communication complexity of the inner product function.
Quantum algorithms revisited.
Quantum theory
Quantum computational networks.
Rapid solution of problems by quantum computation.
Can quantummechanical description of physical reality be considered complete?
A limit on the speed of quantum computation in determining parity.
Forbidden intersections.
A fast quantum mechanical algorithm for database search.
Bounds for the quantity of information transmitted by a quantum communication channel.

The probabilistic communication complexity of set intersection.
On quantum and probabilistic communication: Las Vegas and one-way protocols
Quantum communication complexity.
On rounds in quantum communication.
Quantum communication.
Communication Complexity.
Las Vegas is better than determinism in VLSI and distributed computing.
Optimal lower bounds for quantum automata and random access codes.
Interaction in quantum communication complexity.
Private vs. common random bits in communication complexity.
Quantum Information Theory.
Quantum Computation and Quantum Information.
Exponential separation of quantum and classical communication complexity.
On the distributional complexity of disjointness.
Physicists triumph at Guess my Number.
Classical versus quantum communication complexity.
Characterization of non-deterministic quantum query and quantum communication complexity
A single quantum cannot be copied.
Probabilistic computations: Toward a unified measure of complexity.
Some complexity questions related to distributive computing.
Quantum circuit complexity.
Grover's quantum searching algorithm is optimal.
--TR
Private vs. common random bits in communication complexity
The probabilistic communication complexity of set intersection
On the distributional complexity of disjointness
A fast quantum mechanical algorithm for database search
Public vs. private coin flips in one round communication games (extended abstract)
Quantum Complexity Theory
Strengths and Weaknesses of Quantum Computing
Communication complexity and parallel computing
Communication complexity
Quantum vs. classical communication and computation
Exponential separation of quantum and classical communication complexity
Dense quantum coding and a lower bound for 1-way quantum automata
Classical versus quantum communication complexity
On quantum and probabilistic communication
Interaction in quantum communication and the complexity of set disjointness
On communication over an entanglement-assisted quantum channel
Quantum Entanglement and Communication Complexity
Quantum Entanglement and the Communication Complexity of the Inner Product Function
Lower Bounds in the Quantum Cell Probe Model
Improved Quantum Communication Complexity Bounds for Disjointness and Equality
On Quantum Versions of the Yao Principle
Randomized Simultaneous Messages
Characterization of Non-Deterministic Quantum Query and Quantum Communication Complexity
The Quantum Communication Complexity of Sampling
Quantum Lower Bounds by Polynomials
Optimal Lower Bounds for Quantum Automata and Random Access Codes
Bounds for Small-Error and Zero-Error Quantum Algorithms
Las Vegas is better than determinism in VLSI and distributed computing (Extended Abstract)
Some complexity questions related to distributive computing(Preliminary Report)
Communication Complexity Lower Bounds by Polynomials
Lower Bounds for Quantum Communication Complexity

--CTR
Franois Le Gall, Exponential separation of quantum and classical online space complexity, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
Dmitry Gavinsky , Julia Kempe , Oded Regev , Ronald de Wolf, Bounded-error quantum state identification and exponential separations in communication complexity, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
Dmitry Gavinsky , Julia Kempe , Iordanis Kerenidis , Ran Raz , Ronald de Wolf, Exponential separations for one-way quantum communication complexity, with applications to cryptography, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
communication complexity;quantum computing