{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigcfh5xye2leycf3plkecd7mp5e7zfcg4eyyzte5cvfkqsru2ls2e",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3medp4gxebgm2"
  },
  "path": "/report/2026/013",
  "publishedAt": "2026-02-08T07:53:40.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "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.",
  "title": "TR26-013 |  Quantum–Classical Equivalence for AND-Functions | \n\n\tSreejata Bhattacharya, \n\n\tFarzan Byramji, \n\n\tArkadev Chattopadhyay, \n\n\tYogesh Dahiya, \n\n\tShachar Lovett"
}