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 |

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)Psuch that:

- The quantum communication complexity of
PisO(log m).

- The classical probabilistic communication complexity of
PisOMEGA(m.^{1/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

Pis of geometrical nature, and is a finite precision variation of the following problem: Player I gets as input a unit vectorxinRand two orthogonal subspaces^{n}Mand_{0}Mboth subsets of_{1}R. Player II gets as input an orthogonal matrix^{n}T:R. Their goal is to answer^{n}-> R^{n}0ifT(x)is inMand_{0}1ifT(x)is inM(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._{1}In order to prove our results we prove several lemmas about the geometry of the sphere

Sand about sets of orthogonal matrices. One example is the following lemma:^{n-1}Let

C, a subset ofS, be a measurable set of measure (fraction)^{n-1}cin the sphereS. Let^{n-1}V, a subset ofRbe a random linear subspace of dimension^{n}k, and denote bygthe measure (fraction) of_{V}Cintersected withVwhich is in the sphereSintersected with^{n-1}V. Then, for anyd > 0,

PROB[ |_{V}g|_{V}- c>= d]< (4/d) exp[-(d]^{2}/2) k