poly: the power of quantum computation

http://www.cs.berkeley.edu/~vazirani/qcom.ps

This remarkable preprint proves that quantum computers may perform some
distributed computations using exponentially less communication than is
required with a classical computer. It is, in my opinion, the first time
a completely unambiguous separation in power between quantum and
classical computation has been proven, and as such is an important
milestone.

Michael Nielsen
Received on Sat Dec 26 19:19:10 1998