Colloquium Speaker

Speaker:Ran Raz
Faculty of Mathematics and Computer Science
The Weizmann Institute of Science
Rehovot, Israel
Topic:Exponential Separation of Quantum and Classical Communication Complexity
Date:Tuesday, October 26, 1999
Time:9:30 AM
Place:Gould-Simpson, Room 701


Refreshments will be served in the 7th-floor lobby of Gould-Simpson at 9 :15 AM


ABSTRACT


Communication complexity has become a central complexity model. In that model, we count the amount of communication bits needed between two parties in order to solve certain computational problems. We show that for certain communication complexity problems, quantum communication protocols are exponentially faster than classical ones. More explicitly, we give an example for a communication complexity relation (or promise problem) P such that:
  1. The quantum communication complexity of P is O(log m).

  2. The classical probabilistic communication complexity of P is OMEGA(m1/4 / log m).

(where m is the length of the inputs). This gives an exponential gap between quantum communication complexity and classical probabilistic communication complexity. Only a quadratic gap was previously known.

Our problem P is of geometrical nature, and is a finite precision variation of the following problem: Player I gets as input a unit vector x in Rn and two orthogonal subspaces M0 and M1 both subsets of Rn. Player II gets as input an orthogonal matrix T:Rn -> Rn. Their goal is to answer 0 if T(x) is in M0 and 1 if T(x) is in M1 (and any answer in any other case). We give an almost tight analysis for the quantum communication complexity and for the classical probabilistic communication complexity of this problem.

In order to prove our results we prove several lemmas about the geometry of the sphere Sn-1 and about sets of orthogonal matrices. One example is the following lemma:

Let C, a subset of Sn-1, be a measurable set of measure (fraction) c in the sphere Sn-1. Let V, a subset of Rn be a random linear subspace of dimension k, and denote by gV the measure (fraction) of C intersected with V which is in the sphere Sn-1 intersected with V. Then, for any d > 0,

PROBV[ | gV - c | >= d ] < (4/d) exp[ -(d2/2) k ]