{
  "annotation_id": "53a1b2b3-ef99-469c-b080-42a152311eb1",
  "date_created": "2026-03-02T18:02:15.966000Z",
  "date_modified": "2026-03-02T18:02:15.966000Z",
  "file_hash": "717aca911e9c0b859b32aedf7869300c2c21b8fd76976da4aa042ae9b06d0312",
  "private": false,
  "record": {
    "abstract": "We define a quantum model for multiparty communication complexity and prove a\nsimulation theorem between the classical and quantum models. As a result of our\nsimulation, we show that if the quantum k-party communication complexity of a\nfunction f is $\\Omega(n/2^k)$, then its classical k-party communication is\n$\\Omega(n/2^{k/2})$. Finding such an f would allow us to prove strong classical\nlower bounds for (k\u003elog n) players and hence resolve a main open question about\nsymmetric circuits. Furthermore, we prove that for the Generalized Inner\nProduct (GIP) function, the quantum model is exponentially more efficient than\nthe classical one. This provides the first exponential separation for a total\nfunction between any quantum and public coin randomized communication model.",
    "arxiv_id": "quant-ph/0504087",
    "authors": [
      "Iordanis Kerenidis"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Quantum multiparty communication complexity and circuit lower bounds",
    "url": "https://arxiv.org/abs/quant-ph/0504087"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "809c6fb4-895a-429e-b32e-9b2e2129b636",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}