{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiap2ybt532yr7dbpw7fqtzxyc4f4nwnypdipph4bjo6i2nzhsmwna",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mnespolvevi2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.03249v1",
  "publishedAt": "2026-06-03T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Sreejata Kishor Bhattacharya",
    "Farzan Byramji",
    "Arkadev Chattopadhyay",
    "Yogesh Dahiya",
    "Shachar Lovett"
  ],
  "textContent": "**Authors:** Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett\n\nA 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 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 \\circ \\mathrm{AND}_2$ 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 (2025) on structural characterizations of non-sparse Boolean functions, which we extend to resolve the conjecture for general AND-functions.",
  "title": "Quantum-Classical Equivalence for AND-Functions"
}