This paper addresses two problems in the context of two-party communication complexity of functions. First, it concludes the line of research which can be viewed as demonstrating qualitative advantage of quantum communication in the three most common communication “layouts”: two-way interactive communication, one-way communication and simultaneous message passing (SMP). I demonstrate a functional (problem c̅E̅q̅T̅, whose communication complexity is O (log n)2) in the quantum version of the SMP and Ω̃ (√n) in the classical (randomized) version of SMP. Second, this paper contributes to understanding the power of the weakest commonly studied regime of quantum communication-SMP with quantum messages and without shared randomness (the latter restriction can be viewed as a somewhat artificial way of making the quantum model “as weak as possible”). Our function c̅E̅q̅T̅ has an efficient solution in this regime as well, which means that even lacking shared randomness, quantum SMP can be exponentially stronger than its classical counterpart with shared randomness.
We study a new type of separations between quantum and classical communication complexity, separations that are obtained using quantum protocols where all parties are efficient , in the sense that they can be implemented by small quantum circuits, with oracle access to their inputs. Our main result qualitatively matches the strongest known separation between quantum and classical communication complexity Gavinsky (2016) and is obtained using a quantum protocol where all parties are efficient. More precisely, we give an explicit partial Boolean function f over inputs of length N , such that: f can be computed by a simultaneous-message quantum protocol with communication complexity polylog( N ) (where at the beginning of the protocol Alice and Bob also have polylog( N ) entangled EPR pairs). Any classical randomized protocol for f , with any number of rounds, has communication complexity at least
Ω~(N1/4) . All parties in the quantum protocol of Item (1) (Alice, Bob and the referee) can be implemented by quantum circuits of size polylog( N ) (where Alice and Bob have oracle access to their inputs). Items (1), (2) qualitatively match the strongest known separation between quantum and classical communication complexity, proved by Gavinsky (2016). Item (3) is new. (Our result is incomparable to the one of Gavinsky. While he obtained a quantitatively better lower bound of
Ω(N1/2) in the classical case, the referee in his quantum protocol is inefficient). Exponential separations of quantum and classical communication complexity have been studied in numerous previous works, but to the best of our knowledge the efficiency of the parties in the quantum protocol has not been addressed, and in most previous separations the quantum parties seem to be inefficient. The only separations that we know of that have efficient quantum parties are the recent separations that are based on lifting Göös et al. (2017), Chattopadhyay et al. (2019a). However, these separations seem to require quantum protocols with at least two rounds of communication, so they imply a separation of two-way quantum and classical communication complexity, but they do not give the stronger separations of simultaneous-message quantum communication complexity vs. two-way classical communication complexity (or even one-way quantum communication complexity vs. two-way classical communication complexity). Our proof technique is completely new, in the context of communication complexity, and is based on techniques from Raz & Tal (2019). Our function f is based on a lift of the forrelation problem, using xor as a gadget.
We study the advantages of quantum communication models over classical communication models that are equipped with a limited number of qubits of entanglement. In this direction, we give explicit partial functions on
n bits for which reducing the entanglement increases the classical communication complexity exponentially. Our separations are as follows. For every
k≥1:
Q∥∗ versus
R2∗: We show that quantum simultaneous protocols with
Θ~(k5log3n) qubits of entanglement can exponentially outperform two-way randomized protocols with
O(k) qubits of entanglement. This resolves an open problem from [Gav08] and improves the state-of-the-art separations between quantum simultaneous protocols with entanglement and two-way randomized protocols without entanglement [Gav19, GRT22].
R∥∗ versus
Q∥∗: We show that classical simultaneous protocols with
Θ~(klogn) qubits of entanglement can exponentially outperform quantum simultaneous protocols with
O(k) qubits of entanglement, resolving an open question from [GKRW06, Gav19]. The best result prior to our work was a relational separation against protocols without entanglement [GKRW06].
R∥∗ versus
R1∗: We show that classical simultaneous protocols with
Θ~(klogn) qubits of entanglement can exponentially outperform randomized one-way protocols with
O(k) qubits of entanglement. Prior to our work, only a relational separation was known [Gav08]. Our techniques can also be used to show advantages of quantum communication models over hybrid classical-quantum models, i.e., models that have a large amount of both classical communication and quantum simultaneous communication.
A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean functions; the prevailing conjecture is that they cannot be so. In a seminal work, Razborov (2002) resolved this question for AND-functions of the form
F(x,y)=f(x1∧y1,…,xn∧yn), when the outer function
f is symmetric, by proving that their bounded-error quantum and classical communication complexities are polynomially related. Since then, extending this result to all AND-functions has remained open and has been posed by several authors.
In this work, we settle this problem in a strong way. We show that for every Boolean function
f, the bounded-error quantum and classical deterministic communication complexities of the function
f∘AND2 are polynomially related, up to polylogarithmic factors in
n. We prove this by showing that both are characterized--up to polynomial loss--by the logarithm of the De Morgan sparsity of
f.
Our results build on the recent work of Chattopadhyay, Dahiya, and Lovett (2025) on structural characterizations of non-sparse Boolean functions, which we extend to resolve the conjecture for general AND-functions.
A longstanding question in quantum communication complexity is whether some task can be accomplished with a small amount of communication in the presence of entanglement, yet require much more quantum communication in the absence of entanglement. Separations of this nature were previously known for relational problems and, in the simultaneous message passing model, for partial functions. But it has remained unresolved whether any such separation exists for a total Boolean function. We resolve this question with an exponential separation in the one-way setting: we exhibit a family of total Boolean functions
fn:{0,1}n×{0,1}n→{0,1} that can be computed with
O(logn) bits of one-way classical communication given prior entanglement, but that require
Ω(n1/3) qubits of one-way quantum communication without entanglement. Our function is a special case of the subgroup membership problem, first studied in the communication setting by Aaronson, Le Gall, Russell, and Tani.