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.
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.
We study the one-way communication complexity of the f-Boolean Hidden Partition problem. Here, Alice is given an n-bit string and Bob is given Ω(n) disjoint blocks of its indices together with a string of labels. Under the promise that the evaluations of f on these blocks either agree with all of the labels or disagree with all of them, Bob must determine which is the case using a single message from Alice. This problem generalizes the Boolean Hidden Matching and Hidden Hypermatching problems, which capture the special case where f is the parity function.
We establish classical and quantum communication bounds for f-Boolean Hidden Partition in terms of the sign degree d of f, proving a conjecture of Doriguello and Montanaro (TQC 2020). Their prior work gave logarithmic communication upper bounds for classical protocols when d≤1 and quantum protocols when d≤2, as well as polynomial lower bounds for certain structured functions with larger sign degree. We show that for every f of sign degree d≥2, the randomized classical communication complexity of this problem is Θ(n1−1/d) while its quantum communication complexity lies between Ω(n1−2/d) and $\bO{n^{1-1/\lceil d/2 \rceil} \log n}$. This completely characterizes the functions f admitting polynomial quantum advantage as those for which d≥2, with a new infinite family of exponential separations given by the case d=2.
Almost-quantum correlations form the 1+AB level of the Navascués--Pironio--Acín hierarchy. They strictly contain the quantum set, are characterized by a single semidefinite program, arise in Sorkin's quantum measure theory, and satisfy several principles proposed to single out quantum theory. We show that they are nevertheless unboundedly stronger than quantum correlations in a zero-error communication task. Alice and Bob receive labels s,t∈[N], N≥3; after one bit from Alice, Bob must decide whether s=t, never erring but allowed to abstain. For every model of quantum correlations, from finite-dimensional tensor products to commuting operators, the optimal worst-case probability of a conclusive answer is exactly 1/N, the value attained with shared randomness, so the bound does not depend on the resolution of Tsirelson's problem. An explicit family of almost-quantum correlations attains 1/19 for every N. For certificates of equality from binary-outcome boxes, we solve the underlying semidefinite programs in closed form. The almost-quantum optimum equals N2/(17N2−80N+64) for N≥8 and tends to 1/17. The first level of the hierarchy, which coincides with the set singled out by macroscopic locality, attains N/[8(N−2)], which tends to 1/8; its optimal boxes lie outside the almost-quantum set for every N≥5. For longer messages, entanglement saves at most one bit over shared randomness, whereas almost-quantum correlations reduce the one-way zero-error cost of deciding equality of n-bit strings from n bits to at most 13. The quantum bound also yields a linear witness of post-quantumness on a face of the nonsignalling polytope.
Quantum systems are known to offer advantages over their classical counterpart in communication complexity protocols, where the aim is to minimize the amount of information exchange between distant parties to compute global functions of their distributed inputs. In this work, we establish that any one-way communication protocol implemented using a prime-dimensional quantum system -- restricted to stabilizer-state encodings and Clifford-operation decodings -- can be exactly simulated by transmitting a classical system of the same dimension, given access to shared randomness between the sender and receiver. In direct analogy with the Gottesman-Knill theorem, which attributes quantum computational speedup to non-stabilizer resources, commonly known as the magic resources, our result identifies the same non-stabilizer resources as the essential ingredient for the quantum advantage in one-way communication complexity. Furthermore, we present explicit tasks where even a 'minimal magic resource' suffices to achieve a provable quantum advantage, highlighting its efficient use in communication protocols.
Private simultaneous quantum messages (PSQM) provide a minimal model of noninteractive secure multiparty quantum computation, yet their communication complexity for concrete functions remains poorly understood. We show that familiar total functions already exhibit both genuine quantum advantages and strong structural limitations. For three-party equality on n-bit inputs, which determines whether the players' n-bit strings are identical, we construct an entanglement-assisted protocol with asymptotic communication (1.633…)n qubits, whereas every perfectly correct protocol without prior entanglement requires at least 3n qubits. For three-bit majority, one shared GHZ state and one transmitted qubit per player suffice for perfect correctness and perfect privacy, reducing the communication from the optimal classical cost of six bits to three qubits. Three-bit AND behaves differently. No perfectly correct and perfectly private protocol exists when the players share an arbitrary three-qubit state, apply arbitrary local unitary encodings, and transmit one qubit each. However, increasing the local dimension overcomes this obstruction: one shared three-qutrit GHZ state and one transmitted qutrit per player yield a one-shot protocol with total communication 3log23. Together with the six-bit classical lower bound, this gives a strict quantum communication advantage. More generally, for every k≥3, we construct a perfectly correct and perfectly private one-shot protocol for k-bit AND using one qudit of dimension at most k per player, and hence at most klog2k qubits in total.
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 Ω~(n) randomized communication with two quantum messages, and versus Ω(n1−ε) for every fixed 0<ε<1 with more quantum messages.