Quantum protocols drastically reduce communication for search problems
Optimal and Verifiable Quantum Advantages in Communication Complexity
Computational Complexity
Summary
Some problems require a lot of back-and-forth communication to solve if done with normal computers. The authors found special search problems where a quantum computer can solve them by sending a much smaller quantum message, while classical methods need exponentially more communication. They also created versions where answers can be quickly checked, and the quantum advantage remains very large and can be proven optimal under certain conditions. This work shows strong, verifiable cases where quantum communication outperforms classical communication by a huge margin.
What this means in practice
- •For quantum algorithm designers: Develop quantum communication protocols that minimize message size while solving verification-friendly search problems efficiently.
- •For quantum experiment designers: Create near-term experiments demonstrating unconditional, efficiently verifiable quantum advantages in communication tasks.
A theory result. No direct application yet.
Authors
Ryan Anselm, Michelle Ding, Dar Gilboa, Sabee Grewal
Abstract
We establish optimal quantum-classical separations in communication complexity for search problems. We introduce a total search problem called Pelagic Fourier Fishing and show that it admits an $n$-qubit quantum one-way protocol, whereas every randomized two-way protocol requires $Ω(2^n)$ bits of communication. We then introduce a variant of this problem whose solutions can be verified in polynomial time. This variant also admits an $n$-qubit quantum one-way protocol, while every randomized one-way protocol requires $Ω(2^n)$ bits of communication. We also construct a family of efficiently verifiable total search problems achieving an $n$ versus $Ω_d(n^d)$ separation between quantum one-way and randomized one-way communication for every fixed $d \ge 2$. In the quantum protocol, Alice prepares her message using a single unitary from the $d$th level of the Clifford hierarchy, and Bob performs a Clifford measurement. This separation is asymptotically optimal under this restriction on Alice's message. For $d = 2$, Alice's message is a stabilizer state and Bob's measurement is Clifford, so the protocol uses no magic, yet achieves an optimal quadratic quantum advantage. Finally, we discuss how these separations can be adapted to near-term quantum advantage experiments in which the demonstrated advantage is both unconditional and efficiently verifiable.