Two-way finite automata with quantum and classical states
| dc.creator | Ambainis, Andris | |
| dc.creator | Watrous, John | |
| dc.date | 1999-11-16 | |
| dc.date.accessioned | 2026-07-07T03:24:27Z | |
| dc.date.available | 2026-07-07T03:24:27Z | |
| dc.description | We introduce 2-way finite automata with quantum and classical states (2qcfa's). This is a variant on the 2-way quantum finite automata (2qfa) model which may be simpler to implement than unrestricted 2qfa's; the internal state of a 2qcfa may include a quantum part that may be in a (mixed) quantum state, but the tape head position is required to be classical. We show two languages for which 2qcfa's are better than classical 2-way automata. First, 2qcfa's can recognize palindromes, a language that cannot be recognized by 2-way deterministic or probabilistic finite automata. Second, in polynomial time 2qcfa's can recognize {a^n b^n | n>=0}, a language that can be recognized classically by a 2-way probabilistic automaton but only in exponential time. | |
| dc.description | 11 pages | |
| dc.identifier | https://arxiv.org/abs/cs/9911009 | |
| dc.identifier | http://arxiv.org/abs/cs/9911009 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/33331 | |
| dc.subject | Computational Complexity | |
| dc.subject | Quantum Physics | |
| dc.subject | F.1.1 | |
| dc.title | Two-way finite automata with quantum and classical states | |
| dc.type | text |