{"id":"arxiv/2606.03249","url":"https://arxiv.org/abs/2606.03249","tags":["cs.CC","quant-ph"],"score":0,"title":"Quantum-Classical Equivalence for AND-Functions","domain":"cs.CC","source":"arxiv","authors":["Sreejata Kishor Bhattacharya","Farzan Byramji","Arkadev Chattopadhyay","Yogesh Dahiya","Shachar Lovett"],"reviews":0,"subject":"cs.CC","summary":"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_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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-02","reactions":{}}