TR26-013 | Quantum–Classical Equivalence for AND-Functions | Sreejata Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett

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 \land y_1, \ldots, x_n \land 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 communication complexities of the AND-function $f \circ \mathrm{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 \circ \mathrm{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.