{
  "annotation_id": "e9359c43-18de-4b41-bd92-688a8d7697b1",
  "date_created": "2026-03-02T18:02:41.037000Z",
  "date_modified": "2026-03-02T18:02:41.037000Z",
  "file_hash": "a1382a86403b3b94169ae35f7f1b78cb19b74f87143134e5d9a94a2b1b0f92ae",
  "private": false,
  "record": {
    "abstract": "Let a classical algorithm be determined by sequential applications of a black\nbox performing one step of this algorithm. If we consider this black box as an\noracle which gives a value F(a) for any query a, we can compute T sequential\napplications of F on a classical computer relative to this oracle in time T.\n  It is proved that if T=O(2^{n/7}), where n is the length of input, then the\nresult of T sequential applications of F can not be computed on quantum\ncomputer with oracle for F for all possible F faster than in time \\Omega (T).\nThis means that there is no general method of quantum speeding up of classical\nalgorithms provided in such a general method a classical algorithm is regarded\nas iterated applications of a given black box.\n  For an arbitrary time complexity T a lower bound for the time of quantum\nsimulation was found to be \\Omega (T^{1/2}).",
    "arxiv_id": "quant-ph/9712051",
    "authors": [
      "Yuri Ozhigov"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Quantum Computer Can Not Speed Up Iterated Applications of a Black Box",
    "url": "https://arxiv.org/abs/quant-ph/9712051"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "0c69d7c1-71d1-45ab-839d-65b7a070f50f",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}