Exponential separation of quantum and classical communication complexity

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 Ω(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 P is of geometrical nature, and is a finite precision variation of the following problem: Player I gets as input a unit vector x∈Rⁿ and two orthogonal subspaces M₀, M₁⊂Rⁿ. Player II gets as input an orthogonal matrix T:Rⁿ→R_n. Their goal is to answer 0 if T(x)∈M₀ and 1 if T(x)∈M₁, (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.