Paper Info
Title
Superiority of one-way and realtime quantum machines.
Abstract
In automata theory, quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of QFAs where the input head operates in one-way or realtime mode, and present some new results regarding their superiority over their classical counterparts. Our first result is about the nondeterministic acceptance mode: Each quantum model architecturally intermediate between realtime finite state automaton and one-way pushdown automaton (one-way finite automaton, realtime and one-way finite automata with one-counter, and realtime pushdown automaton) is superior to its classical counterpart. The second and third results are about bounded error language recognition: for any k > 0, QFAs with k blind counters outperform their deterministic counterparts; and, a one-way QFA with a single head recognizes an infinite family of languages, which can be recognized by one-way probabilistic finite automata with at least two heads. Lastly, we compare the nondeterminictic and deterministic acceptance modes for classical finite automata with k blind counter(s), and we show that for any k > 0, the nondeterministic models outperform the deterministic ones.
Year
DOI
Venue
2012
10.1051/ita/2012018
RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS
Keywords
Field
DocType
Quantum computation,quantum automata,blind counter automata,multihead finite automata,nondeterminism,bounded error
Discrete mathematics,Quantum finite automata,Automata theory,Nondeterministic algorithm,Quantum computer,Algorithm,Finite-state machine,Pushdown automaton,Mathematics,Quantum cellular automaton,ω-automaton
Journal
Volume
Issue
ISSN
46
SP4
0988-3754
Citations 
PageRank 
References 
4
0.46
21
Authors
1
Name
Order
Citations
PageRank
Abuzer Yakaryilmaz116825.31