{
  "annotation_id": "09265151-9541-41c8-a703-bcc382598572",
  "date_created": "2026-03-02T18:02:34.603000Z",
  "date_modified": "2026-03-02T18:02:34.603000Z",
  "file_hash": "d46f77a37ce610569287573562e5018b05efbe267bb28ae6e079a6bee75e83b4",
  "private": false,
  "record": {
    "abstract": "In this paper, we focus on determining the equivalence for {\\it 1-way quantum\nfinite automata with control language} (CL-1QFAs) defined by Bertoni et al and\n{\\it measure-many 1-way quantum finite automata} (MM-1QFAs) introduced by\nKondacs and Watrous. More specifically, we obtain that: \\begin{enumerate}\n  \\item[(i)] Two CL-1QFAs ${\\cal A}_1$ and ${\\cal A}_2$ with control languages\n(regular languages) ${\\cal L}_1$ and ${\\cal L}_2$, respectively, are equivalent\nif and only if they are $(c_1n_1^2+c_2n_2^2-1)$-equivalent. Furthermore, if\n${\\cal L}_1$ and ${\\cal L}_2$ are given in the form of DFAs, with $m_1$ and\n$m_2$ states, respectively, then there exists a polynomial-time algorithm\nrunning in time $O ((m_1n_1^2+m_2n_2^2)^4)$ that takes as input ${\\cal A}_1$\nand ${\\cal A}_2$ and determines whether they are equivalent. \\item[(ii)] Two\nMM-1QFAs ${\\cal A}_1$ and ${\\cal A}_2$ with $n_1$ and $n_2$ states,\nrespectively, are equivalent if and only if they are\n$(3n_1^2+3n_2^2-1)$-equivalent. Furthermore, there is a polynomial-time\nalgorithm running in time $O ((3n_1^2+3n_2^2)^4)$ that takes as input ${\\cal\nA}_1$ and ${\\cal A}_2$ and determines whether ${\\cal A}_1$ and ${\\cal A}_2$ are\nequivalent.",
    "arxiv_id": "quant-ph/0703087",
    "authors": [
      "Lvzhou Li",
      "Daowen Qiu"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Determining the equivalence for 1-way quantum finite automata",
    "url": "https://arxiv.org/abs/quant-ph/0703087"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "c351da22-50ee-4566-8f76-f70cb6a936ec",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}