Abstract. Since the seminal work of Paturi and Simon [25, FOCS’84 & JCSS’86], the unboundederror classical communication complexity of a Boolean function has been studied based on the arrangement of points and hyperplanes. Recently, [13, ICALP’07] found that the unbounded-error quantum communication complexity in the one-way communication model can also be investigated using the arrangement, and showed that it is exactly (without a difference of even one qubit) half of the classical one-way communication complexity. In this paper, we extend the arrangement argument to the two-way and simultaneous message passing (SMP) models. As a result, we show similarly tight bounds of the unbounded-error two-way/one-way/SMP quantum/classical communication complexities, implying that all of them are equivalent up to a multiplicative constant of four. Moreover, the arrangement argument is used to show that the gap between weakly unbounded-error quantum and classical communication complexities is at most a factor of three. 1
Abstract. Since the seminal work of Paturi and Simon [25, FOCS’84 & JCSS’86], the unboundederror classical communication complexity of a Boolean function has been studied based on the arrangement of points and hyperplanes. Recently, [13, ICALP’07] found that the unbounded-error quantum communication complexity in the one-way communication model can also be investigated using the arrangement, and showed that it is exactly (without a difference of even one qubit) half of the classical one-way communication complexity. In this paper, we extend the arrangement argument to the two-way and simultaneous message passing (SMP) models. As a result, we show similarly tight bounds of the unbounded-error two-way/one-way/SMP quantum/classical communication complexities, implying that all of them are equivalent up to a multiplicative constant of four. Moreover, the arrangement argument is used to show that the gap between weakly unbounded-error quantum and classical communication complexities is at most a factor of three. 1
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.
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.
Abstract. We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HMn: Alice gets as input a string x ∈ {0,1} n, and Bob gets a perfect matching M on the n coordinates. Bob’s goal is to output a tuple 〈i, j, b 〉 such that the edge (i,j) belongs to the matching M and b = xi ⊕ xj. We prove that the quantum one-way communication complexity of HMn is O(logn), yet any randomized one-way protocol with bounded error must use Ω ( √ n) bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM), and hence we provide the first exponential separation between quantum SM and randomized SM with public coins. For a Boolean decision version of HMn, we show that the quantum one-way communication complexity remains O(logn) and that the 0-error randomized one-way communication complexity is Ω(n). We prove that any randomized linear one-way protocol with bounded error for this problem requires Ω ( 3 √ nlog n) bits of communication.
We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HMn: Alice gets as input a string x∈{0,1}n, and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple ⟨i,j,b⟩ such that the edge (i,j) belongs to the matching M and b=xi⊕xj. We prove that the quantum one-way communication complexity of HMn is O(logn), yet any randomized one-way protocol with bounded error must use Ω(n) bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM), and hence we provide the first exponential separation between quantum SM and randomized SM with public coins. For a Boolean decision version of HMn, we show that the quantum one-way communication complexity remains O(logn) and that the 0-error randomized one-way communication complexity is Ω(n). We prove that any randomized linear one-way protocol with bounded error for this problem requires Ω(3nlogn) bits of 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(x₁ ∧ y₁, …, x_n ∧ y_n), 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∘And₂ 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 [Arkadev Chattopadhyay et al., 2026] on structural characterizations of non-sparse Boolean functions, which we extend to resolve the conjecture for general And-functions.
We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HMn: Alice gets as input a string x ∈ (0, 1)n and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple [i,j,b] such that the edge (i,j) belongs to the matching M and b = xi ⊕ xj. We prove that the quantum one-way communication complexity of HMn is O(log n), yet any randomized one-way protocol with bounded error must use Ω(√n) bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM) and hence we provide the first exponential separation between quantum SM and randomized SM with public coins.For a Boolean decision version of HMn, we show that the quantum one-way communication complexity remains O(log n) and that the 0-error randomized one-way communication complexity is Ω(n). We prove that any randomized linear one-way protocol with bounded error for this problem requires Ω(√[3] n log n) bits of communication.