On Quantum–Classical Equivalence in the Communication Model
Yogesh Dahiya (UC San Diego)
Monday, February 9th, 2026, 2-3pm
Abstract:
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 AND_2 y_1, ..., x_n AND_2 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 composed with the two-bit AND function are polynomially related, up to polylogarithmic factors in n. Moreover, modulo such polylogarithmic factors, we prove that the bounded-error quantum communication complexity of such functions 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 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 talk is based on joint work with Sreejata Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, and Shachar Lovett. The paper is available at
https://eccc.weizmann.ac.il/