{
  "annotation_id": "a1e91319-6748-4bf2-a6df-fbcf406599c6",
  "date_created": "2026-03-02T18:02:03.586000Z",
  "date_modified": "2026-03-02T18:02:03.586000Z",
  "file_hash": "6f16942d3f056514a682139ddbfc734cabceb76d5d6d60e42551c66873c118dd",
  "private": false,
  "record": {
    "abstract": "A recent paper on quantum walks by Childs et al. [STOC\u002703] provides an\nexample of a black-box problem for which there is a quantum algorithm with\nexponential speedup over the best classical randomized algorithm for the\nproblem, but where the quantum algorithm does not involve any use of the\nquantum Fourier transform. They give an exponential lower bound for a classical\nrandomized algorithm solving the black-box graph traversal problem defined in\ntheir paper. In this note we give an improved lower bound for this problem via\na straightforward and more complete analysis.",
    "arxiv_id": "quant-ph/0312230",
    "authors": [
      "Stephen A. Fenner",
      "Yong Zhang"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "A note on the classical lower bound for a quantum walk algorithm",
    "url": "https://arxiv.org/abs/quant-ph/0312230"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "5001fa8d-3b19-4a41-9f82-1a856198abad",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}