|
|
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.