arXiv:2610.05585
Optimal and Verifiable Quantum Advantages in Communication Complexity
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.
AI Summary
The paper asks how large quantum–classical communication separations can be for total search problems, including when individual answers are efficiently verifiable or quantum messages have restricted preparation complexity. It reaches the general classical simulation ceiling of $O(2^n)$ bits for an $n$-qubit one-way message. Pelagic Fourier Fishing asks for a Fourier coefficient lying in the bulk of the squared-mass-weighted spectrum of the product of two distributed Boolean functions. Fourier sampling gives an $n$-qubit one-way protocol succeeding with probability at least $3/4$ on every input; randomized two-way protocols achieving average success $2/3$ on uniform inputs require $\Omega(2^n)$ bits. The lower bound uses an entropy-based coupling decomposition of high-entropy inner products into independent Gaussian-like noise plus a shift and negligible error, then bounds the probability of hitting a two-sided magnitude window. An affine-coset variant preserves the $n$ versus $\Omega(2^n)$ separation against classical one-way protocols while permitting verification with $O(n^2)$ input queries and polynomial time. Its proof combines coupling and covariance bounds with maximum-load bounds for linear hashing. A directional-derivative problem for degree-$d$ Boolean polynomials gives exact $n$-qubit protocols versus $\Omega_d(n^d)$ classical one-way bits. Lower bounds establish independence of derivative functionals; circuit-description and Clifford-hierarchy counting bounds establish resource optimality. Preparation uses $O_d(n^d/\log n)$ gates, with Clifford measurements; $d=2$ uses only stabilizer operations. Efficient verification and optimal two-way hardness are not achieved simultaneously. Exponential separations require exponentially costly preparation, and proposed memory-advantage experiments still need finite-size, noise, and hardware-specific analysis.
The models were also used for literature search, checking arguments, and revising portions of the exposition.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 65 pages