## DIMACS TR: 2000-36

## Interaction in Quantum Communication and the Complexity of Set Disjointness

### Authors: Ashwin Nayak, Amnon Ta-Shma and David Zuckerman

**
ABSTRACT
**

One of the most intriguing facts about communication using quantum
states is that these states cannot be used to transmit more classical bits
than the number of qubits used, yet
in some scenarios
there are ways of conveying information
with exponentially fewer qubits than possible classically~\cite{ASTVW98,R99}.
Moreover, these methods
have a very simple structure---they involve only
%little interaction
few message exchanges
between the communicating parties.
We
%look more closely at the ways in which information encoded in quantum
%states may be manipulated, and
consider the question as to whether every classical
protocol may be transformed to a ``simpler'' quantum protocol---one that
has similar efficiency,
%By a simpler protocol, we mean a protocol
but uses fewer message exchanges.
We show that for any constant~$k$, there is a problem such that
its~$k+1$ message classical communication complexity
is exponentially smaller than its~$k$
message quantum communication complexity, thus answering the above
question in the negative.
This in particular proves a round hierarchy theorem for
quantum communication complexity, and implies, via a simple
reduction~\cite{Klauck00},
an~$\Omega(N^{1/k})$ lower bound for~$k$ message protocols for
Set Disjointness (for constant~$k$).

Our result builds on two primitives,
{\em local transitions in bi-partite states} (based on previous work)
and {\em average encoding\/}
which may
be of significance in other contexts as well.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-36.ps.gz

DIMACS Home Page