Improved Separations between Quantum and Classical Communication Complexity of Total Functions

Abstract

We refine Gavinsky's framework (arXiv:2608.18784) for exponential separations between quantum and randomized communication complexity of total functions and obtain larger separations: polylogarithmic quantum communication versus $\tilde{\Omega }(\sqrt{n})$ randomized communication with two quantum messages, and versus $\Omega (n^{1-\epsilon })$ for every fixed $0<\epsilon <1$ with more quantum messages.

13 pages