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 show a new duality between the polynomial margin complexity of
f and the discrepancy of the function
f∘XOR, called an
XOR function. Using this duality, we develop polynomial based techniques for understanding the bounded error (
BPP) and the weakly-unbounded error (
PP) communication complexities of
XOR functions. We show the following. A weak form of an interesting conjecture of Zhang and Shi (Quantum Information and Computation, 2009) (The full conjecture has just been reported to be independently settled by Hatami and Qian (Arxiv, 2017). However, their techniques are quite different and are not known to yield many of the results we obtain here). Zhang and Shi assert that for symmetric functions
f:{0,1}n→{−1,1}, the weakly unbounded-error complexity of
f∘XOR is essentially characterized by the number of points
i in the set
{0,1,…,n−2} for which
Df(i)=Df(i+2), where
Df is the predicate corresponding to
f. The number of such points is called the odd-even degree of
f. We show that the
PP complexity of
f∘XOR is
Ω(k/log(n/k)). We resolve a conjecture of a different Zhang characterizing the Threshold of Parity circuit size of symmetric functions in terms of their odd-even degree. We obtain a new proof of the exponential separation between
PPcc and
UPPcc via an
XOR function. We provide a characterization of the approximate spectral norm of symmetric functions, affirming a conjecture of Ada et al. (APPROX-RANDOM, 2012) which has several consequences. Additionally, we prove strong
UPP lower bounds for
f∘XOR, when
f is symmetric and periodic with period
O(n1/2−ε), for any constant
ε>0.
We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions
p and
q over domains
X and
Y, respectively. Their goal is to estimate
Ex∼p,y∼q[f(x,y)] to within additive error
ε for a bounded function
f, known to both parties. We refer to this as the distributed estimation problem. Special cases of this problem arise in a variety of areas including sketching, databases and learning. Our goal is to understand how the required communication scales with the communication complexity of
f and the error parameter
ε. The random sampling approach -- estimating the mean by averaging
f over
O(1/ε2) random samples -- requires
O(R(f)/ε2) total communication, where
R(f) is the randomized communication complexity of
f. We design a new debiasing protocol which improves the dependence on
1/ε to be linear instead of quadratic. Additionally we show better upper bounds for several special classes of functions, including the Equality and Greater-than functions. We introduce lower bound techniques based on spectral methods and discrepancy, and show the optimality of many of our protocols: the debiasing protocol is tight for general functions, and that our protocols for the equality and greater-than functions are also optimal. Furthermore, we show that among full-rank Boolean functions, Equality is essentially the easiest.
Understanding the entanglement cost of non-local quantum computation (NLQC) is relevant to complexity theory, cryptography, quantum gravity, and other areas. A central special case is
f-routing, motivated in part by quantum position verification. Proving lower bounds on its entanglement cost in the fully robust setting has been a major open problem in NLQC.
Motivated by this problem, we establish two related lower bounds. First, we study the shared-randomness cost of robust conditional disclosure of secrets (CDS). The connection between CDS and
f-routing established by Allerstorfer et al. (Quantum 2024) makes understanding the randomness complexity of robust CDS a natural step toward lower bounds for the fully robust routing problem. We show that the shared-randomness cost of robust CDS is lower bounded by the logarithm of deterministic SMP communication complexity, even when communication and private randomness are unrestricted. Our lower bound is tight for the equality function.
Second, we consider one-sided-perfect
f-routing, in which the protocol is exact on one input class and has constant error on the other. By exploiting the positivity of the low-rank matrix in the method of Asadi, Culf, and May (ITCS 2025), we derive a lower bound on the entanglement cost in terms of sign rank. In particular, this yields a linear lower bound on the entanglement cost of routing for the inner-product function in both one-sided-perfect settings, matching the known upper bound.