{
  "annotation_id": "3079c732-9246-48bf-9569-5bae2ae6c7d8",
  "date_created": "2026-03-02T18:02:00.223000Z",
  "date_modified": "2026-03-02T18:02:00.223000Z",
  "file_hash": "eb448d134600ce9325cc2503c4b6fc2ae9962c8987b44912e553af610e8105d8",
  "private": false,
  "record": {
    "abstract": "Harry Buhrman et al gave an Omega(sqrt n) lower bound for monotone graph\nproperties in the adjacency matrix query model. Their proof is based on the\npolynomial method. However for some properties stronger lower bounds exist. We\ngive an Omega(n^{3/2}) bound for Graph Connectivity using Andris Ambainis\u0027\nmethod, and an O(n^{3/2} log n) upper bound based on Grover\u0027s search algorithm.\nIn addition we study the adjacency list query model, where we have almost\nmatching lower and upper bounds for Strong Connectivity of directed graphs.",
    "arxiv_id": "quant-ph/0303169",
    "authors": [
      "Christoph Durr",
      "Mehdi Mhalla",
      "Yaohui Lei"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Quantum query complexity of graph connectivity",
    "url": "https://arxiv.org/abs/quant-ph/0303169"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "647fca68-00fe-41a3-9d26-4fa78fda5c98",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}