{
  "annotation_id": "aa8725f2-ac26-4db0-bb08-878ab6df4974",
  "date_created": "2026-03-02T18:02:05.749000Z",
  "date_modified": "2026-03-02T18:02:05.749000Z",
  "file_hash": "9839932d374a84978f65766eb618917058179b190cb583fec6b7404dc095f18d",
  "private": false,
  "record": {
    "abstract": "Quantum algorithms for graph problems are considered, both in the adjacency\nmatrix model and in an adjacency list-like array model. We give almost tight\nlower and upper bounds for the bounded error quantum query complexity of\nConnectivity, Strong Connectivity, Minimum Spanning Tree, and Single Source\nShortest Paths. For example we show that the query complexity of Minimum\nSpanning Tree is in Theta(n^{3/2}) in the matrix model and in Theta(sqrt{nm})\nin the array model, while the complexity of Connectivity is also in\nTheta(n^{3/2}) in the matrix model, but in Theta(n) in the array model. The\nupper bounds utilize search procedures for finding minima of functions under\nvarious conditions.",
    "arxiv_id": "quant-ph/0401091",
    "authors": [
      "Christoph Durr",
      "Mark Heiligman",
      "Peter Hoyer",
      "Mehdi Mhalla"
    ],
    "categories": [
      "quant-ph"
    ],
    "doi": "10.1137/050644719",
    "journal_ref": "SIAM J. Comput., 35(6), 1310-1328 (19 pages), 2006",
    "title": "Quantum query complexity of some graph problems",
    "url": "https://arxiv.org/abs/quant-ph/0401091"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "ec1c61e9-3410-4d98-b1ee-932f2f7689bf",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}