{
  "annotation_id": "b85b8563-500a-4ba4-943f-68dd258b9abc",
  "date_created": "2026-03-02T18:01:49.511000Z",
  "date_modified": "2026-03-02T18:01:49.511000Z",
  "file_hash": "7c30b069d9fed2c3bcf4eccd164a4d3f6026f22f6ffcb8b9fdcde8425fbf2fb6",
  "private": false,
  "record": {
    "abstract": "The main purpose of this paper is to show that we can exploit the difference\n($l_1$-norm and $l_2$-norm) in the probability calculation between quantum and\nprobabilistic computations to claim the difference in their space efficiencies.\nIt is shown that there is a finite language $L$ which contains sentences of\nlength up to $O(n^{c+1})$ such that: ($i$) There is a one-way quantum finite\nautomaton (qfa) of $O(n^{c+4})$ states which recognizes $L$. ($ii$) However, if\nwe try to simulate this qfa by a probabilistic finite automaton (pfa)\n\\textit{using the same algorithm}, then it needs $\\Omega(n^{2c+4})$ states. It\nshould be noted that we do not prove real lower bounds for pfa\u0027s but show that\nif pfa\u0027s and qfa\u0027s use exactly the same algorithm, then qfa\u0027s need much less\nstates.",
    "arxiv_id": "quant-ph/0204075",
    "authors": [
      "Masami Amano",
      "Kazuo Iwama",
      "Rudy Raymond"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Exploiting the Difference in Probability Calculation between Quantum and   Probabilistic Computations",
    "url": "https://arxiv.org/abs/quant-ph/0204075"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "ba9ded8f-e609-4c57-b506-93c8b7a10413",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}