2026-07-23T20:56:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27065 2026-07-23T11:36:19Z ddc:004 open_access

Quantum-Classical Equivalence for And-Functions Bhattacharya, Sreejata Kishor Byramji, Farzan Chattopadhyay, Arkadev Dahiya, Yogesh Lovett, Shachar Communication complexity quantum communication complexity De Morgan sparsity approximate gamma two norm And-functions 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₁ ∧ y₁, …, 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 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∘And₂ 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 [Arkadev Chattopadhyay et al., 2026] on structural characterizations of non-sparse Boolean functions, which we extend to resolve the conjecture for general And-functions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sreejata Kishor Bhattacharya and Farzan Byramji and Arkadev Chattopadhyay and Yogesh Dahiya and Shachar Lovett 2026 Is Part Of LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2026.23 urn:nbn:de:0030-drops-270656 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.23 eng https://creativecommons.org/licenses/by/4.0/legalcode