Exponential separation of quantum and classical communication complexity

Research output: Contribution to journalConference articlepeer-review

185 Scopus citations


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 Ω(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∈Rn and two orthogonal subspaces M0, M1⊂Rn. Player II gets as input an orthogonal matrix T:Rn→Rn. Their goal is to answer 0 if T(x)∈M0 and 1 if T(x)∈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.

Original languageEnglish (US)
Pages (from-to)358-367
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - 1999
Externally publishedYes
EventProceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA
Duration: May 1 1999May 4 1999

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'Exponential separation of quantum and classical communication complexity'. Together they form a unique fingerprint.

Cite this