#### Milestone Year

### 1999

#### Exponential Separation of Quantum and Classical Communication Complexity

Quantum computers, if ever built, will be able to factor numbers
in polynomial time. Since it is widely believed that numbers
cannot be factored in polynomial time by a classical computer,
this result gives a strong indication, although not a proof,
that quantum computers will be able to solve certain computational
problems significantly faster than classical computers.

A Weizmann scientist studied the equivalent question for
communication: Can quantum communication channels significantly
reduce the amount of communication needed to solve certain tasks?
that is, are quantum communication protocols significantly stronger
than classical ones?

In 1999, he proved that for certain communication tasks,
quantum communication protocols are exponentially faster
than classical ones.