{
  "annotation_id": "cdd4363b-86b0-4be5-998d-acc50ad1be37",
  "date_created": "2026-03-02T18:02:47.312000Z",
  "date_modified": "2026-03-02T18:02:47.312000Z",
  "file_hash": "bb04af785e1fb93d45e3402dca92e776ee5f1942772edb52f5f55744e23dfd51",
  "private": false,
  "record": {
    "abstract": "Quantum finite automata were introduced by C.Moore, J.P. Crutchfield, and by\nA.Kondacs and J.Watrous. This notion is not a generalization of the\ndeterministic finite automata. Moreover, it was proved that not all regular\nlanguages can be recognized by quantum finite automata. A.Ambainis and\nR.Freivalds proved that for some languages quantum finite automata may be\nexponentially more concise rather than both deterministic and probabilistic\nfinite automata. In this paper we introduce the notion of quantum finite\nmultitape automata and prove that there is a language recognized by a quantum\nfinite automaton but not by a deterministic or probabilistic finite automata.\nThis is the first result on a problem which can be solved by a quantum computer\nbut not by a deterministic or probabilistic computer. Additionally we discover\nunexpected probabilistic automata recognizing complicated languages.",
    "arxiv_id": "quant-ph/9905026",
    "authors": [
      "Andris Ambainis",
      "Richard Bonner",
      "Rusins Freivalds",
      "Marats Golovkins",
      "Marek Karpinski"
    ],
    "categories": [
      "quant-ph",
      "cs.CC",
      "cs.FL"
    ],
    "title": "Quantum finite multitape automata",
    "url": "https://arxiv.org/abs/quant-ph/9905026"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "15f89059-80dd-44b3-95fe-186f4819021a",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}