{
  "annotation_id": "881ced79-aef6-48a5-b47e-f8e022045ae6",
  "date_created": "2026-03-02T18:01:45.339000Z",
  "date_modified": "2026-03-02T18:01:45.339000Z",
  "file_hash": "a7550693c9010acdfd7991af978bfd961f61c5a2bac9d639d51f11c12e98cf0d",
  "private": false,
  "record": {
    "abstract": "We prove new lower bounds for bounded error quantum communication complexity.\nOur methods are based on the Fourier transform of the considered functions.\nFirst we generalize a method for proving classical communication complexity\nlower bounds developed by Raz to the quantum case. Applying this method we give\nan exponential separation between bounded error quantum communication\ncomplexity and nondeterministic quantum communication complexity. We develop\nseveral other lower bound methods based on the Fourier transform, notably\nshowing that \\sqrt{\\bar{s}(f)/\\log n}, for the average sensitivity \\bar{s}(f)\nof a function f, yields a lower bound on the bounded error quantum\ncommunication complexity of f(x AND y XOR z), where x is a Boolean word held by\nAlice and y,z are Boolean words held by Bob. We then prove the first large\nlower bounds on the bounded error quantum communication complexity of\nfunctions, for which a polynomial quantum speedup is possible. For all the\nfunctions we investigate, the only previously applied general lower bound\nmethod based on discrepancy yields bounds that are O(\\log n).",
    "arxiv_id": "quant-ph/0106160",
    "authors": [
      "Hartmut Klauck"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Lower bounds for quantum communication complexity",
    "url": "https://arxiv.org/abs/quant-ph/0106160"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "6b46791d-96d1-4217-8604-817cdef2ce14",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}