In 1999 Raz demonstrated a partial function that had an efficient quantum two-way communication protocol but no efficient classical two-way protocol and asked, whether there existed a function with an efficient quantum one-way protocol, but still no efficient classical two-way protocol. In 2010 Klartag and Regev demonstrated such a function and asked, whether there existed a function with an efficient quantum simultaneous-messages protocol, but still no efficient classical two-way protocol. In this work we answer the latter question affirmatively and present a partial function Shape, which can be computed by a protocol sending entangled simultaneous messages of poly-logarithmic size, and whose classical two-way complexity is lower bounded by a polynomial.
In 1999 Raz demonstrated a partial function that had an efficient quantum two-way communication protocol but no efficient classical two-way protocol and asked whether there existed a function with an efficient quantum one-way protocol, but still no efficient classical two-way protocol. In 2010 Klartag and Regev demonstrated such a function and asked whether there existed a function with an efficient quantum simultaneous-messages protocol, but still no efficient classical two-way protocol. In this work we answer the latter question affirmatively and present a partial function Shape that can be computed by a protocol sending entangled simultaneous messages of poly-logarithmic size, and whose classical two-way complexity is lower bounded by a polynomial.
In STOC 1999, Raz presented a (partial) function for which there is a quantum protocol communicating only
O(logn) qubits, but for which any classical (randomized, bounded-error) protocol requires $\poly(n)$ bits of communication. That quantum protocol requires two rounds of communication. Ever since Raz's paper it was open whether the same exponential separation can be achieved with a quantum protocol that uses only one round of communication. Here we settle this question in the affirmative.
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.
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.
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.