Quantum communication can beat classical for total functions
Improved Separations between Quantum and Classical Communication Complexity of Total Functions
Computational Complexity
Summary
This paper looks at how quantum communication compares to classical communication when solving certain problems. The authors build on an existing method and improve it, showing that quantum communication can use much less information than classical methods for some tasks. Specifically, they find cases where only a tiny amount of quantum information needs to be exchanged, but classical communication has to be very large to do the same. This strengthens the evidence that quantum communication can be much more efficient for certain kinds of problems.
What this means in practice
- •For quantum communication engineers: Design communication protocols that exploit fewer quantum bits than classical bits for certain problem classes, improving quantum communication efficiency.
- •For cryptography developers: Explore new cryptographic schemes that rely on quantum communication complexity advantages for enhanced security proofs.
A theory result. No direct application yet.
Authors
François Le Gall
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Ω(\sqrt n)$ randomized communication with two quantum messages, and versus $Ω(n^{1-\varepsilon})$ for every fixed $0<\varepsilon<1$ with more quantum messages.