On the quantum communication complexity of total functions

Dmytro Gavinsky

We present a total function with a polylogarithmic two-message quantum protocol, whereas every randomised protocol, even with arbitrarily many rounds, requires polynomial communica…