{
  "annotation_id": "8789d9ee-b6f5-4ff3-bcc2-01496610143b",
  "date_created": "2026-03-02T18:02:41.715000Z",
  "date_modified": "2026-03-02T18:02:41.715000Z",
  "file_hash": "5560649525d04ce20f1c8d48a11eef0b405cf937ab5667d0528d33792a7eaf38",
  "private": false,
  "record": {
    "abstract": "We study 1-way quantum finite automata (QFAs). First, we compare them with\ntheir classical counterparts. We show that, if an automaton is required to give\nthe correct answer with a large probability (over 0.98), then the power of\n1-way QFAs is equal to the power of 1-way reversible automata. However, quantum\nautomata giving the correct answer with smaller probabilities are more powerful\nthan reversible automata.\n  Second, we show that 1-way QFAs can be very space-efficient. Namely, we\nconstruct a 1-way QFA which is exponentially smaller than any equivalent\nclassical (even randomized) finite automaton. This construction may be useful\nfor design of other space-efficient quantum algorithms.\n  Third, we consider several generalizations of 1-way QFAs. Here, our goal is\nto find a model which is more powerful than 1-way QFAs keeping the quantum part\nas simple as possible.",
    "arxiv_id": "quant-ph/9802062",
    "authors": [
      "A. Ambainis",
      "R. Freivalds"
    ],
    "categories": [
      "quant-ph",
      "cs.CC"
    ],
    "title": "1-way quantum finite automata: strengths, weaknesses and generalizations",
    "url": "https://arxiv.org/abs/quant-ph/9802062"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "f8aac18a-e80c-4606-be08-6c48b12e0426",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}