{
  "annotation_id": "b8dfc6dd-e9e2-48f5-b76f-56e9f0cdec96",
  "date_created": "2026-03-02T18:02:03.228000Z",
  "date_modified": "2026-03-02T18:02:03.228000Z",
  "file_hash": "8922a5addb5a81cb41950c47bbe8e24b993c3d96f232afcaab5d4a14a0c81320",
  "private": false,
  "record": {
    "abstract": "This paper employs a powerful argument, called an algorithmic argument, to\nprove lower bounds of the quantum query complexity of a multiple-block ordered\nsearch problem in which, given a block number i, we are to find a location of a\ntarget keyword in an ordered list of the i-th block. Apart from much studied\npolynomial and adversary methods for quantum query complexity lower bounds, our\nargument shows that the multiple-block ordered search needs a large number of\nnonadaptive oracle queries on a black-box model of quantum computation that is\nalso supplemented with advice. Our argument is also applied to the notions of\ncomputational complexity theory: quantum truth-table reducibility and quantum\ntruth-table autoreducibility.",
    "arxiv_id": "quant-ph/0312003",
    "authors": [
      "Harumichi Nishimura",
      "Tomoyuki Yamakami"
    ],
    "categories": [
      "quant-ph",
      "cs.CC"
    ],
    "doi": "10.1007/978-3-540-28629-5_65",
    "journal_ref": "Proceedings of the 29th International Symposium on Mathematical\n  Foundations of Computer Science (MFCS2004), Lecture Notes in Computer Science\n  3153, pp. 827-838, 2004",
    "title": "An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on   Advised Quantum Computation",
    "url": "https://arxiv.org/abs/quant-ph/0312003"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "dd1a6a53-7c0f-48fc-bead-08f3af9a6413",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}