dorsal/arxiv
View SchemaSome observations on two-way finite automata with quantum and classical states
| Authors | Daowen Qiu |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0701187 |
| URL | https://arxiv.org/abs/quant-ph/0701187 |
| Journal | Lecture Notes in Computer Science, vol. 5226, pp.1-8, 2008. |
Abstract
{\it Two-way finite automata with quantum and classical states} (2qcfa's) were introduced by Ambainis and Watrous. Though this computing model is more restricted than the usual {\it two-way quantum finite automata} (2qfa's) first proposed by Kondacs and Watrous, it is still more powerful than the classical counterpart. In this note, we focus on dealing with the operation properties of 2qcfa's. We prove that the Boolean operations (intersection, union, and complement) and the reversal operation of the class of languages recognized by 2qcfa's with error probabilities are closed; as well, we verify that the catenation operation of such class of languages is closed under certain restricted condition. The numbers of states of these 2qcfa's for the above operations are presented. Some examples are included, and $\{xx^{R}|x\in \{a,b\}^{*},#_{x}(a)=#_{x}(b)\}$ is shown to be recognized by 2qcfa with one-sided error probability, where $x^{R}$ is the reversal of $x$, and $#_{x}(a)$ denotes the $a$'s number in string $x$.
{
"annotation_id": "ce371cf2-d348-4488-9ec9-216ca3fd7234",
"date_created": "2026-03-02T18:02:34.425000Z",
"date_modified": "2026-03-02T18:02:34.425000Z",
"file_hash": "3795e771834fbcd00d532d79b30b44d99e8006098909ff16444a790adbbb7020",
"private": false,
"record": {
"abstract": "{\\it Two-way finite automata with quantum and classical states} (2qcfa\u0027s)\nwere introduced by Ambainis and Watrous. Though this computing model is more\nrestricted than the usual {\\it two-way quantum finite automata} (2qfa\u0027s) first\nproposed by Kondacs and Watrous, it is still more powerful than the classical\ncounterpart. In this note, we focus on dealing with the operation properties of\n2qcfa\u0027s. We prove that the Boolean operations (intersection, union, and\ncomplement) and the reversal operation of the class of languages recognized by\n2qcfa\u0027s with error probabilities are closed; as well, we verify that the\ncatenation operation of such class of languages is closed under certain\nrestricted condition. The numbers of states of these 2qcfa\u0027s for the above\noperations are presented. Some examples are included, and $\\{xx^{R}|x\\in\n\\{a,b\\}^{*},#_{x}(a)=#_{x}(b)\\}$ is shown to be recognized by 2qcfa with\none-sided error probability, where $x^{R}$ is the reversal of $x$, and\n$#_{x}(a)$ denotes the $a$\u0027s number in string $x$.",
"arxiv_id": "quant-ph/0701187",
"authors": [
"Daowen Qiu"
],
"categories": [
"quant-ph"
],
"journal_ref": "Lecture Notes in Computer Science, vol. 5226, pp.1-8, 2008.",
"title": "Some observations on two-way finite automata with quantum and classical states",
"url": "https://arxiv.org/abs/quant-ph/0701187"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "7674b314-ef66-4adc-8e2f-b2657fc97573",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}