dorsal/arxiv
View SchemaA small 1-way quantum finite automaton
| Authors | Arnolds Kikusts |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9810065 |
| URL | https://arxiv.org/abs/quant-ph/9810065 |
Abstract
We study 1-way quantum finite automata (QFAs) and compare them with their classical counterparts. We show that 1-way QFAs can be very space efficient. We construct a 1-way QFAs that are quadratically smaller than any equivalent deterministic finite automata and give the correct answer with a large probability by recognizing the languages in a two letter alphabet "the number of the letters a and the number of the letters b are divisible by n".
{
"annotation_id": "ed881884-505d-4505-927a-be1a19a9556c",
"date_created": "2026-03-02T18:02:44.138000Z",
"date_modified": "2026-03-02T18:02:44.138000Z",
"file_hash": "1e4f03b8eaecf60b366c7842b5ae5035c37e5ec326cb670b194ae74814ae6f40",
"private": false,
"record": {
"abstract": "We study 1-way quantum finite automata (QFAs) and compare them with their\nclassical counterparts. We show that 1-way QFAs can be very space efficient. We\nconstruct a 1-way QFAs that are quadratically smaller than any equivalent\ndeterministic finite automata and give the correct answer with a large\nprobability by recognizing the languages in a two letter alphabet \"the number\nof the letters a and the number of the letters b are divisible by n\".",
"arxiv_id": "quant-ph/9810065",
"authors": [
"Arnolds Kikusts"
],
"categories": [
"quant-ph"
],
"title": "A small 1-way quantum finite automaton",
"url": "https://arxiv.org/abs/quant-ph/9810065"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "9dd3e7b8-b153-4e32-85ad-002bd8bbb7ac",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}