Optimal and Verifiable Quantum Advantages in Communication Complexity
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 Ω(2n) 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 Ω(2n) bits of communication. We also construct a family of efficiently verifiable total search problems achieving an n versus Ωd(nd) separation between quantum one-way and randomized one-way communication for every fixed d ≥ 2. In the quantum protocol, Alice prepares her message using a single unitary from the dth 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.
Related
- Communication Advantages from Quantum Dense Network Coding
- On the quantum communication complexity of total functions
- Constant-round quantum advantage in communication complexity for total functions
- Improved Separations between Quantum and Classical Communication Complexity of Total Functions
- Quantum Encodings, Private Messages, and Communication Complexity
BibTeX
@misc{anselm2026optimal,
title = {{Optimal and Verifiable Quantum Advantages in Communication Complexity}},
author = {Ryan Anselm and Michelle Ding and Dar Gilboa and Sabee Grewal},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.05585},
eprint = {2610.05585},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.05585},
}
RIS
TY - UNPB
TI - Optimal and Verifiable Quantum Advantages in Communication Complexity
AU - Ryan Anselm
AU - Michelle Ding
AU - Dar Gilboa
AU - Sabee Grewal
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2610.05585
UR - https://arxiv.org/abs/2610.05585
AB - 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 ≥ 2. In the quantum protocol, Alice prepares her message using a single unitary from the dth 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.
ER -