{
  "annotation_id": "bbeaa4d0-b08d-4586-91e5-b9ba44a5a0e0",
  "date_created": "2026-03-02T18:02:03.229000Z",
  "date_modified": "2026-03-02T18:02:03.229000Z",
  "file_hash": "eb1c6c72ef5f60129b7d1f28eed5c0c5e957e04b4c462a98c6c6304626fa435e",
  "private": false,
  "record": {
    "abstract": "We prove a very general lower bound technique for quantum and randomized\nquery complexity, that is easy to prove as well as to apply. To achieve this,\nwe introduce the use of Kolmogorov complexity to query complexity. Our\ntechnique generalizes the weighted, unweighted methods of Ambainis, and the\nspectral method of Barnum, Saks and Szegedy. As an immediate consequence of our\nmain theorem, adversary methods can only prove lower bounds for boolean\nfunctions $f$ in $O(\\min(\\sqrt{n C_0(f)},\\sqrt{n C_1(f)}))$, where $C_0, C_1$\nis the certificate complexity, and $n$ is the size of the input. We also derive\na general form of the ad hoc weighted method used by Hoyer, Neerbek and Shi to\ngive a quantum lower bound on ordered search and sorting.",
    "arxiv_id": "quant-ph/0311189",
    "authors": [
      "Sophie Laplante",
      "Frederic Magniez"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Lower bounds for randomized and quantum query complexity using   Kolmogorov arguments",
    "url": "https://arxiv.org/abs/quant-ph/0311189"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "21453775-1cb4-45c3-a8e8-8e1c6c331b00",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}