1999/11/16 by Andris Ambainis, John Watrous, Ambainis, Andris +1
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #F.1.1 #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #cs.CC #quant-ph #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.cs/9911009
11 pages
arxiv created 1999/11/16 · openalex publication_date 1999/11/16 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 an bn | n>=0, a language that can be recognized classically by a 2-way probabilistic automaton but only in exponential time.