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