Quantum communication beats classical methods in three-player number games
Exponential Quantum Advantage in Numbers-on-Forehead Communication
Computational Complexity
Summary
The paper shows that quantum communication can solve a certain interactive three-player number game much more efficiently than classical methods. The researchers create a specific problem where quantum communication uses only a small amount of information exchange, while classical randomized communication requires much more. They overcome a known challenge in proving quantum advantages by developing a new technique for lower bounds in classical communication. This work demonstrates a clear separation between quantum and classical communication power in a more general setting than before.
What this means in practice
- •For quantum communication engineers: Design efficient multi-party quantum communication protocols that outperform classical ones for distributed computing tasks.
- •For distributed system designers: Understand fundamental limitations of classical communication methods to guide development of new protocols with quantum elements.
A theory result. No direct application yet.
Authors
Haoyu Wang, Pei Wu, Guangxu Yang
Abstract
We give the first exponential quantum advantage in the general interactive three-party Numbers-on-Forehead (NOF) model for a decision problem. Previous separations hold only for restricted protocols like one-way communication for a relation. We construct an explicit partial Boolean function, the Interleaved Unitary Product problem, that requires only $O(\log n)$ NOF quantum communication but $\widetildeΩ(n^{1/32})$ randomized communication. This function builds on the two-party unitary product problem of Arunachalam, Girish, and Lifshitz (TQC 2024). The main technical obstacle is that discrepancy, the standard lower-bound method for NOF, also lower-bounds quantum communication. We instead develop a regularity-based argument for randomized NOF lower bounds, building on the approach of Kelley, Lovett, and Meka and adapting the regularity decomposition of Abboud, Fischer, Kelley, Lovett, and Meka (STOC 2024) to cylinder intersections. Combined with matrix-product estimates of Arunachalam, Girish, and Lifshitz, this yields our randomized lower bound.