Improved Separations between Quantum and Classical Communication Complexity of Total Functions
This research refines communication complexity bounds for total functions, achieving significantly larger separations between quantum and classical communication. It moves from previous exponents like 1/6 to 1/2, establishing polylogarithmic quantum communication versus super-linear randomized complexity. This improves upon earlier results by demonstrating stronger separation exponents across different message counts.