On the quantum communication complexity of total functions
The authors studied a specific family of total Boolean functions called Cheat-Shapen and developed a polylogarithmic two-message quantum protocol to compute them. This quantum protocol achieves communication complexity of O(log3 Nn log log Nn), which is significantly better than the polynomial communication required by any randomized protocol for these functions, demonstrating quantum advantage in this context.