A major open problem at the interface of quantum computing and 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 are not. In a seminal work, Razborov (2002) resolved this question for AND-functions of the form
F(x, y)=f(x_1, y_1, ..., 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. We show that for every Boolean function f, the bounded-error quantum and classical randomized communication complexities of the AND-function f • AND_2 are polynomially related, up to polylogarithmic factors in n. Moreover, modulo such polylogarithmic factors, we prove that the bounded-error quantum communication complexity of f • AND_2 is polynomially equivalent to its deterministic communication complexity, and 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.
Based on joint work with Farzan Byramji, Arkadev Chattopadhyay, Yogesh Dahiya, and Shachar Lovett.
